Friday, March 26, 2010

Game Logic IX : Generic Optimisations

While thinking about how to do general optimisations on this data-oriented stuff, like good sorted views on tables and fast set existence checks, something that struck me was that I've been used to using a non standard container for a very long time that helps with both of these operations.

Judy arrays have been around a long time, and I remember at the time I first found them, I thought they were magical and cool. Now, they're looking even more useful as they offer a very fast sorted insert operation. They can also be optimised to return early from existence checks. I'm not sure I'd like to try and make a branchless version of it, but there are many places where the version of Judy arrays that I implemented could be made branch free, without any degradation of performance on out of order processors. Judy arrays were designed to mostly allocate 16 byte lumps, or regular multiples of. This on it's own is probably worth caring about for the sake of the cache line size.

Judy arrays are really worth reading up on. So go do it.

The other thing I thought of when talking about existence based behaviour was that sometimes you wanted to be able to check if an implicit entity existed through their components. This is quite easy on a sorted container, but what about an unsorted container? Do you have to run through all the elements to find out if a certain one exists? Well, no, not all the time. A certain Mr Bloom invented a very clever use of a bit field and a hash function. The Bloom filter lets you check to see if an entry exists. It sometimes returns false positives, but the bloom filter operation is so quick and so lacking in memory usage that it's a really good trade off to run it quick, then do a make sure afterwards.

Judy Arrays
Bloom Filters

And so you now have some generic optimisations for your row-oriented development.

1 comment:

Ethics said...

Judy Arrays were designed to be cache cohesive out of the bag, so you shouldn't need to worry overly about taking branches out. This might also be interesting (you probably read it years ago) The test system isn't especially appropriate for testing heavy cache work, which I think may be how the hash keeps up. on an spu I imagine it's a very different story. If you could beat a judy this easily, it wouldn't have been worth the development of a very complex data container.