Random thoughts on C++ containers: - The major game engines do their own std::vector's, yet it's difficult to find good drop-in std::vector replacements on the web. - As far as I know std::vector can't take advantage of realloc() on trivial types, which seems like an easy win.
6
1
33
- A smart std::vector replacement could use the following info to optimize its auto-grow behavior: The modules/lines it's being called from ("callsite optimization") The element type The current size of the container How aggressively the vector grows (fast vs. slow)
3
0
2
For example, if you see a uint64 vector being created at a certain callsite, and the app always push_back's 256 elements into the container, you can use this history to optimize the container's behavior.

9:21 AM ยท Jan 16, 2021

2
0
2
- A good std::vector communicates deeply with the underlying heap implementation. After allocating a block, the vector should immediately query the heap to get that block's *actual* size so it can exploit that entire block's allocation.
3
0
6
- A vector for large arrays can take advantage of virtual memory to grow blocks one page at a time
1
0
0
- It seems like everybody works on speeding up C++ hash tables, but relatively little effort has been applied to vectors
4
0
13
Replying to @richgel999
I've seen papers applying ~machine learning~ to binning and such for the allocator itself, but not for guessing the base allocation size for an array.
1
0
1
I expect the main difference is that it's very easy to pre-allocate an array when you know you're going to add 256 elements. (and to clear it instead of reallocating every time as well) Allocator interfaces are much less expressive generally.
0
0
1