<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=https://github.com/llvm/llvm-project/issues/73699>73699</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            libc++ std::visit does not optimize well
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            libc++
      </td>
    </tr>

    <tr>
      <th>Assignees</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Reporter</th>
      <td>
          davidben
      </td>
    </tr>
</table>

<pre>
    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
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzEVsFu4zgS_Rr6UrAhkZYlHXzoJKtFY2d2B9hc-tQgqZJUHYpUk5S9ytcvKGvS7p3undwGCJLYYknv1Xv1SjIE6i3imRUPrHjayTkOzp9beaFWod0p1y7nZ7-Q7SE6CFeKeoDOuxHYKZMqGCY-MPHhIj1JG9kpS8fYKQux_cMVsvA4eDfSPILHMJuIbfpSQhilMaDmCNbZffR0IWlAkZV-gUCvCB57jyGQswf4zb0kPNK72baMP8JHiAPZF4gDgpZzQKAAhpRm_GH9KcP3mChQQpQ-ZU8s236_owIC4hgSR4VA42RwRJtoqAXUTKZdgUE3Wx3JWZgc2YgeolQGQdoWvszjlA6RjQ4oHuAjdIlHohBgciHCdSA9QJj7HkMMtwvajRhujZfgZRzQg2tb8Ph1Jr-igOuAHuHxRgGm1OmAAaSFfzFe5YzXP-4CfwSPRka6YGKWumjnUaUndKAHRxpD0ild2OQ8AOPVP_GCfqQVu4w3nBRAJrATGdxHGhG0syEmB_DHtQGGXtAssLjZJ4y9lyNcyRjoJJn0_K0aFHbOYzoIPUaIzsEo7QLSRPR2hbsqoaVHxhO9m4xDjFNIFHnDeDMZuXSz2Z40ku0Pyrg-TC4etBsZb3iWV4w3OWe8uQ5o9xP6zvlRWo37fpZe2ogY9sPsYzgMcTT3pnlOrFuHwTJeRnBTpDEZ9orGrHwpbqZ5NDLpHmC2qxuS_taQTb5YkoF7kMrNcXXFz6brVhGgI4uHH_HtXauciQfne8abV8ab-jccsC3q1_cd__r8j8uvn9zfynuWv9ALXilgEtGQCrHdJuWNcFgZv03Unz0lb-0nq-pSv-_48YuWn_TFDfegPqbRwhDJ9mb5IzJ5cdQGGORlS6-r837Zepy8zE7ZRZoZDYbwWS2f8T8apzS266BHGfEAzwMuq37rZPhlTcEJNUmTVP5J0kV3e_qWSAHTbNo0LmnCAymDP-uU1ofezhv1nmL6WjQTE0_rJYpMPEgmnpRxiomHjomnN9pFIl7wh_1FMN6Q1WZukfEmQeTN7_jEw8DEU14rnhfVqc5krY5tJrIq7051iSdZH4u21FwesTh16bhi4kl3qqh4d-JlnbedbDU_irYuW1F2maoEdmWpu2OVMS6MqLL3yfpclvbvl1-P7n3Hi7r-ql8_fQ33Lvhgl6tc5VcuDvBBBSSzJc29He5U2zoR4EpxgHlKegmx1uT5d_lyy8ZUmj6a5VYht0XIeJPETYdumU0BBndNqi93BthGRK4bgUKYU26lxPy2cCB6msKPB5riMKstq-TK7u2fvZ4mxpvVC7ypMl7JqtT1qe2yrusKqYqqlYhaZPooNJ46lbU8u5Wnu8RlShybdUlZab655DAwLn4p8uLPTarm_pWMkclog7t-VnN_0D0x0VDLxFNZ5bm4F-zfaxpeEcLgZtMC0rrNRvmC9x15266p3TSSkf6bhmsvU9_dVngLV4UxbVv5lsNrqF7lsq7d2xb-vcubeza7mOBgkGl5bQ0AhVYPo_Qvq7XmCB9TlOAt5qMnXKPd2XvMC8a_TMMN9-c33Aetd-1ZtLWo5Q7PeZnlPDsWRbUbzplo25OuT4VUlchQ5OKIvM0zVekuP2qxozPPuMhzXvHsWOfVIeuy46kSJ3XMO15VBTtmOEoyB2MuY3LCbnX2uRSnut4ZqdCE9a2S8_v3Kp7eMv05Fe3V3Ad2zAyFGL7dJlI0eL5r6vcvLOuuBev-Z9XuZm_O_6fp6fbbn_3k3RfUKVlvw8h4s6L-bwAAAP__WYqcGg">