std::visit produces duplicate code for identical branches

[smeenai]

See https://godbolt.org/z/3436hhhz6 for an example, where we're generating identical copies of the deletion code for each variant type. https://godbolt.org/z/1c7PsGK4P shows that libstdc++ produces a single copy (with nothing else changed), so I assume this is something related to libc++'s implementation of variant and/or visit?

[philnik777]

This could definitely be optimized better by the compiler, but the library could maybe also be improved. Adding clang folks to take a look.

[llvmbot]

@llvm/issue-subscribers-clang-codegen

[smeenai]

Yeah, I wasn't sure if this was more of an optimization issue or a library issue. I filed it under libc++ because Clang is able to produce the expected code with libstdc++'s implementation, but that might not be the best benchmark, since I know libc++ has a strong philosophy of relying on the compiler to optimize things it should be optimizing (and I don't know how libstdc++ handles that).

[davidben]

Reposting analysis from #73699:

(In summary, most other std::visit implementations seem to (almost always) use a switch/case instead of a jump table, which optimizes more easily.)

---

Trying to switch from absl::variant to std::variant in Chromium resulted in a small but non-trivial binary size regression. Poking around, I think the cause is libc++'s std::visit:

libc++'s std::visit seems to be implemented by building a function pointer table and jumping into it. I found this post which suggests this comes from a rather odd requirement where C++ promises an O(1) std::visit, relative to the number of choices in the variant. (Nevermind that this is a compile-time constant, and likely your program will fail to compile before you get too many alternatives to care!)
https://playfulprogramming.blogspot.com/2018/12/when-performance-guarantees-hurts.html

This doesn't optimize well and it seems Clang is unable to inline anything about it. absl::variant inlines fine.
https://godbolt.org/z/9Pehed59z
https://godbolt.org/z/qTKvMYoE7

Likewise, libstdc++ optimizes well:
https://godbolt.org/z/1dnYnb97c
https://godbolt.org/z/4jcaYcvoh

Interestingly, libstdc++ avoids having to worry about the valueless_by_exception state. They seem to try to specialize std::variant to avoid the case whenever possible:
https://gcc.gnu.org/git/?p=gcc.git;a=blob;f=libstdc%2B%2B-v3/include/std/variant;h=19b2158690a9b4d03081f697e6a945d7c2a4e56f;hb=cfb582f62791dfadc243d97d37f0b83ef77cf480#l380
https://godbolt.org/z/T77nGvM4o
https://godbolt.org/z/599qczYqs

Anyway, both Abseil and libstdc++ specialize variants with up to 33 and 11 alternatives, respectively with a switch/case, which is how they avoid the optimization issues that libc++ trips.
https://github.com/abseil/abseil-cpp/blob/8028a87c96df0fff5ab58daeec30c43ce6fb0d20/absl/types/internal/variant.h#L515
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=78113

Seems we should either make libc++ implement a similar specialization, or make Clang better at optimizing away jump tables.

Abseil also has a variant benchmark, but I haven't tried it on libc++ yet.
https://github.com/abseil/abseil-cpp/blob/8028a87c96df0fff5ab58daeec30c43ce6fb0d20/absl/types/variant_benchmark.cc

[ldionne]

We actually tried moving to a switch-based variant in the past and I think there were some issues. We committed it but it was reverted and I think the patch was never pursued again. Some relevant links:

https://reviews.llvm.org/D91662
9c09757
35d2269

[davidben]

Ah, interesting. I see that goes up to 256 for the switch-case, which is much higher than Abseil and libstdc++'s threshold. I'm guessing that, without optimization, the dead switch-case branches don't get deleted?

Maybe a smaller threshold? Or maybe, rather than a switch/case, just recursively generate an if/else chain? I would naively hope both are comparably optimizable.

[ldionne]

If you're willing to take up that patch, I'll review it.

[davidben]

Just to circle back here, @alexander-shaposhnikov put together #77709 which, AIUI, will do the transform automatically. (No strong feelings on my end whether this should be done in the optimizer, libc++, or both.)

[rnk]

This issue came up today, and I spent enough time thinking about it to form a preference for fixing this in the middle-end. In C++ and performance engineering generally, we're always making tradeoffs between what we expect the compiler optimizer to do for us and what optimizations we expect reasonable programmers to write if they expect to get good results, and this case is kind of on the edge where either approach seems reasonable: library logic to emit a switch, or middle-end logic to form the switch.

For me, I feel like libc++ headers are already large and slow to compile, and adding the logic to choose a switch or function pointer lookup based feels like implementing optimization pass decisions in library code in the header. If we do it in the library, this becomes a very hard-coded decision, potentially with C++ ABI implications. If we do it in the optimizer, we are free to take the same source code and tune the switch threshold to optimize for size or performance after the fact. And, who knows, perhaps this table of function pointers pattern appears organically somewhere in user written code.

Reasonable people could absolutely disagree on this, but I would lean in the direction of simplifying libc++ headers if possible.

That raises the question of, what blockers are there to enabling the table-to-switch conversion pass as part of the default pipeline?

[zmodem]

That raises the question of, what blockers are there to enabling the table-to-switch conversion pass as part of the default pipeline?

That's #83229 and the issue seem to be concerns about pathological compile time increase.