Use of appropriate data structures and custom allocators

[endragor]

Bevy currently uses the stdlib's Vec and HashMap types everywhere, but they are not a great fit for a realtime system that a game engine is. The main problems are:

1. While they provide O(1) amortized complexity, worst-case is O(n). So while most pushes to a Vec are very cheap, the Nth will be expensive (allocation + copy of the current contents). When the array contains a large number of elements, this will result in a significant increase of the frame time compared to average, and most likely a noticeable hiccup for the player. This is why, in general, game engines should optimize for worse-case complexity: avoiding hiccups is important, worst-case frame time should be predictable and fit into the target boundary (usually 16 or 33 ms).
   This is a good illustration of the problem:

2. The std collections do not support custom allocators. Again, worse-case performance is important for game engines and the default allocators (jemalloc included) have N-dependent worst-case complexity. Even when using upper-bound allocators, such as TLSF, you may perform up to about 200 instructions and some amount of uncached memory reads, where a couple of instructions would be enough (increasing a pointer with a scratch allocator). A very common use case in ECS is to allocate something that is only necessary for the current system run. Scratch allocator is a great fit here that is super cheap.

The solution to these problems would be to implement custom data structures and allocators, perhaps a bevy_std create, that would be used throughout the engine. In general, more thought should be put into use of data structures in every part of the engine, so that the best fit for the job are used.

Our Machinery's blog can be a great source of inspiration, as they are also implementing a data-oriented game engine with a lot of thought put into the fundamental aspects of it, including the use of data structures.

If @cart agrees this should be implemented, it's better be done earlier, as more work will be necessary in the future to refactor existing crates to use appropriate data structures.

[pickfire]

The std collections do not support custom allocators.

Yet, the team is still working on it. rust-lang/wg-allocators#7

[cart]

I agree with the premise, and I also trust the judgement of the Our Machinery folks. However building these data-structures won't be my personal immediate short (or likely medium) term priority. Theres just too much other groundwork to lay down. The interfaces should probably be drop-in replacements for std types (or close to that), so the cost of adopting them later should be low.

bevy_utils is probably the place we'd put them. We currently put specialized versions of HashMap/HashSet there with non-default hashing algorithms.

If anyone wants to pick up this work, I'll happily weigh in / do code reviews. But if nobody wants to pick it up, it will likely be months before I get to it.

[caelunshun]

Given that custom allocator support in std is moving forward (rust-lang/rust#77187, rust-lang/rust#78461)—is there still a reason to implement these in Bevy? Once feature(allocator_api) stabilizes, it would suffice to add type aliases in bevy-utils for collections based on bump/scratch allocators, as is done for hashing right now.

[cart]

Yeah I agree with that, provided those features stabilize in a reasonable time frame. Ex: there's lots of cool stuff we could do with specialization, but it could be years before that's actually possible on stable. In the meantime we've implemented alternative designs so people can do stuff now.

[pickfire]

One way I can think that would be better if bevy is working on it, it would be good to be aware of the differences made and maybe even contribute back to rust so the whole rust ecosystem can benefit from it, it could even boost the development speed, maybe those interested might want to ping in the issue comment, I believe @TimDiekmann is one of them working on it.

[TimDiekmann]

Thanks for the ping!

Yes, I am currently working in my spare time to add custom allocators to the std-collections. Vec should have landed upstream already, but at the moment I get an error at LLDB that I can't reproduce locally and so I'm still waiting for some help (if someone can help, that would be great!).
Box and Vec both took a bit longer than expected, further implementations like HashMap or String (probably the most important data structures for a game engine besides Box and Vec) should be pretty simple. String is a simple wrapper around Vec and HashMap already has allocator support in hashbrown. There I am preparing a pull request to get rid of the Clone-bound, then I will try to merge HashMap with allocator support into the std-library.

I would be happy if in bevy the Vec implementation is changed, this will be put back into the std-library, so that everyone can benefit from it. Even if there are changes upstream, this engine has an advantage. Also I think it's very hard to get the same performance in downstream crates because the std-library makes heavy use of nightly features and/or compiler magic to get rid of unnecessary allocations (__rust_alloc isn't even guaranteed to be called and may be optimized out, even if it has side effects).

Once feature(allocator_api) stabilizes, it would suffice to add type aliases in bevy-utils for collections based on bump/scratch allocators

I think the allocator_api-feature could be splitted once the AllocRef trait is finalized, but, yes, this will probably take a while. Also we are planing on deprecating GlobalAlloc in favor of AllocRef (or Allocator).

Even though I hadn't the time to update it, alloc-compose is a crate worth looking at I think (It's currently using the "old" AllocRef trait and isn't compatible with recent nightly builds).

[TimDiekmann]

Update: rust-lang/rust#78461 has landed! 🙂

[joshuajbouw]

Can't this just be solved with ensuring that the correct about of capacity is allocated to prevent memory re-allocations? Then trimming down to size to free up memory, etc.

[cart]

That only works when you know exactly how much memory you need ahead of time. Games are often "dynamic" with unpredictable memory usage.