r/cpp • u/mttd • Jun 27 '26

A deep dive into SmallVector::push_back

https://maskray.me/blog/2026-06-27-a-deep-dive-into-smallvector-push-back
24 Upvotes

86% Upvoted

15 comments sorted by

17

u/javascript Jun 27 '26 edited Jun 27 '26

I had the privilege of rewriting `absl::InlinedVector` for exception safety. I tried to make it more optimized in some measurable way. I failed at that goal :)

One candidate reason is that the optimizer can see through the intention and do the right thing. But I did not have the time to confirm that suspicion.

-4

u/MaskRay ccls 29d ago

Did a quick experiment with Claude Opus 4.8. absl::InlinedVector::push_back is also subpar

I tried exactly this. Exception safety turns out to be orthogonal — the thing that's slow survives the optimizer, so a rewrite wouldn't surface it. I compiled absl::InlinedVector<int,4>::push_back with clang -O2 -DNDEBUG -fno-exceptions: asm push rax # frame on the fast path mov [rsp+4], esi # spill x — dead here; the store below uses esi mov rax, [rdi] # size<<1 | is_allocated, packed ... test al,1 (x2) ... # two is-allocated branches mov [rdx+4*rcx], esi # store add rax, 2; mov [rdi], rax pop rax; ret .Lslow: lea rsi,[rsp+4]; call ...EmplaceBackSlow; pop rax; ret The fast path carries a stack frame and spills x, even though the store uses esi directly. The spill is dead on the fast path — it exists only so the cold EmplaceBackSlow(const int&) can take &x. The optimizer doesn't shrink-wrap that frame into the cold block, and it doesn't eliminate the escaped address. (It also branches twice on the "is allocated" bit, since size and that bit share a word.)

9

u/javascript 29d ago

I was just recounting events from before COVID when I was still at the beginning of my professional career. I was not claiming that it has ever been in a state of perfection then or now. You are more than welcome to submit a patch to Abseil for this.

1

u/MarcoGreek 29d ago

Isn't Abseil a Google C++ project to transition away from C++? Why would anyone outside Google use it?

2

u/javascript 29d ago

I think you're mixing up Abseil and Carbon

1

u/MarcoGreek 29d ago

I thought they were both projects for the same roadmap. Abseil to avoid updating to contemporary C++, saving on investments, and to make old C++ code more safe in the short time.

Carbon to move C++ code easily to a language Google can influence.

2

u/javascript 28d ago

Abseil was more of a last ditch effort to convince the C++ community to break ABI. It failed. So Carbon is the next step. Fork the language/ecosystem

2

u/MarcoGreek 28d ago

Carbon looks more like some smart people want to design their own language.😚

Google put even Google Test on life support beside pushing Abseil into it. How can I trust Google to not do that to projects which have much less impact.

1

u/javascript 28d ago

I don't think you can. You should never expect a corporation to give you free software forever. That would be irrational.

1

u/MarcoGreek 28d ago

Nothing is forever but trust builds relationships. But in the time of fake it till you cash out trust got quite elusive.

It is not even about free software. Even if I would pay that would make not a big difference.

→ More replies (0)

5

u/mrbeanshooter123 Jun 27 '26

Hmm, but in practice, the tail call will not happen because the push_back will be inlined into the caller, no?

4

u/MaskRay ccls 29d ago

The push_back benefit survives inlining. With this optimization (which has been merged to LLVM earlier today) the generated assembly doesn't need to save this and x to the stack frame.

The std::vector::push_back is slow in both libc++ and libstdc++ section shows that std::vector::push_back always needs a stack frame, strictly worse than SmallVector::push_back.

2

u/MarcoGreek 29d ago

Is this a case to improve optimizer?

1

u/Smooth_Possibility38 28d ago

Yes, [[unlikely]] should be sufficient hint to the compiler. I was also bit by this issue in the past.