2
\$\begingroup\$

I've had an idea for optimising my ECS engine. Instead of storing components in an array, store components in a hash table as <id> => <component>.

This means that checking whether an entity has a particular component can now be done in O(1) rather than O(n). Just wondering whether there are any drawbacks to this approach?

Since I'm using a managed memory language, cache locality doesn't matter as much.

\$\endgroup\$
6
  • \$\begingroup\$ There's not enough information to answer your question. How many entities will you have? How often will you access them? How often will you add? delete? modify? Also, if you're concerned about cache locality, it is also very important to know what the access pattern will look like... \$\endgroup\$ Commented Apr 25, 2021 at 9:27
  • \$\begingroup\$ @PandaPajama I'm not sure at this point. I was looking for potential pitfalls that I might encounter, nothing particular to my setup. \$\endgroup\$ Commented Apr 25, 2021 at 9:59
  • 1
    \$\begingroup\$ How about you start with what you think makes the most sense, and build from there? Optimizing too early for a very specific use case may end up backfiring -- at best, it will just make your code more difficult to read. \$\endgroup\$ Commented Apr 25, 2021 at 10:07
  • 1
    \$\begingroup\$ That's a risk you take with any choice you make. Since you said you don't know anything about the entities and how they will be accessed, you might have to end up changing the data structure, regardless of which one you chose first. At this point, all data structures are equally valuable, so my suggestion is to optimize for readability instead. \$\endgroup\$ Commented Apr 25, 2021 at 10:15
  • 1
    \$\begingroup\$ It seems like this is a learning project, so even moreso, I think you should optimize for readability, since this is one of thousands of parts that will go into your game engine. As somebody who has written many game engines, I can assure you the first one you write will not be the last -- the things that you learn with this project will give you insights to make these types of decisions earlier in your project. However, if all you want is to hear somebody tell you yes or no, then this site might be able to help with that. \$\endgroup\$ Commented Apr 25, 2021 at 10:19

2 Answers 2

6
\$\begingroup\$

If you want to know what is faster, measure. That is the engineering approach. Thus, write your code in a way that you can swap the implementation (e.g. behind an interface) and benchmark.


With a hash table, the selection of hash function is important. Not only the hash function may have more or less collision, but also it may take more or less time to compute.

We, of course, want a hash function that is fast and has very little collisions. Well, if the input is an integer, using an identity function (a function that just returns the input) as hash function is the fastest, and also does not have collisions.

That is one way to use an array. Just look up the entity id. That is O(1). Very easy to write, very fast code. The issue is that you need to allocate an array with as many entries as entities you may have.

That reminds me. How will the hash table grow? If it uses an array internally, it would have to allocate a new array and move the entries form the old one to the new one. Which is slow, and that is an issue.

We could solve these issues by implementing the hash table over a tree instead of an array. Usually a large branching factor is good for this use. Let us say we are using 32 bits integers for entity ids… We can have a branching factor of 256, meaning that selecting a branch requires 8 bits of the key. Then getting a leaf always takes 4 levels (8 * 4 = 32) of the tree (and yes, that is still O(1), because it does not depend on how many entries are there in the tree nor which one we want, it always 4 levels, that is constant). Or 8 levels and branching factor of 16 (4 bits).

By the way, O(n) can be faster than O(1) for small n. It might make sense to use one strategy for small n, and another large n. So… Benchmark.


Thus yes, use a hash table (which is an array when the hash function is the identity function, and the growing strategy is none). The details of the hash table are what matters. And to reiterate the first paragraph: benchmark.

In fact, other structures are possible. For example self-balancing binary tree (e.g. AVL or Red–black tree) would give you O(log n) performance.


If cache locality were important, what you put in the hash table would not be the component, but the index of the component in an array where they are stored contiguously (instead of wherever the hash function says). So that iterating over the array of components is fast, despite of the hash table. Since cache locality is not important in your case, you can simply put the components in the hash table.

