Query performance optimization

[MioQuispe]

At the moment the speed of querying depends on the amount of entities. As this should be one of the most common operations performed I think it should be optimized. I did a little experiment where I'd store all entities with the same mask in an array which could be accessed by their mask through a hashmap.

var hashMap = {}

hashMap[0] = [] //All entities with mask 0 stored here
hashMap[5] = [] //All entities with mask 5 stored here

...etc

The entities then move around based on their mask. This lets us get a constant query time no matter the amount of entities by simply testing the query mask against each index in the hashmap. Initial tests gave ~5mil queries per second no matter the amount of entities (with hardly any optimizations applied).

var result = []

var entityMasks = Object.keys(hashMap)
for (var index = 0; index < entityMasks.length; index++) {
  var entityMask = entityMasks[index]
  if ((entityMask & mask) === mask) {
    Array.prototype.push.apply(result, this._entityCache[entityMask])
  }
}

The problem is that you'd have to keep track of each entitys index in its hashMap[entityMask] array to remove it from there when its mask changes or it is destroyed. You'd also have to update the indices of the other entities in the mask array which would in turn make any operation that changes the mask of entities slower (the speed would now be determined by the amount of entities with the same mask and the index of the entity that was removed).

Thoughts? Or perhaps other ideas on how to do it? If something was unclear I'll explain it better.

[ooflorent]

v1 was developed this way. The main problem with this approach is if your game adds, removes and modifies a lot of entities, perfs would be horrible. I haven't find an efficient way to implement a similar caching system.

The perf bottleneck comes from result.push. In ES6 we could write:

// entity_manager.js
EntityManager.prototype.query = function *() {
  const mask = this._components.masks(...arguments)

  for (var id = 0; id < this._entityCounter; id++) {
    if (this._entityFlag[id] === ENTITY_ALIVE && (this._entityMask[id] & mask) === mask) {
      yield this._entityInst[id]
    }
  }
}

// my_system.js
update(em) {
  for (let entity of em.query(A, B, C)) {
    // do stuff
  }
}

This would solve all perf issues since no intermediate array would be created.
BUT ES6 is not ready:

• V8 does not optimize generators
• V8 does not really optimize iterators
• Iteration results are not pooled and trigger CheckMaps on access (which is heavy)

If you look closer at benchmarks you will see that numbers are currently pretty good! 300.000 op/s on 1000 entities equals 18.750 frames!

Let's do some quick math:

• 1.000 entities
• 300.000 op/s on query
• 20 calls to query per tick

Equals: 15.000 tick/s
It's more than enough.

If you succeed in implementing a fast, bug free, caching system, I would be happy to merge it! 😉

[MioQuispe]

Interesting! I like the yield idea.
You're absolutely right, for 1000 entities it's perfectly fine.
Problems arise only when the numbers go quite a bit higher (Not sure why I can even care, guess I'm just a performance freak).
I'm currently experimenting with a cyclic array which calculates the new index dynamically based on old index and old array length and the new array length and start index + end index (which change when you delete an entity). If my head doesn't explode before I finish it I'll make sure to send a PR 😄 Hopefully it'll work out.

[MioQuispe]

So I did an initial implementation and the tests are passing, but I'm adding more tests to be absolutely sure it works since it's a very error prone thing.

Initial test results:

100k entities:
2,681 op/s » query on 100,000 entities with 1 component (~50000 matches)
14,559 op/s » query on 100,000 entities with 3 components (~8400 matches)
84,944 op/s » query on 100,000 entities with 10 components (~40 matches)

10k entities:
19,613 op/s » query on 10,000 entities with 1 component (~5000 matches)
51,200 op/s » query on 10,000 entities with 3 components (~840 matches)
93,640 op/s » query on 10,000 entities with 10 components (~4 matches)

1k entities
51,835 op/s » query on 1000 entities with 1 component (500 matches)
68,658 op/s » query on 1000 entities with 3 components (84 matches)
81,470 op/s » query on 1000 entities with 10 components (1 match)

Your current implementation:

100k entities
1,331 op/s » query on 100,000 entities with 1 component (~50000 matches)
3,139 op/s » query on 1000 entities with 3 components (~8400 matches)
4,037 op/s » query on 1000 entities with 10 components (~40 matches)

10k entities
17,453 op/s » query on 1000 entities with 1 component (~5000 matches)
32,848 op/s » query on 1000 entities with 3 components (~840 matches)
40,870 op/s » query on 1000 entities with 10 components (~4 matches)

1k entities
179,097 op/s » query on 1000 entities with 1 component (500 matches)
354,579 op/s » query on 1000 entities with 3 components (84 matches)
392,777 op/s » query on 1000 entities with 10 components (1 match)

Not as good as I had hoped, it's actually slower when dealing with a smaller amount of entities but it scales better and when returning only a few matches the number stays constant independent of the amount of alive entities. Like you said, push is in fact the biggest bottleneck.
I won't make a PR until I'm happy with the numbers though, you can decide then whether it's worth it.

[ooflorent]

If you have a public branch I could drop an eye and suggest some optimizations.

[MioQuispe]

Ok, but let me make sure it works correctly first. I need to test absolutely every scenario because if even one thing is wrong, it won't function correctly.

Just the cache index calculation looks like this (Yeah I know, I will make it readable lol):

EntityManager.prototype._getCacheIndex = function(cache, entity) {
  var index = (cache.arr.length - 1) - ((entity._oldCacheIndex - entity._oldCacheLength) + (entity._oldCacheLength - (cache.arr.length - 1)))
  return (cache.start + index) % cache.arr.length
}

This one is only used when deleting/removing entities from one mask array in the cache to avoid having to loop over each entity.

[MioQuispe]

So I came up with a much much nicer way to do this! It's much simpler too (can't believe I was so stupid not to think of it). I think you'll be happy with the results. I'm currently implementing it, should be ready soon!

[MioQuispe]

Check it out!
https://github.com/MioQuispe/makr/tree/cache

The solution is, instead of using splice to remove entities from each cache, we simply replace the entity with the last element in the cache array. This means we don't have to update any indices since we are just moving it around, leaving other elements unaffected.
Example:
cache array: [e0, e1, e2, e3, e4]
//We now decide to remove e0 from it
cache.pop() //this gets us e4
[e4, e1, e2, e3] //We replace e0 with e4 and update e4s cacheIndex to 0

This gives us a constant time for destroying/removing components/adding components.
Luckily the order of entities returned doesn't matter which makes this possible.

[ooflorent]

Can you make a PR to enable code annotations?

[MioQuispe]

Done #4