[font=arial]
dustArtemis
[/font][font=arial]dustArtemis is a fork of Artemis Entity System, which is a BSD-licenced small Java framework for setting up Entities, Components and Systems.[/font]
[font=arial]
Updates!
[/font][font=arial]I kinda lied, no puppies sadly. I got several updates tho share though:[/font]
[font=arial]
Ordered Iteration
[/font][font=arial]The principle of the 'Bag' collection is that disregards item order inside. If you remove an item, it doesn't shifts elements to fill the open slot, rather it just puts the last element in the array there. This has the tendency of simply mixing the element ordering on removals.[/font]
[font=arial]There is a good reason for this, copying an element is much less work than copying whatever's left of the backing array one position to the left to fill the gap.[/font]
[font=arial]My solution to entity removal times in original Artemis (basically, linearly searching through entire entity 'Bag' in a system) was simply reducing the linear search. Entities stored the position they were located on each system, and on removal, the system would just linearly search for itself in the entity's array to grab the index of the entity. This reduces the linear search from possibly thousand elements to just a few dozen at most.[/font]
[font=arial]This still mixes up the contents of the entity 'Bag', so to preserve ordering I decided to go implement ArrayList-like behavior on 'Bag' and just use binary search on the entities. Turns out that even with the whole array shifting, ordered iteration of entities is actually faster than whatever gains I had on entity removals with the previous method.[/font]
private final void removeFromSystem ( final Entity e ) { // Binary search for index. final int ei = searchFor( e ); // Remove entity, shift items to left. actives.eraseUnsafe( ei ); // fastClear, new OpenBitSet method! e.systemBits.fastClear( index ); removed( e );} private final void insertToSystem ( final Entity e ) { // Binary search for insert position. final int ei = -(searchFor( e ) + 1); // Make sure actives can hold the entity. actives.ensureCapacity( actives.size() + 1 ); // Insert entity at found index. actives.insertUnsafe( ei, e ); // Update system bits for entity. e.systemBits.set( index ); inserted( e );}
[font=arial]I wasn't totally convinced on the benefits of ordered iteration at first simply because JVM deals with references. So even if I am retrieving components and entities in order, there is no guarantee they're close in memory. The only way to guarantee locality is to use native buffers.[/font]
[font=arial]
Say hi to OpenBitSet
[/font][font=arial]BitSets are quite important in Artemis, they tell what component types an Entity has, what kind of entities an Aspect is interested on. Sadly, standard JDK BitSet has most of the operations implemented via mutating the state of the BitSet. So, if you wanted to check if an Entity had all the components an Aspect wanted, instead of just ANDing the bit sets, you'd need to check bit by bit in an ugly for loop.[/font]
[font=arial]Imagine this Aspect check (which was before in EntitySystem, I moved it to Aspect) is done for all entities, for all systems, for all component changes. That's a lot of checks! And the 'allSet' check is the one most often used.[/font]
/** Check if the entity possesses ALL of the components defined in the* aspect.*/if ( hasAll ) { for ( int i = allSet.nextSetBit( 0 ); i >= 0; i = allSet.nextSetBit( i + 1 ) ) { if ( componentBits.get( i ) ) { // Entity system is still interested, continue checking. continue; } //Aspect is not interested. return false; }}//Aspect is interested.return true;
[font=arial]So ugly! That "nextSetBit" call isn't much prettier either it has an inner loop, a bunch of other checks, and it's done for all the components in the Aspect.[/font]
[font=arial]I decided to take HPPC's route and try to retarget a popular bit set implementation to my purposes. Apache Lucene project has a bunch of pretty general purpose utility libs in their sources, one of them is OpenBitSet, a bit set implementation that exposes the backing long array and also has a bunch of union and intersection tests that don't mutate the bit set's state, perfect![/font]
[font=arial]Some refactoring was needed to reduce dependencies on other classes and was just left with BitUtils and OpenBitSet. Also removed most of the functionality that basically allowed you to have big ass bit sets using OpenBitSet. I don't need a 16Gb bit set, so plain 'int' indices instead of 'long' indices are fine for dustArtemis.[/font]
[font=arial]Now see the new implementation:[/font]
/** Check if the entity possesses ALL of the components defined in the* aspect.*/if ( hasAll ) { final OpenBitSet all = allSet; /* * Intersection bit count between allSet and cmpBits should be same * if Entity possesses all the components. Otherwise Aspect isn't * interested. */ return all.cardinality() == OpenBitSet.intersectionCount( all, cmpBits );}
[font=arial]So pretty! Two very simple loops are run, one for 'cardinality' call and one for 'intersectionCount', both use Long.bitCount which are very fast JVM intrinsic methods. And no mutated state at all, allSet and cmpBits are kept as they are.[/font]
[font=arial]
General optimizations
[/font][font=arial]There are a bunch of little tweaks here and there. Like for example, all entities are created through EntityManager. But EntityManager was notified of when an Entity was added like any other system/manager. Which meant that when the entityManager.added(entity) method was called, inside there was a check if the manager could hold the entity, otherwise grow the backing array of entities, copy everything, then add the entity to the manager. Totally unneeded![/font]
[font=arial]Now 'ensureCapacity' is called for the entity Bag when an entity is created, so the Bag can hold the Entity when its inevitably Incorporated into the manager. No more size checks.[/font]
[font=arial]There are quite a few places when this idiom of "ensureCapacity" first, then do operations, can save up a few checks down the road. Nothing groundbreaking but can simplify code quite a bit in some places.[/font]
[font=arial]Also, all EntityObservers (ie, managers, systems), had these "added(entity)" or "removed(entity)" which were essentially events. When an entity was added or removed from the world, those methods were called on all systems/managers to see if they had to add/remove an entity. They get notified of any change in the World instance like that.[/font]
[font=arial]Now, say that you added 100 entities. For all entity systems and managers, you'd issue an 'added' call, for each entity you added. Say that you have 5 managers and 20 systems. That's 2500 'added' calls. In itself this isn't an issue, but it lands on a very special place for the JIT. Those are all megamorphic calls. Those are 25 different implementations of the 'added' method, so there is no way for the JIT to not to make them go through a vtable.[/font]
[font=arial]This was a very silly thing really. There are Bag of entities for all these "events". 'added' entities get pushed to 'added' Bag, 'removed' entities get pushed to 'removed' Bag, and so on. These all reside on the World instance. Whats preventing the World instance from simply passing down the Bag to the EntityObservers? Absolutely nothing. So now World just passes the 'added' Bag to the EntityObservers and they do whatever they want to do with it inside that call.[/font]
private final void notifyObservers ( final Bag observers ) { final int size = observers.size(); final T[] obs = observers.data(); // Call all the event methods on all observers. // added, change, disabled, etc, are all Bags containing entities. for ( int i = 0; i < size; ++i ) { final T o = obs; // Only one megamorphic call per event. o.added( added ); o.changed( changed ); o.disabled( disabled ); o.enabled( enabled ); o.deleted( deleted ); } }
[font=arial]For our example case from before, instead of 2500 'added(entity)' calls, you'd only have 25 calls to 'added(addedEntities)'. Much better![/font]
[font=arial]
And that's all for now...
[/font][font=arial]You can always check the sources out from dustArtemis repository, I try to comment all the commits so you can find short descriptions of all changes in the commit list. Cya![/font]
I should down vote for lack of puppies :/