1
\$\begingroup\$

I'm implementing an Entity-Component-System library based on simple dense array approach (using huge arrays for every component field with the size equal to the number of entities, where array[entity] = field value). I also want an index akin to relational databases, i.e. an additional data structure allowing to quickly (in O(1) or at least O(log N)) answer the question "which entity (or entities) has this exact value of this field in this component?" I've implemented it using homebrew open-hashed hashtable, but I'm afraid it is way too unfriendly to CPU cache (since value hashing is pretty much random). What are some options of such data structures which are more cache-friendly?

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Can you clarify when you would be looking up entities by component field value? That seems like an unusual operation for most fields. The ones where I can think of where it would be common - like position - are better addressed with a specialized data structure like a spatial partition. \$\endgroup\$ Commented Aug 12, 2023 at 13:03
  • \$\begingroup\$ Sure, the first two uses that come to mind are parent-child relationships ("parent" field allows every entity to know its parent, but also having an index one could quickly get the list of children for given parent) and yes, position hashing (calculating the tile number from x, y values in position component and storing it in indexed field would allow to quickly get all of the enitites residing in the given map tile). \$\endgroup\$ Commented Aug 12, 2023 at 13:16
  • \$\begingroup\$ Another one would be the name component for entities, having that I'll be able to quickly get the entity # by using human-readable name. \$\endgroup\$ Commented Aug 12, 2023 at 13:18

0

Reset to default

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.