News for hackers. Stuff that matters.
Re:Compilers Are (Too) Smart by tialaramex on Sunday June 09, 2024 @06:14AM (#40623352)
I've watched a few talks about the STL containers. I don't think they're savage enough. In particular the C++ growable array type std::vector is often cited as good. Is it terrible? No. But it's still not actually as good as it should be, we can easily do better if we provide the proper API.

Growable arrays are a very popular idea. Your preferred language almost certainly has them, but they might be built in to the language as an optimisation, if "normal" arrays in your language can grow and that's fast enough, chances are you're got the growable array type just as the only array, which is fine (but won't fly on tiny embedded systems).

This type has amortized O(1) aka constant time growth, which is one of those tricks which is amazing if you've never seen it before, then it just seeps into your understanding of the world and so it's easy to imagine why C++ doesn't do any better.

As a necessary optimisation beyond the amortized growth we must be able to tell a growable array hints about its future size. The only hint provided in the C++ STL is reserve, which tells the array its maximum final size. Rust calls this hint Vec::reserve_exact, if our array isn't this big, we should grow immediately, makes sense.

Here's where the problem kicks in: Suppose I don't know the maximum final size, but I do know I need to put say, at least 50 more things in the container? Algorithmically the answer is actually yes, the amortized growth can be preserved if we either grow sooner or skip growth steps and otherwise the hint can be ignored, this is Rust's Vec::reserve

If we try to use the C++ reserve here (aka Vec::reserve_exact) even though this isn't the final size, we destroy our amortized growth performance, our container may have lousy performance. If we just don't bother because we can't express our hint, our container has worse performance than necessary because we grow more often or less optimally.

Re:Compilers Are (Too) Smart by mandarax8 on Sunday June 09, 2024 @07:37AM (#40623743)
Easily solved manually reserving exponentially. All my projects use some variation of this: https://github.com/facebook/folly/blob/9f125c94e10fd01f5567c...

But I've burned myself on this a few times before.

Re:Compilers Are (Too) Smart by jstimpfle on Thursday June 13, 2024 @05:20AM (#40667547)
resize(size() + N), resize(size() - N) should do the trick too, unless default constructing your elements is costly or not defined.

But I wonder what use case there is where you can't just push_back() one by one? The only potential issue here is that there might be a reallocation happening while append this range of N elements, but can't imagine what might break.

Re:Compilers Are (Too) Smart by tialaramex on Thursday June 13, 2024 @09:07AM (#40669176)
It's a perf leak, not a correctness issue, as with std::unordered_map. So yes, you can just push_back() each item, and as with std::unordered_map the worst case is linearly worse than the Right Thing™.

This is a Quality of Implementation issue in the library standard itself.

Re:Compilers Are (Too) Smart by jstimpfle on Friday June 14, 2024 @05:34AM (#40679147)
Ok - if the N elements you want to add would cause more than 1 reallocation by constant size factor, yes I can see that. (also I just saw that resize() has the same allocation behaviour as reserve() has, so scratch my suggestion above).

Never had a problem myself with that though, my main use case for std::vector is with reserve() right at the beginning and never provoking a reallocation (so I often end up coding up my own container to assert reallocation can't happen accidentally).

Sometimes (infrequently) I use the script-style push_back()-only pattern. But I feel very uneasy about uncontrolled reallocations in larger systems, and anyway they constrain the implementation space because of pointer and iterator invaliation.