avoid megamorphic call site with bytecode weaving

junkdog commented 10 years ago

EntityProcessingSystem#process(Entity)
PackedComponent#forEntity(Entity)
Progess update:

Benchmark results

Test: NormalSpeedBenchmark (nvm the name)

Score = average execution time invoking world.process(), measured in microseconds.

without optimizeEntitySystems

Benchmark                               (entityCount)  Mode  Samples     Score  Score error  Units
c.a.NormalSpeedBenchmark.plain_world             1024  avgt        3    30.368        4.751  us/op
c.a.NormalSpeedBenchmark.plain_world             4096  avgt        3   135.582       97.552  us/op
c.a.NormalSpeedBenchmark.plain_world            16384  avgt        3   506.352      168.231  us/op
c.a.NormalSpeedBenchmark.plain_world            65536  avgt        3  3840.948      179.433  us/op

with optimizeEntitySystems

Benchmark                               (entityCount)  Mode  Samples     Score  Score error  Units
c.a.NormalSpeedBenchmark.plain_world             1024  avgt        3    20.099        1.553  us/op
c.a.NormalSpeedBenchmark.plain_world             4096  avgt        3   105.755       62.644  us/op
c.a.NormalSpeedBenchmark.plain_world            16384  avgt        3   391.068       37.549  us/op
c.a.NormalSpeedBenchmark.plain_world            65536  avgt        3  3444.936      165.864  us/op

How to enable

Optimization is automatically applied when running with the maven plugin, optionally one can explicitly enable/disable entity system optimizations:

    <properties>
        <artemis.version>0.6.6-SNAPSHOT</artemis.version>
        <optimizeSystems>false</optimizeSystems>
    </properties>

    <profiles>
        <profile>
            <id>fast</id>
            <properties>
                <optimizeSystems>true</optimizeSystems>
            </properties>
        </profile>
    </profiles>

    <build>
        <plugins>
            <plugin>
                <groupId>net.onedaybeard.artemis</groupId>
                <artifactId>artemis-odb-maven-plugin</artifactId>
                <version>${artemis.version}</version>
                <executions>
                    <execution>
                        <goals>
                            <goal>artemis</goal>
                        </goals>
                        <configuration>
                            <optimizeEntitySystems>${optimizeSystems}</optimizeEntitySystems>
                        </configuration>
                    </execution>
                </executions>
            </plugin>
        </plugins>
    </build>

Remaining

artemis-odb-cli support
per-EntityProcessingSystem#process INVOKEVIRTUAL/INVOKESPECIAL depending on usage
optimize other base entity systems?
@PackedWeaver and PackedComponentMapper optimizations, although probably not related to this issue,

DaanVanYperen commented 10 years ago

I want cool sounding issues like this in my projects.

junkdog commented 10 years ago

Mathematicians seized all cool terminology, only leaving isolated words for the rest of us.

That said, I figured out a way of reducing artemis' overhead by a large amount: simply avoid calling/implementing abstract EntityProcessingSystem#process(Entity) - when doing it by hand, the benchmarks results improved by 1/3 to 1/4.

junkdog commented 10 years ago

Mechanical Sympathy on method invocation costs.

JesseTG commented 10 years ago

Mathematicians seized all cool terminology, only leaving isolated words for the rest of us.

We steal all our terms from real life anyway. Texture. File. Directory. Object. Code. Machine. I'm sure mathematicians won't mind if we gank a few more.

Flet commented 10 years ago

Mechanical Sympathy is also the name of my ambient space music band.

junkdog commented 10 years ago

I'm sure mathematicians won't mind if we gank a few more.

Such as Shinichi Mochizuki's alien arithmetic holomorphic structures?

Mechanical Sympathy is also the name of my ambient space music band.

Cool, have any links?

Flet commented 10 years ago

It was a joke :)

junkdog commented 10 years ago

There's been progress, updated description.

DaanVanYperen commented 10 years ago

There's been progress

pff, where's my GWT support for bytecode weaving, slacker!

DaanVanYperen commented 10 years ago

Cool beans though! I'll write you up a nice wiki page if you want, it's the perfect leg stretcher for a crunch. ;)

Can you ELI5 a summary? Something like:

how does this work,
what are the design constraints a user has to consider.
android compatibility/benefits.
Any other weaving goodness currently not advertised?

junkdog commented 10 years ago

pff, where's my GWT support for bytecode weaving, slacker!

When I've figured out how to implement a worldwide kill-switch into JS - maybe then we can populate the web with sane languages.

