Just to retroactively invalidate my previous statement, I've found that GCC 8 and MSVC don't have the same 10% performance detriment as GCC9. I'm in the middle of doing more cross-compiler testing to be thorough on this. I suspect that the 2% performance difference is likely to hold true, but will have to see. I would be interested to know what sort of % performance threshold people would tolerate in order to have a working reserve function.
In the meantime I do one other question for people:
If we allow unused empty memory blocks (which is what reserve ensures), that means we can retain memory blocks when all elements in them are erased, rather than deallocating the blocks. This has numerous potential performance advantages, for example if you have filled all element memory blocks and then insert a new element, a new memory block will be created. If that element is subsequently erased and then another inserted, on repeat, without retaining the memory block you would end up deallocating and reallocating a memory block repeatedly.
However it also throws up a lot of implementation-defined decision-making as to the capacity of memory blocks which will be retained. For example, we would almost always want to retain the back block as this will be the largest - and similarly we might want to retain any other blocks which are at the maximum memory block size. But if there's twenty memory blocks, and the front memory block gets all it's elements erased, we wouldn't want to retain it, as it's capacity would be small, which leads to worse cache locality. Re-using that block would be a detriment to performance.
Also, retaining erased memory blocks leads to a vector-like scenario where the user can have a lot of unused memory after erasures, until a shrink-to-fit is called (I just remembered from the june talk that we established that shrink-to-fit would be a non-element-reallocating "free unused blocks" function much like std::deque, in this case). This has the advantage of allowing the user to move a lot of deallocation to non-hot-loop areas, but how much deallocation would occur in the hot loops themselves would be dependent on the implementation as mentioned in the previous paragraph.
Are either of these two aspects problematic, if we retain reserve?
Now, replying to Ben:
I believe your results, but I'm trying to understand the "why" a bit better. Does the addition of reserve() have knock-on effects on the rest of the design of the container? Perhaps because it makes prior, simple invariants more complicated?
It introduces new code and branches into all the various insert/emplace/erase/splice functions, and of course there are minor changes to constructors/swap/etc as well, to re-use or retain empty memory blocks. As above, I need to do more vigorous cross-compiler testing to establish the true effect of this - to find out whether what I've seen with GCC9 is merely a bug in it's optimization.
How does the container differ in the following cases:
* Reservable design: Start empty, reserve(512) elements, insert 100 elements
* Non-reservable design: Start empty, insert 512 elements, erase 412 elements
* Reservable design: Start empty, insert 100 elements
* Non-reservable design: Start empty, insert 100 elements
Basically as-noted, extra code and branching occuring. In case you're interested, I've attached the before (reserve can only allocate one block) and after (incomplete, reserve can allocate many blocks, erase can retain memory blocks) variants to this email, may not be worth investigating further until I've completed my investigation however.