EASTL

EASTL copied to clipboard

after reading about the facebook-vector-replacement it came to my attention that eastl also uses a growth factor of 2 which is a bad choice (https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md) for memory allocators. can/should the growth-factor be a template-parameter (so easily tunable) or hard changed to for example 1.5?

the relevant section from above is: The initial HP implementation by Stepanov used a growth factor of 2; i.e., whenever you'd push_back into a vector without there being room, it would double the current capacity. This was not a good choice: it can be mathematically proven that a growth factor of 2 is rigorously the worst possible because it never allows the vector to reuse any of its previously-allocated memory. Despite other compilers reducing the growth factor to 1.5, gcc has staunchly maintained its factor of 2. This makes std::vector cache- unfriendly and memory manager unfriendly.

This is a really good point. clang and gcc are still on 2x while MSVC is doing something else (not 1.5).

My opinion is that this should be tunable through config.h or some similar location rather than adding another template parameter. I'd prefer that EASTL generally follow the C++ standard as much as possible with changes being purely additive (e.g. the fixed and intrusive containers or functions like erase_unsorted()) without a really good reason. Furthermore, I don't see any real use-case for having it be tunable per-instance. Much better to have a place to globally tune it. I'm also fine with just shifting it to 1.5.

Some more explanations about the growth-factor: https://blog.demofox.org/2016/05/18/who-cares-about-dynamic-array-growth-strategies/ this article concludes "the ideal factor to use when upsizing a buffer in general (when worrying about fragmentation like this), is the golden ratio 1.618"