(There's some experimentation scheduled for sometime after 0.7.0 - need to figure out how to compile bytecode back to java source (lombok does a pretty good job with delombok) plus benchmark GWT; it'll be easy if everything transpires smoothly, but that never happens when breaching the java-javascript barrier)

Can you ELI5 a summary? Something like:

how does this work,

Some background

Normally, when invoking World#process, an EntityProcessingSystem is invoked as follows:

EntitySystem#process: method is declared final so only one implementation - cheap for the JVM to call
EntitySystem#process makes a call to abstract method #processEntities: since this one has several implementations, method invocation is much slower (10-20x is often cited, but regardless, it's much slower) - though it doesn't really matter since it's only called once per system and tick.
EntityProcessingSystem#processEntities - the most common parent for concrete entity systems - declares protected abstract void process(Entity e);; as EntityProcessingSystem#process(Entity) is likely to be one of the most frequently executed methods AND has multiple implementations (one for each concrete entity processing system), the higher method invocation cost builds up
In summary:
- EntitySystem#process: monomorphic
- EntityProcessingSystem#processEntities: megamorphic
- EntityProcessingSystem#process(Entity): megamorphic and invoked once per entity per system, every tick.

Ideally, we'd like to get rid of the expensive call to EntityProcessingSystem#process(Entity),

Practical

Scans all classes, looking for those directly extending EntityProcessingSystem
Replaces super class: s/EntityProcessingSystem/EntitySystem
Injects processEntities, copied from EntityProcessingSystem. Method is already megamorphic, so it doesn't affect performance noticeably if we add a few more.
Rewrite #process(Entity) as a private method
- Since #process(Entity) is only declared abstract in EntityProcessingSystem, we are no longer invoking a polymorphic method; ie, the method is now monomorphic.

what are the design constraints a user has to consider.

Currently, #process(Entity) becomes private (there seems to be a slight perf gain from invoking it as a private method, presumably the JVM can omit de-optimization guards in the generated assembly).

It will however be fixed before the issue is closed, probably with an annotation of some sort: so if one needs to invoke #process from an external class, it should be possible to control.

Also, doesn't work from the CLI tool yet, but it's coming.

android compatibility/benefits.

Compatible, though I haven't tested it. Not sure how aggressively dalvik JITs stuff or how it does its method dispatch. I'd like to think it'd improve performance, but needs testing.

Any other weaving goodness currently not advertised?

Nope, apart from making this work with GWT too, but it's further down the line. @PackedWeaver can likely be optimized without relying on bytecode manipulation.

DaanVanYperen commented 10 years ago

Interesting! Does the class still report as an instanceof EntityProcessingSystem? I assume not.

Wonder if this even applies to javascript. GWT must jump through some interesting hoops to emulate java classes to begin with.

DaanVanYperen commented 10 years ago

I've figured out how to implement a worldwide kill-switch into JS

D: Did I mention my crunch is a web based application that will fail horribly without JS. I'm all for a change but this close to a deadline? Thanks for feeding my nightmares! ;)

junkdog commented 10 years ago

Does the class still report as an instanceof EntityProcessingSystem? I assume not.

Nope, no traces left of EntityProcessingSystem.

Wonder if this even applies to javascript. GWT must jump through some interesting hoops to emulate java classes to begin with.

It would be possible to inline #process(Entity) inside #processEntities, but the bigger win would probably come from supporting @PackedWeaver, @PooledWeaver and @Profile in GWT.

D: Did I mention my crunch is a web based application that will fail horribly without JS. I'm all for a change but this close to a deadline? Thanks for feeding my nightmares! ;)

It should be an occasion for celebration: an opportunity to bring the project to a close before the deadline!

junkdog commented 10 years ago

Another constraint: doesn't work with classes imported from external jars, though this is true for all of artemis' weaving, including the matrix. Should probably fix before 0.7.0 - or better: before LD48.

DaanVanYperen commented 10 years ago

Mind copying over your comments to the wiki? I'm not sure how to grab your markdown. I can cleanup after if you want.

Optimize system tight loops https://github.com/junkdog/artemis-odb/wiki/Megamorphic

junkdog commented 10 years ago

Copied.

I've started putting together an overview of what the bytecode weaving and instrumentation facilities provide: there may be some structural changes to the wiki in the next hour or so.

junkdog commented 10 years ago

Renamed page to: https://github.com/junkdog/artemis-odb/wiki/Optimizing-Entity-Systems

junkdog / artemis-odb