[Bug libstdc++/91788] New: std::variant index +1-1

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

[Bug libstdc++/91788] New: std::variant index +1-1

rguenth at gcc dot gnu.org
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=91788

            Bug ID: 91788
           Summary: std::variant index +1-1
           Product: gcc
           Version: 10.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: glisse at gcc dot gnu.org
  Target Milestone: ---

(this is a detail, it probably has a negligible impact)

      constexpr size_t index() const noexcept
      { return size_t(typename _Base::__index_type(this->_M_index + 1)) - 1; }

IIUC, the whole +1-1 is here so that for a valueless variant, index_type(-1)
becomes size_t(-1). I think there are cases where we could do better. For
instance, for a never valueless type, we could just return _M_index. If there
are fewer than 128 alternatives, we could use a sign extension: "return (signed
char)_M_index;". Maybe some well-placed __builtin_unreachable to specify the
range of _M_index would work as well.
Reply | Threaded
Open this post in threaded view
|

[Bug libstdc++/91788] std::variant index +1-1

rguenth at gcc dot gnu.org
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=91788

--- Comment #1 from Marc Glisse <glisse at gcc dot gnu.org> ---
Internally, it may also be possible to avoid calling index() so often and work
with the raw _M_index more often.
Reply | Threaded
Open this post in threaded view
|

[Bug libstdc++/91788] std::variant index +1-1

rguenth at gcc dot gnu.org
In reply to this post by rguenth at gcc dot gnu.org
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=91788

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2019-09-23
     Ever confirmed|0                           |1

--- Comment #2 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Marc Glisse from comment #0)
> IIUC, the whole +1-1 is here so that for a valueless variant, index_type(-1)
> becomes size_t(-1).

You do understand correctly :-)

> I think there are cases where we could do better. For
> instance, for a never valueless type, we could just return _M_index. If
> there are fewer than 128 alternatives, we could use a sign extension:
> "return (signed char)_M_index;".

I think we can do that more generically. Does this look right?

--- a/libstdc++-v3/include/std/variant
+++ b/libstdc++-v3/include/std/variant
@@ -1518,7 +1518,14 @@ namespace __variant
       { return !this->_M_valid(); }

       constexpr size_t index() const noexcept
-      { return size_t(typename _Base::__index_type(this->_M_index + 1)) - 1; }
+      {
+       using __index_type = typename _Base::__index_type;
+       if constexpr (__detail::__variant::__never_valueless<_Types...>())
+         return this->_M_index;
+       else if constexpr (sizeof...(_Types) <= __index_type(-1) / 2)
+         return make_signed_t<__index_type>(this->_M_index);
+       return size_t(typename _Base::__index_type(this->_M_index + 1)) - 1;
+      }

       void
       swap(variant& __rhs)



(In reply to Marc Glisse from comment #1)
> Internally, it may also be possible to avoid calling index() so often and
> work with the raw _M_index more often.

IIRC I considered that, but (at the time) decided to play it safe rather than
spend more time analysing what could be done.

I think we could replace checks like this in get<_Np>:

  if (__v.index() == _Np)

with:

  static_assert(index_type(_Np) == _Np && _Np != index_type(-1));
  if (__v._M_index == _Np)

And in many (most?) cases the static assert is unnecessary because we already
check something like:

       static_assert(_Np < sizeof...(_Types),
                    "The index must be in [0, number of alternatives)");

Anywhere we test equality of index() with a value that is known to be in range,
it's OK to use index_type(-1) directly instead of extending it to size_t(-1).
(The downside would be that many more functions might need to be friends to
access _M_index).

The relational operators need a bit more thought and I don't think we can
change the calls to index() in __do_visit without breaking the implied contract
with the _M_access functions in the "vtable".
Reply | Threaded
Open this post in threaded view
|

[Bug libstdc++/91788] std::variant index +1-1

rguenth at gcc dot gnu.org
In reply to this post by rguenth at gcc dot gnu.org
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=91788

--- Comment #3 from Marc Glisse <glisse at gcc dot gnu.org> ---
(In reply to Jonathan Wakely from comment #2)
> I think we can do that more generically. Does this look right?

lgtm

> (The downside would be that many more functions might need to be
> friends to access _M_index).

You can always make in public instead, or give it a public accessor...

(not commenting on the rest, I haven't studied the implementation enough)
Reply | Threaded
Open this post in threaded view
|

[Bug libstdc++/91788] std::variant index +1-1

rguenth at gcc dot gnu.org
In reply to this post by rguenth at gcc dot gnu.org
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=91788

--- Comment #4 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Author: redi
Date: Mon Sep 23 15:54:16 2019
New Revision: 276056

URL: https://gcc.gnu.org/viewcvs?rev=276056&root=gcc&view=rev
Log:
PR libstdc++/91788 improve codegen for std::variant<T...>::index()

If __index_type is a smaller type than size_t, then the result of
size_t(__index_type(-1)) is not equal to size_t(-1), but to an incorrect
value such as size_t(255) or size_t(65535). The old implementation of
variant<T...>::index() uses (size_t(__index_type(_M_index + 1)) - 1)
which is always correct, but generates suboptimal code for many common
cases.

When the __index_type is size_t or valueless variants are not possible
we can just return the value directly.

When the number of alternatives is sufficiently small the result of
converting the _M_index value to the corresponding signed type will be
either non-negative or -1. In those cases converting to the signed type
and then to size_t will either produce the correct positive value or
will sign extend -1 to (size_t)-1 as desired.

For the remaining case we keep the existing arithmetic operations to
ensure the correct result.

        PR libstdc++/91788 (partial)
        * include/std/variant (variant::index()): Improve codegen for cases
        where conversion to size_t already works correctly.

Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/std/variant