Interestingly, the C++ standard doesn't specify a cost for this, or an implementation. So there could be some C++ implementation out there somewhere that just copies the whole string on each append.
This is in contrast to std::vector, where the cost of adding one element to the end _is_ specified to be amortized O(1).
No, but there was an unreasonable one. Microsoft Foundation Classes, which preceded the STL. Originally, Their CString class extended the capacity in such a way that appending one character at a time had quadratic cost.
1. Both std::vector<T> and std::basic_string<T> support push_back(T) with amortized constant performance.
2. Additionally, std::basic_string<T> has an operator+=(T) that behaves semantically identical to push_back(T), but does not have a complexity requirement imposed by the standard.
Logically that leads to every reasonable standard library implementation to simply dispatch std::basic_string<T>::operator+=(T) to std::basic_string<T>::push_back(T) (or vice versa, of course) and have both operations run in amortized constant time.
You're technically correct that the standard theoretically allows push_back(T) and operator+=(T) to have different time complexities, so you could make operator+=(T) run in linear time if you're trolling (but in that case, why stop at O(N) and not make it O(2^N) or something?), but since push_back(T) and +=(T) need to be equivalent and the former needs to run in O(1) amortized time, there is no reason to make the latter perform worse than the former.
> Interestingly, the C++ standard doesn't specify a cost for this, or an implementation.
Table 76 (page 797-798 of the C++20 draft [0]; page numbers read 789-790) specifies the sequence operations on containers that shall take amortized constant time. Among these includes push_back() for basic_string.
With an allocation of size n, you have capacity for n-1 characters and the trailing 0, and the trailing 0 does not count as a character. If you double the size of the allocation to 2n, the capacity increases to 2(n-1) + 1.
That is the new allocation size. The new capacity is one character less. The allocation must include space for the trailing 0, which is not a part of the string and is hence not included in the length/capacity numbers.
LLVM's libc++ doesn't use a generic growable vector thing for std::string; they rolled their own, specifically for strings. (I checked the source. Alas, no explanatory comments and nothing in the "initial libc++ import" git commit message.)
Google has proposed adding precise growth to std::string on with the benefit that it saves quite a bit of memory and time you the string isn't being repeatedly appended. However, the project rejected the idea.
Google also proposed uninitialized resize, and the ability to treat string as if it were unique_ptr, by just giving it some already-allocated buffer. You can tell they use these internally because the fingerprints of these features are all over the protocol buffers open source libraries. I believe none of them have been adopted by the standard.
Reserve sets the capacity, not the size. If you were to reserve and overwrite the buffer, the size is still wrong. Now if you resize, STL overwrites your contents with value initialized chars.
i think you may have misunderstood the standard - data() will always return a valid pointer, but the pointer returned may be invalidated by any number of functions:
string s;
s.reserve(50);
char * p = s.data(); // ok so far
s.reserve(100); // now p may be invalid
Of course, you need to call push_back() or insert() to add the data. Actually, insert() wouldn't even require reserve() in the first place.
I guess the idea of uninitialized resize is that you reserve the space, bump the size, and then you can directly set the new members with operator[]. If your input data is not contiguous, and would need to use push_back() otherwise, you can save a few if-checks. But that's pretty much it, I assume.
s.reserve(n);
s.append(....); // a fairly robust set of overloads.
That being said... I completely agree that imprecise resize() is unfortunate, and unexpected. I'm going to have to keep an eye out for how I use resize() going forward. (Not a lot, admittedly).
I've had much grief with this in Rust, adding to an array with "push".
Down at the bottom, this grows by resizing an allocation. Ordinarily, that's cheap. But if you're resizing a reasonably sized array, at least under Wine it's a copy of the array with the lock on the memory allocator set. There's a spinlock involved. If many threads are allocating, futex congestion is possible and speed drops by two orders of magnitude. Ouch.
Surely that must be a specific allocator. Does rust allow you to use say jemalloc or alternatives? Or are you saying this lock is acquired no matter which allocator is used?
Yeah you can override the global allocator pretty easily[1]. But the default uses the system allocator, and I guess it sounds like Wine's is pretty bad
49 comments
[ 2.7 ms ] story [ 105 ms ] threadInterestingly, the C++ standard doesn't specify a cost for this, or an implementation. So there could be some C++ implementation out there somewhere that just copies the whole string on each append.
This is in contrast to std::vector, where the cost of adding one element to the end _is_ specified to be amortized O(1).
See my comment here for details: https://news.ycombinator.com/item?id=38032949
You're technically correct that the standard theoretically allows push_back(T) and operator+=(T) to have different time complexities, so you could make operator+=(T) run in linear time if you're trolling (but in that case, why stop at O(N) and not make it O(2^N) or something?), but since push_back(T) and +=(T) need to be equivalent and the former needs to run in O(1) amortized time, there is no reason to make the latter perform worse than the former.
Table 76 (page 797-798 of the C++20 draft [0]; page numbers read 789-790) specifies the sequence operations on containers that shall take amortized constant time. Among these includes push_back() for basic_string.
[0] https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/n48...
This was also the case in the C++11 draft, and quite possibly before then as well. (I don't have a copy of the C++03 spec handy)
;-)
That’s interesting, why add one? Is there something to suggest this is better than simply doubling in real world scenarios?
https://cs.stackexchange.com/questions/19020/why-should-one-...
https://reviews.llvm.org/D102727
[0] https://github.com/facebook/folly/blob/3c8829785e3ce86cb821c...
https://github.com/abseil/abseil-cpp/blob/master/absl/string...
The standard adopted it as resize_and_overwrite. Which I think is a little clunky.
What would be the practical difference to std::string::reserve?
I guess the idea of uninitialized resize is that you reserve the space, bump the size, and then you can directly set the new members with operator[]. If your input data is not contiguous, and would need to use push_back() otherwise, you can save a few if-checks. But that's pretty much it, I assume.
Down at the bottom, this grows by resizing an allocation. Ordinarily, that's cheap. But if you're resizing a reasonably sized array, at least under Wine it's a copy of the array with the lock on the memory allocator set. There's a spinlock involved. If many threads are allocating, futex congestion is possible and speed drops by two orders of magnitude. Ouch.
The effect was that a game-type program dropped from 60FPS to 0.5 FPS.
[1]: https://doc.rust-lang.org/std/alloc/index.html#the-global_al...
Bug report: [1]
[1] https://bugs.winehq.org/show_bug.cgi?id=54979
It's only not used when shift by 1 was so much cheaper than float mult.
llvm's libc++ uses this grow logic instead:
which is actually closer to the metal, allocating a new page when needed.