\$\endgroup\$
3
  • \$\begingroup\$ Storing references is a very good idea. I'll use that if I need entities in a quadtree/heap/other data structure \$\endgroup\$ Commented Apr 25, 2021 at 13:34
  • 4
    \$\begingroup\$ As a developer in an unrelated field (but still programming), I've observed that any/all hash implementations are actually worse for use cases where there are a very small number of elements. As you say, the tipping point depends on the hash used, but it's probably going to take at least 6 bits of hash (e.g. at least 64 entries) before it starts gaining speed. One needs to test the results for small lists as well as very large lists to find that tipping point. \$\endgroup\$
    – phyrfox
    Commented Apr 25, 2021 at 14:00
  • \$\begingroup\$ Like I said below, at that point, performance really doesn't matter. It's the big cases that do. \$\endgroup\$ Commented Apr 26, 2021 at 1:16
4
\$\begingroup\$

I'd agree with Panda Pajama's advice:

How about you start with what you think makes the most sense, and build from there? Optimizing too early for a very specific use case may end up backfiring -- at best, it will just make your code more difficult to read.

It seems like this is a learning project, so even moreso, I think you should optimize for readability, since this is one of thousands of parts that will go into your game engine. As somebody who has written many game engines, I can assure you the first one you write will not be the last -- the things that you learn with this project will give you insights to make these types of decisions earlier in your project.

The exact way that components are stored should generally be hidden behind an API like GetComponent / AddComponent / HasComponent / RemoveComponent, so if you decide to change your storage approach later (or profile two options to test how they compare), then you should be able to change just the implementation of those methods, without breaking or modifying any code that relies on them. So you're not making an irrevocable commitment right now - you can (and, based on my experience in gamedev, probably will) change your mind later, no matter what option you pick now.

If that kind of refactoring isn't straightforward in your implementation, then improving your encapsulation might be a better priority to focus on first. Designing for maintainability often pays off in the long term. 😉

That said, from having taught algorithms courses, I'd say you should be wary of the seduction of big-O notation. \$O(1)\$ can still have a substantial constant cost. For hash tables in particular, they tend to take up more space to store the keys and empty slots to keep the load factor under control, they require additional steps to hash the key, wrap it to the size of the table, and compare it to the stored key, and they randomize branch selection and memory access, which can reduce the benefit you get from processor features like caching and speculative execution (and even in a managed language, you can write code that benefits from these).

An ECS will often have just a dozen or fewer components on a single object, or of a single type. At that scale, you might well find a \$O(n)\$ linear probe through an array is just as fast or faster than a hash table, because your \$n\$ is so small.

When in doubt, profile it. Make two versions of AddComponent/GetComponent that you can switch between with a compiler flag, and run the same test scene or the same sequence of millions of component interactions to time whether one is significantly better for your case and usage patterns. That will be measurable proof you can trust far more than the opining of Internet strangers like us. 😉

\$\endgroup\$
6
  • \$\begingroup\$ That's very true. However, by the time the input get so small that big-O notation doesn't matter due to the overhead, performance shouldn't really be an issue anyway. I'll implement some methods for abstraction though, that's what I was missing. Thanks \$\endgroup\$ Commented Apr 25, 2021 at 13:19
  • \$\begingroup\$ Not true, sadly. I've profiled alternative solutions where the approach with the better big-O took seconds longer than an alternative with worse big-O but better cache use and branch consistency. That's a huge, meaningful performance difference. Big-O tells you how the solutions will perform on a theoretical computer when the data is immense. Profiling tells you how the solutions perform on the hardware and data that actually exist. \$\endgroup\$
    – DMGregory
    Commented Apr 25, 2021 at 13:24
  • \$\begingroup\$ You usually have different "n" values. N the number of components on an object versus m number of objects versus k operations per object each tick. One can be small while the others amplify the difference. But also: if you weren't concerned about the performance at your target n values then you wouldn't have asked this question in the first place. 😉 \$\endgroup\$
    – DMGregory
    Commented Apr 25, 2021 at 13:28
  • \$\begingroup\$ @EnderShadow8 what DMGregory says is true. Here is more hearsay from Internet strangers: Sometimes the best option is to have code that checks the capacity you want and if it is small use one strategy, and if it is large use another. \$\endgroup\$
    – Theraot
    Commented Apr 25, 2021 at 13:29
  • \$\begingroup\$ @DMGregory My point is, if n is small then it doesn't matter. If n is big, then the overhead is negligible so the better complexity translates to better performance. Is that true? \$\endgroup\$ Commented Apr 25, 2021 at 13:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .