6 ms·
Appending to an std:string character-by-character: how does the capacity grow?
- pacaro 3y agoThis is, of course, the same mechanism that allows appending to an ArrayList in Java to be O (1), or at least amortized too such
- kadoban 3y agoEdit: the following is wrong, sorry about that. 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).
- foota 3y agoAre there reasonable string implementations lacking 0(1) amortized append runtime?
- deleted 3y ago[deleted]
- sltkr 3y agoNo, because appending with push_back() which strings must also support is required to have O(1) amortized time. See my comment here for details: https://news.ycombinator.com/item?id=38032949 https://news.ycombinator.com/item?id=38032949
- not2b 3y agoNo, 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.
- rurban 3y agoIt was just using the naive approach (grow by the exact size), the same idea as Google is now proposing. https://news.ycombinator.com/item?id=38033206 https://news.ycombinator.com/item?id=38033206
- sltkr 3y agoThe C++ standard requires: 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.
- lmm 3y agoMight an implementor use a specialised implementation for operator+= that performs better for practical-sized strings while not being O(1)?
- vitus 3y ago> 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. [0] https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/n4849.pdf 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)
- kadoban 3y agoWoops, thanks. Not sure how I missed that.
- AnimalMuppet 3y agoYeah. It was only on page 797! How could you miss that? ;-)
- deleted 3y ago[deleted]
- Permit 3y ago> Under macOS (LLVM 15), I get that clang doubles the capacity and add one That’s interesting, why add one? Is there something to suggest this is better than simply doubling in real world scenarios?
- akomtu 3y agoThe trailing 0 char?
- tedunangst 3y agoIn theory, it should be (len - 1) x 2 + 1 in that case.
- jltsiren 3y agoWith 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.
- tedunangst 3y agoSo why does it increase the size of the allocation to 2n + 1?
- jltsiren 3y agoAllocation size is capacity + 1. If you double the allocation size to 2 * (capacity + 1), the new capacity is 2 * capacity + 1.
- anonymoushn 3y agoSurely 2 * (capacity + 1) = 2 * capacity + 2
- smoothc 3y agoThere’s also [small string optimization](https://stackoverflow.com/questions/10315041/meaning-of-acronym-sso-in-the-context-of-stdstring/10319672#10319672 https://stackoverflow.com/questions/10315041/meaning-of-acro...)
- compiler-guy 3y agoGoogle 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. https://reviews.llvm.org/D102727 https://reviews.llvm.org/D102727
- jeffbee 3y agoGoogle 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.
- terrelln 3y agofolly provides functions to resize std::string & std::vector without initialization [0]. [0] https://github.com/facebook/folly/blob/3c8829785e3ce86cb821cc87853cfd2b823c6a13/folly/memory/UninitializedMemoryHacks.h#L49-L51 https://github.com/facebook/folly/blob/3c8829785e3ce86cb821c...
- jeffbee 3y agoYeah, it's nice! And Abseil does it, IFF you use LLVM libc++. https://github.com/abseil/abseil-cpp/blob/master/absl/strings/internal/resize_uninitialized.h 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.
- spacechild1 3y ago> Google also proposed uninitialized resize What would be the practical difference to std::string::reserve?
- jeffbee 3y agoReserve 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.
- zabzonk 3y agoit is possible that the compiler has simply elided all that loop.
- Animats 3y agoI'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.
- nynx 3y agoThat’s a bug in the allocator. Realloc should not grab a lock the entire time.
- Animats 3y agoIt's complicated. There are three nested locks. I could see snapshots of what was happening in gdb, but don't fully understand the dynamics. The effect was that a game-type program dropped from 60FPS to 0.5 FPS.
- hawk_ 3y agoSurely 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?
- connicpu 3y agoYeah 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 [1]: https://doc.rust-lang.org/std/alloc/index.html#the-global_allocator-attribute https://doc.rust-lang.org/std/alloc/index.html#the-global_al...
- Animats 3y agoIt's in the DLL that Wine uses to emulate Windows. Not in the Rust library. Bug report: [1] [1] https://bugs.winehq.org/show_bug.cgi?id=54979 https://bugs.winehq.org/show_bug.cgi?id=54979
- rurban 3y agoWonder why he didn't mention the correct growth factor for the geometric series, the golden ratio 1.618f. It's only not used when shift by 1 was so much cheaper than float mult. llvm's libc++ uses this grow logic instead: if (actual > 30) actual = ((actual & ~15) == actual) ? (actual + 15) : ((actual + 15) & ~15) - 1; which is actually closer to the metal, allocating a new page when needed.