This is, of course, the same mechanism that allows appending to an ArrayList in Java to be O (1), or at least amortized too such

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).

> 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/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)

Woops, thanks. Not sure how I missed that.

Yeah. It was only on page 797! How could you miss that?

;-)

The 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.

Might an implementor use a specialised implementation for operator+= that performs better for practical-sized strings while not being O(1)?

Are there reasonable string implementations lacking 0(1) amortized append runtime?

No, 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

Depends what you mean by reasonable I suppose. If you just implement it naively, either by growing by 1 or a constant amount each time, it'll be O(n) amortized.

I'd call those potentially reasonable, in that it works and it doesn't break the standard. I probably wouldn't be mad if a student did that impl, but I'd mention it.

I would be surprised if a well-supported, non-toy implementation without strange constraints (eg not for embedded and not trying to optimize solely for size or simplicity or something) did something other than 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.

It 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

> 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?

It’s a stretch, but perhaps this is related to the desire to avoid hash tables which are of size exactly a power of two?

https://cs.stackexchange.com/questions/19020/why-should-one-...

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.)

The trailing 0 char?

In theory, it should be (len - 1) x 2 + 1 in that case.

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.

So why does it increase the size of the allocation to 2n + 1?

Allocation size is capacity + 1. If you double the allocation size to 2 * (capacity + 1), the new capacity is 2 * capacity + 1.

Surely 2 * (capacity + 1) = 2 * capacity + 2

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.

I see, thanks for your patience :)

Great thread, I was scratching me head a bit too.

They may also know something about the memory allocator.

Better L1/L2 cache performance? I'd put good money on that explanation.

There’s also [small string optimization](https://stackoverflow.com/questions/10315041/meaning-of-acro...)

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.

https://reviews.llvm.org/D102727

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.

folly provides functions to resize std::string & std::vector without initialization [0].

[0] https://github.com/facebook/folly/blob/3c8829785e3ce86cb821c...

Yeah, it's nice! And Abseil does it, IFF you use LLVM libc++.

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.

> Google also proposed uninitialized resize

What would be the practical difference to std::string::reserve?

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.

Also I don't think the Standard requires that data() returns a valid pointer after only calling reserve(), so it's technically UB.

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.

Fwiw, they seem to imply (admit) that you can get precise growth using

    s.reserve(n); // precise allocation.
    s.resize(n);  // doesn't grow.

or

    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).

it is possible that the compiler has simply elided all that loop.

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.

That’s a bug in the allocator. Realloc should not grab a lock the entire time.

It'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.

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

[1]: https://doc.rust-lang.org/std/alloc/index.html#the-global_al...

It'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

Nice! Thanks for the link. Also is it the John Nagle who reported this?

Yes.

Wonder 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.