Hacker News Reader

Comment by Permit | Hacker News Reader

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

View on HN

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

Reply on news.ycombinator.com