• entries
11
17
• views
27869

# Entities and tracking their components

2099 views

[font=arial]In this update I'll talk about the latest feature of dustArtemis, fixed length bit sets for component tracking![/font]

# [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]Component-Entity relationship[/font]

[font=arial]dustArtemis still uses original Artemis way of dealing with the relationship between entities and components. Each entity contains a bit set, and each Component type has an index. When an Entity contains a component, its type index is set in the component bit set of said Entity. [/font]

[font=arial]For example, say that Position component index is 3, so the third bit in all entities that have a Position component will be "turned on". Highest index you will ever use will amount to how many different component types you have. If you have 30 different component types, only the first 30 bits of these bit sets will ever be used. Of course, of each of these component types you can instance as many as you need since arrays of components are unbounded.[/font]

[font=arial]This works very well because its a compact way of handling which entity has which component. Its also very practical for detecting when an EntitySystem is interested in an Entity. EntitySystem uses an Aspect as matcher for component bit sets in Entities, if the bit set compares favorably to the bit sets of the Aspect, EntitySystem adds the Entity to its 'actives' Entity list.[/font]

[font=arial]These comparisons are quite fast, albeit making the logic of handling each Entity insertion/removal a bit branchey. In dustArtemis I left this part a bit up to the JVM. Insertion/removal checking its done with 2 bit flags and a switch block. HotSpot can profile them in runtime and decide if it will use a jump-table, a series of comparisons, and in which order they'll be made given which is the one most likely to be taken.[/font]

# [font=arial]Enter OpenBitSet[/font]

[font=arial]Original Artemis used JDK's standard BitSet class. This imposed a few restrictions. For example, you weren't able to retrieve the backing 'long' array of the BitSet for easy iteration. Most operations modified the bit set used, ie, you couldn't do AND/OR checks along the bits of an array and 'break' on some conditions, but you had to use a temporary BitSet, copy the contents of one BitSet to it, AND/OR it with the other BitSet, then check the results.[/font]

