6 ms·
> 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 s
by 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
- jltsiren 3y agoThat 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.
- anonymoushn 3y agoI see, thanks for your patience :)
- ace2358 3y agoGreat thread, I was scratching me head a bit too.
- kevinventullo 3y agoIt’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-not-use-a-2p-size-hash-table-when-using-the-division-method-as-a https://cs.stackexchange.com/questions/19020/why-should-one-...
- pjscott 3y agoLLVM'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.)
- bluGill 3y agoThey may also know something about the memory allocator.
- rerdavies 3y agoBetter L1/L2 cache performance, perhaps?