Switching absl::variant to std::variant

630 views
Skip to first unread message

David Benjamin

unread,
Nov 21, 2023, 4:25:17 PM11/21/23
to cxx
Hi all,

Hot off the heels of std::optional, I think we can close the loop on std::variant now too. The CL is here:

There is a binary size increase, but it's the same cause as with std::optional (crash reporting vs opitmizability tradeoff), so see the previous discussion and document for details on that:

Beyond that, the main thing of note is that std::variant is stricter than absl::variant about narrowing. Originally, variant<A, B, C>'s constructor was modeled as having overloads for A, B, and C. So if your type implicitly converts to A, that will bind to A. (Assuming the overload set isn't ambiguous.)

After p0608r3 and p1957r2, this was tightened so that narrowing conversions were not allowed. So, for example, a variant<size_t, ...> cannot be initialized with an int because int may be negative.

absl::variant implements the original behavior. std::variant implements the new one. For the most part, our code doesn't care. There were a few incompatibles, which I've fixed (https://crrev.com/c/5049641 has the last of it). The most common is that, if our variants take a size_t, passing constants needs to look like 0u or size_t{0} because the literal 0 has type int, and by the time we get to the std::variant constructor, the fact that it's non-negative at compile-time constant has been lost.

Thoughts?

David

Peter Kasting

unread,
Nov 21, 2023, 4:39:48 PM11/21/23
to David Benjamin, cxx
That tighter constant seems nice.

+1 from me.

PK

--
You received this message because you are subscribed to the Google Groups "cxx" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cxx+uns...@chromium.org.
To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/cxx/CAF8qwaDuizS7tVwgHAfDY_6%3DYvkuWa4arr%3DbaohOqYxks1VQQg%40mail.gmail.com.

Dana Jansens

unread,
Nov 21, 2023, 5:14:54 PM11/21/23
to Peter Kasting, David Benjamin, cxx
+1 and +1

To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/cxx/CAAHOzFBS6hDv%3DjMkcFUaUED_z9tC_1jxcY8vhusFTjjFTMSNWQ%40mail.gmail.com.

Nico Weber

unread,
Nov 21, 2023, 10:29:32 PM11/21/23
to Dana Jansens, Peter Kasting, David Benjamin, cxx
Another+1, looks great 🙂

To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/cxx/CAHtyhaQsx9ETxFcfQwwbFeuYORGt7T3c_628pOgGKgDgMwjwSg%40mail.gmail.com.

David Benjamin

unread,
Nov 28, 2023, 11:41:12 AM11/28/23
to Nico Weber, Dana Jansens, Peter Kasting, cxx
An update: my original claim about binary size increase was incorrect. In fact there are no hardening checks in {std,absl}::variant at all because all the places we'd harden are actually defined to throw anyway. So it can't be related to the trap sequence.

I reran the experiments and now the delta from verbose_abort => verbose_abort + std::variant and builtin_trap => builtin_trap + std::variant are comparable. I remember when I previously did this, I ran into some weird infra behavior (possibly bugs but don't remember exactly what happened) relating to rebasing CLs, so I must have gotten confused by it. I've tried again now with fresh CLs to avoid that mess.

So now we've got an unexplained size increase that I'll try to drill into. (Alas, SuperSize is unhelpful because of https://crbug.com/1482440.)

David Benjamin

unread,
Nov 28, 2023, 2:07:48 PM11/28/23
to Nico Weber, Dana Jansens, Peter Kasting, cxx
Okay, while supersize isn't showing me the disassembly, most of the files that get larger have a bunch of symbols relating to std::visit internals. Looking at the absl and libc++ visit implementations, I noticed a difference. Abseil compiles std::visit into a switch/case if there are at most 33 cases. Otherwise it falls back to a function pointer table.


I found this blog post which seems to discuss this a bit. Apparently the C++ standard requires that std::visit be O(1) in the number of choices in the variant. Nevermind that is a compile-time constant. So I guess the conclusion is people believe you have to build a table, rather than chaining conditionals. But jumping through tables is supposedly hard for the compiler to optimize.

This godbolt seems to support this theory. Even for a very basic two-element variant, std::visit from libc++ cannot inline the table.
https://godbolt.org/z/fGTz8e753

Interestingly, the libstdc++ std::visit optimizes well... a little too well. It doesn't seem to be handling the valueless_by_exception case, unless somehow libstdc++ knows the variant can never be in that state??

Supposing this theory is true, I think our options are to either decide we don't care enough, or upstream Abseil's optimization to libc++.

David Benjamin

unread,
Nov 28, 2023, 3:51:05 PM11/28/23
to Nico Weber, Dana Jansens, Peter Kasting, cxx

Matt Denton

unread,
Nov 28, 2023, 7:51:52 PM11/28/23
to David Benjamin, Nico Weber, Dana Jansens, Peter Kasting, cxx
On Tue, Nov 28, 2023 at 12:51 PM David Benjamin <davi...@chromium.org> wrote:

On Tue, Nov 28, 2023 at 2:07 PM David Benjamin <davi...@chromium.org> wrote:
Okay, while supersize isn't showing me the disassembly, most of the files that get larger have a bunch of symbols relating to std::visit internals. Looking at the absl and libc++ visit implementations, I noticed a difference. Abseil compiles std::visit into a switch/case if there are at most 33 cases. Otherwise it falls back to a function pointer table.


I found this blog post which seems to discuss this a bit. Apparently the C++ standard requires that std::visit be O(1) in the number of choices in the variant. Nevermind that is a compile-time constant. So I guess the conclusion is people believe you have to build a table, rather than chaining conditionals. But jumping through tables is supposedly hard for the compiler to optimize.

For the record a switch case up to 33 choices in the variant (with a function pointer table for >33) is still O(1) in the number of choices in the variant. Not to mention that if somehow abseil generated a switch case for any number of choices in the variant, the compiler would probably just generate a jump table anyway, though of course that's not guaranteed.
 

David Benjamin

unread,
Nov 28, 2023, 8:02:27 PM11/28/23
to Matt Denton, Nico Weber, Dana Jansens, Peter Kasting, cxx
On Tue, Nov 28, 2023, 19:51 Matt Denton <mpde...@google.com> wrote:


On Tue, Nov 28, 2023 at 12:51 PM David Benjamin <davi...@chromium.org> wrote:

On Tue, Nov 28, 2023 at 2:07 PM David Benjamin <davi...@chromium.org> wrote:
Okay, while supersize isn't showing me the disassembly, most of the files that get larger have a bunch of symbols relating to std::visit internals. Looking at the absl and libc++ visit implementations, I noticed a difference. Abseil compiles std::visit into a switch/case if there are at most 33 cases. Otherwise it falls back to a function pointer table.


I found this blog post which seems to discuss this a bit. Apparently the C++ standard requires that std::visit be O(1) in the number of choices in the variant. Nevermind that is a compile-time constant. So I guess the conclusion is people believe you have to build a table, rather than chaining conditionals. But jumping through tables is supposedly hard for the compiler to optimize.

For the record a switch case up to 33 choices in the variant (with a function pointer table for >33) is still O(1) in the number of choices in the variant. Not to mention that if somehow abseil generated a switch case for any number of choices in the variant, the compiler would probably just generate a jump table anyway, though of course that's not guaranteed.


Oh yeah, no disagreements with any of this. I don't think the spec should have this requirement in the first place because it doesn't make much sense. I mean, you also have to load the table from the executable. I suppose that only needs to happen once per call site, but the spec didn't say amortized.

I think the only sensible scheme is to just treat the number of choices as a constant w.r.t big-O. Template expansion will fail long before it gets large anyway, and the compiler should be perfectly capable of figuring out the best way to compile a giant switch/case or if/else chain. :-)

David
Reply all
Reply to author
Forward
0 new messages