[font=arial]I decided to take HPPC's route (a "primitive collections" library) and fork Apache Lucene's bit set, OpenBitSet (that's why there is now an org.apache package in dustArtemis sources).[/font]

[font=arial]OpenBitSet provided many operations that didn't modified the bit set, and exposed the backing 'long' array if you wanted to use it directly. It was designed for very, very big sets (ie, using 'long' to index bits for example), so I trimmed down its implementation to make it more compact.[/font]

[font=arial]This was quite cool because now I could implement a simple iterator over the backing arrays directly (used, for example, to keep track of active entities in a system) and use non-mutating operations in Aspect checks.[/font]

# [font=arial]Now the downsides...[/font]

[font=arial]While this was great for the few places where big bit sets were used, but it wasn't quite nice for Entity's component bit sets.[/font]

[font=arial]How many different kinds of components will you have? 20? 50? 100? Say that you have between 64 and 128 components, that means that you need 128 bit long bit sets, ie 2 longs, 16 bytes.[/font]

[font=arial]If your idealized cost of tracking what component types an Entity has should be 16 bytes (per Entity instance), how does practical usage measures up having in mind Java's lack of value types? [/font]

# What the government doesn't wants you to know about JVM's costs

[font=arial]Have in mind we're using a 64 bit JVM here as reference, and that the JVM does 8 byte alignment regardless of architecture.[/font]

[font=arial]Cost for an OpenBitSet instance is:[/font]

• [font=arial]12 bytes for object header.[/font]
• [font=arial]4 bytes for "int wlen" field.[/font]
• [font=arial]8 bytes for "long[] bits" reference.[/font]

[font=arial]24 bytes for an OpenBitSet instance.[/font]

[font=arial]Now, we have to measure that "long[] bits" field since its another whole object![/font]

• [font=arial]12 bytes for object header.[/font]
• [font=arial]4 bytes for standard "int length" field of arrays.[/font]
• [font=arial]16 bytes for our 'long' data (8 bytes per 'long' * 2 'long's we're using for this example).[/font]

[font=arial]That's 32 bytes.[/font]

[font=arial]32 bytes + 24 = 56 bytes in total f[/font][font=arial]or an OpenBitSet instance compared to the [/font]16 bytes of data we actually want. Nevermind the additional indirection[font=arial] of fetching the 'bits' array instance from the bit set instance.[/font]

# [font=arial]Enter FixedBitSet[/font]

[font=arial]This is an experimental implementation of these, so they might not be the best possible course of action to fix this issue, but its a start![/font]

[font=arial]You got 4 types of FixedBitSet, for 64 bits, for 128 bits, for 192 bits and 256 bits. Obviously you're nuts if you have more than 256 component types.[/font]

The inheritance order is:

1. FixedBitSet
2. FixedBitSet64
3. FixedBitSet128
4. FixedBitSet192
5. FixedBitSet256.

Each inherits the implementations of the previous one ('cept for FixedBitSet since its mostly abstract, so there isn't much to inherit), and only has to add the methods that deal with the newer longer bit set (ie, no need to implement ANDing between two 64 bit sets in FixedBitSet128 since FixedBitSet64 already implements it).

[font=arial]Now, based on the cool implementation of OpenBitSet, we can do a lil' bit better by implementing fixed length bit sets. There are two places where we use small bit sets: Entity instances and Aspect instances, they're both used for tracking component indices.[/font]

[font=arial]Issue is, these bit sets are created without external help. You shouldn't know the bit sets exist at all. So we need a little bit of help of DAConstants here. Instead of having this "APPROX_COMPONENT_TYPES" constant, you'll have to provide an actual accurate count of component types, which will be loaded to an static constant that will be used through dustArtemis to decide what exact size of bit set to use.[/font]

[font=arial]Inside the framework, the problem still exists. Everywhere except when they're initialized, code can't know if its dealing with FixedBitSet64 or FixedBitSet256, we only know we're using a FixedBitSet that has a common set of operations (pop count, and, or, andNot, etc).[/font]

[font=arial]This is essentially a problem that multiple dispatch could solve, this:[/font]FixedBitSet a = new FixedBitSet64();FixedBitSet b = new FixedBitSet192();a.and(b)
[font=arial]Should only AND 'word0' of both bit sets, which is essentially an "FixedBitSet64#and(FixedBitSet64)" call. But how does 'a' knows that the FixedBitSet 'b' is of type FixedBitSet192? Short answer is: It doesn't. Java uses single dispatch, so it can't know what method to call based on the runtime type of the passed parameter.[/font]

[font=arial]A reasonable middle end is that we know for a fact that there won't be different types of FixedBitSets, if you specify that you will use 64 or less component types, there will only be FixedBitSet64 instances in the framework.[/font]

[font=arial]So this implementation becomes reasonable:[/font]public void and ( FixedBitSet bits ) { this.and( (FixedBitSet64) bits ); // Calls 64 bit long implementation.}
[font=arial]And overriding 'and' in each subclass of FixedBitSet so it does the cast to its own type.[/font]

[font=arial]Obvious issue here is that if you do that call passing a smaller bitset than the bitset you're ANDing, you get an exception. (ie, ANDing a 128 bit set with a 64 bit set, tries to cast it to 128 bit implementation and BAM, ClassCastException).[/font]

[font=arial]So instead I decided to do some indirection to get around the issue. In paper its a combinatory explosion, but its lessened by the fact that each bit set is an extension of the previous one, so you don't need to do both 64 bit set 'OR' 128 bit set, and vice versa implementations. Just one side is enough.[/font]// Inside FixedBitSet64.public void and ( FixedBitSet bits ) { bits.andThis(this); // We know 'this' is FixedBitSet64 but not 'bits' type.}// Now inside FixedBitSet128.public void andThis ( FixedBitSet64 bits ) {/* Here we know 'this' is FixedBitSet128, so the proper FixedBitSet64.and(FixedBitSet128) call is made. */ bits.and(this); }
[font=arial]This transforms a simple call into two layers of indirection but HotSpot knows very well how to inline these, given that we're always using the same subtypes of FixedBitSet everywhere, so it will become a call to the concrete implementation of the 'and' method we want.[/font]

# [font=arial]Yeah, and what did we gain from this again?[/font]

[font=arial]First and foremost, spaaaaaaace! Remember that an OpenBitSet capable of holding 128 bits had a size of 56 bytes? Lets see how much FixedBitSet128 uses:[/font]

• [font=arial]12 bytes for object header.[/font]
• [font=arial]8 bytes for 'word0'[/font]
• [font=arial]8 bytes for 'word1'[/font]

[font=arial]28 bytes, padded to 32 bytes. That's it. Moreover, the additional 'bits' array pointer indirection? Not a problem anymore.[/font]

[font=arial]FixedBitSet256, biggest one implemented, is 48 bytes, still smaller than the 56 bytes necessary for an OpenBitSet instance of 128 bits.[/font]

[font=arial]Not even mentioning that all operations (AND, OR, pop count, etc) in all FixedBitSets don't even use for-loops anymore since they're all implemented for the given size of the bit set. So there won't be any ugly size checking nor branching in the code that will get executed.[/font]

# [font=arial]What's the catch?[/font]

[font=arial]Hopefully, none at all! The only thing the user has to do is simply putting in their dustArtemis config file how many component types they have (if left unspecified, defaults to 64).[/font]

[font=arial]Well, that's all for this entry, as always you can check out dustArtemis repository, see y'all later![/font]

There are no comments to display.

## Create an account

Register a new account