[v3] Use single-visitation in variant assignment and swap.

Message ID CAFk2RUZ-RvZyqWcUnyAHFRqc9VoPW9+qdWdXQCUGb5i5757wXQ@mail.gmail.com
State New
Headers show
Series
  • [v3] Use single-visitation in variant assignment and swap.
Related show

Commit Message

Ville Voutilainen March 30, 2019, 6 p.m.
This patch makes assignments correct, because they need to
match indices instead of types. In addition, we cut down the
codegen size. The symbols are longer than before, the the amount
of them is roughly the same, so there's no longer an explosion
in their amount.

Relops are the last bit in these fixes, I'll fix them during the weekend.

2019-03-30  Ville Voutilainen  <ville.voutilainen@gmail.com>

    Use single-visitation in variant assignment and swap.
    Also use indices instead of types when checking whether
    variants hold the same thing.
    * include/std/variant (__do_visit): Add a template parameter
    for index visitation, invoke with indices if index visitation
    is used.
    (__variant_idx_cookie): New.
    (_Copy_assign_base::operator=): Do single-visitation with
    an index visitor.
    (_Move_assign_base::operator=): Likewise.
    (_Extra_visit_slot_needed): Adjust.
    (__visit_invoke): Call with indices if it's an index visitor.
    (swap): Do single-visitation with an index visitor.
    (__visitor_result_type): New.

Comments

Paolo Carlini April 1, 2019, 8:29 a.m. | #1
Hi

On 30/03/19 19:00, Ville Voutilainen wrote:
> -  template<typename _Visitor, typename... _Variants>

> +  template<bool __use_index, typename _Visitor, typename... _Variants>

> +    decltype(auto)

> +    __visitor_result_type(_Visitor&& __visitor, _Variants&&... __variants)

> +    {

> +      if constexpr(__use_index)

> +        return __detail::__variant::__variant_idx_cookie{};

> +      else

> +	return std::forward<_Visitor>(__visitor)(

> +	  std::get<0>(std::forward<_Variants>(__variants))...);

> +    }


If I'm not misreading something, the new function will be usually 
compiled/optimized to something very small and isn't constexpr thus 
normally should be explicitly marked inline. Or the problem is the 
missing constexpr? (sorry, I didn't really study the new code)

Paolo.
Ville Voutilainen April 1, 2019, 8:43 a.m. | #2
On Mon, 1 Apr 2019 at 11:30, Paolo Carlini <paolo.carlini@oracle.com> wrote:
>

> Hi

>

> On 30/03/19 19:00, Ville Voutilainen wrote:

> > -  template<typename _Visitor, typename... _Variants>

> > +  template<bool __use_index, typename _Visitor, typename... _Variants>

> > +    decltype(auto)

> > +    __visitor_result_type(_Visitor&& __visitor, _Variants&&... __variants)

> > +    {

> > +      if constexpr(__use_index)

> > +        return __detail::__variant::__variant_idx_cookie{};

> > +      else

> > +     return std::forward<_Visitor>(__visitor)(

> > +       std::get<0>(std::forward<_Variants>(__variants))...);

> > +    }

>

> If I'm not misreading something, the new function will be usually

> compiled/optimized to something very small and isn't constexpr thus

> normally should be explicitly marked inline. Or the problem is the

> missing constexpr? (sorry, I didn't really study the new code)


The only use of this function is to compute its return type. It's
never called. I should probably comment on that...
Ville Voutilainen April 1, 2019, 8:45 a.m. | #3
On Sat, 30 Mar 2019 at 20:00, Ville Voutilainen
<ville.voutilainen@gmail.com> wrote:
>

> This patch makes assignments correct, because they need to

> match indices instead of types. In addition, we cut down the

> codegen size. The symbols are longer than before, the the amount

> of them is roughly the same, so there's no longer an explosion

> in their amount.

>

> Relops are the last bit in these fixes, I'll fix them during the weekend.


Here. This does produce 17 symbols instead of 9 for a test with a
single operator== comparison.
But it's not 47 like it is with the code before this patch.

2019-04-01  Ville Voutilainen  <ville.voutilainen@gmail.com>

    Use single-visitation in variant assignment and swap.
    Also use indices instead of types when checking whether
    variants hold the same thing.
    * include/std/variant (__do_visit): Add a template parameter
    for index visitation, invoke with indices if index visitation
    is used.
    (__variant_idx_cookie): New.
    (__visit_with_index): Likewise.
    (_Copy_assign_base::operator=): Do single-visitation with
    an index visitor.
    (_Move_assign_base::operator=): Likewise.
    (_Extra_visit_slot_needed): Adjust.
    (__visit_invoke): Call with indices if it's an index visitor.
    (relops): Do single-visitation with an index visitor.
    (swap): Likewise.
    (__visitor_result_type): New.
diff --git a/libstdc++-v3/include/std/variant b/libstdc++-v3/include/std/variant
index 7fd6947..3a11e1c 100644
--- a/libstdc++-v3/include/std/variant
+++ b/libstdc++-v3/include/std/variant
@@ -138,7 +138,7 @@ namespace __variant
     constexpr variant_alternative_t<_Np, variant<_Types...>> const&&
     get(const variant<_Types...>&&);
 
-  template<typename _Visitor, typename... _Variants>
+  template<bool __use_index=false, typename _Visitor, typename... _Variants>
     constexpr decltype(auto)
     __do_visit(_Visitor&& __visitor, _Variants&&... __variants);
 
@@ -175,6 +175,10 @@ namespace __variant
 
   // used for raw visitation
   struct __variant_cookie {};
+  // used for raw visitation with indices passed in
+  struct __variant_idx_cookie {};
+  // a more explanatory name than 'true'
+  inline constexpr auto __visit_with_index = bool_constant<true>{};
 
   // _Uninitialized<T> is guaranteed to be a literal type, even if T is not.
   // We have to do this, because [basic.types]p10.5.3 (n4606) is not implemented
@@ -570,45 +574,44 @@ namespace __variant
       operator=(const _Copy_assign_base& __rhs)
 	  noexcept(_Traits<_Types...>::_S_nothrow_copy_assign)
       {
-	__do_visit([this, &__rhs](auto&& __this_mem, auto&& __rhs_mem) mutable
-		   -> __detail::__variant::__variant_cookie
+	__do_visit<__visit_with_index>([this](auto&& __rhs_mem,
+					      auto __rhs_index) mutable
+	    -> __detail::__variant::__variant_idx_cookie
 	  {
-	    if constexpr (is_same_v<
-			    remove_reference_t<decltype(__this_mem)>,
-			    remove_reference_t<decltype(__rhs_mem)>>)
+	    if constexpr (__rhs_index != variant_npos)
 	      {
-		if constexpr (!is_same_v<
-			        remove_reference_t<decltype(__rhs_mem)>,
-			        __variant_cookie>)
-		  __this_mem = __rhs_mem;
-	      }
-	    else
-	      {
-		if constexpr (!is_same_v<
-			        remove_reference_t<decltype(__rhs_mem)>,
-			        __variant_cookie>)
+		if (this->_M_index == __rhs_index)
 		  {
-		    using __rhs_type =
-		      remove_reference_t<decltype(__rhs_mem)>;
-		    if constexpr (is_nothrow_copy_constructible_v<__rhs_type>
-		      || !is_nothrow_move_constructible_v<__rhs_type>)
+		    if constexpr (__rhs_index != variant_npos)
 		      {
-			this->_M_destructive_copy(__rhs._M_index, __rhs_mem);
+			auto& __this_mem =
+			  __get<__rhs_index>(*this);
+			if constexpr (is_same_v<
+				      remove_reference_t<decltype(__this_mem)>,
+				      remove_reference_t<decltype(__rhs_mem)>>)
+			  __this_mem = __rhs_mem;
 		      }
+		  }
+		else
+		  {
+		    using __rhs_type =
+		      remove_reference_t<decltype(__rhs_mem)>;
+		    if constexpr
+		      (is_nothrow_copy_constructible_v<__rhs_type>
+		       || !is_nothrow_move_constructible_v<__rhs_type>)
+			this->_M_destructive_copy(__rhs_index, __rhs_mem);
 		    else
 		      {
 			auto __tmp(__rhs_mem);
-			this->_M_destructive_move(__rhs._M_index,
+			this->_M_destructive_move(__rhs_index,
 						  std::move(__tmp));
 		      }
 		  }
-		else
-		  {
-		    this->_M_reset();
-		  }
 	      }
-	  return {};
-	}, __variant_cast<_Types...>(*this), __variant_cast<_Types...>(__rhs));
+	    else
+	      this->_M_reset();
+	    return {};
+	  }, __variant_cast<_Types...>(__rhs));
 	__glibcxx_assert(this->_M_index == __rhs._M_index);
 	return *this;
       }
@@ -641,25 +644,32 @@ namespace __variant
       operator=(_Move_assign_base&& __rhs)
 	  noexcept(_Traits<_Types...>::_S_nothrow_move_assign)
       {
-	__do_visit([this, &__rhs](auto&& __this_mem, auto&& __rhs_mem) mutable
-		   -> __detail::__variant::__variant_cookie
+	__do_visit<__visit_with_index>([this](auto&& __rhs_mem,
+					      auto __rhs_index) mutable
+	    -> __detail::__variant::__variant_idx_cookie
 	  {
-	    if constexpr (is_same_v<
-			    remove_reference_t<decltype(__this_mem)>,
-			    remove_reference_t<decltype(__rhs_mem)>>)
+	    if constexpr (__rhs_index != variant_npos)
 	      {
-		if constexpr (!is_same_v<
-			        remove_reference_t<decltype(__rhs_mem)>,
-			        __variant_cookie>)
-		  __this_mem = std::move(__rhs_mem);
+		if (this->_M_index == __rhs_index)
+		  {
+		    if constexpr (__rhs_index != variant_npos)
+		      {
+			auto& __this_mem =
+			  __get<__rhs_index>(*this);
+			if constexpr (is_same_v<
+				      remove_reference_t<decltype(__this_mem)>,
+				      remove_reference_t<decltype(__rhs_mem)>>)
+			  __this_mem = std::move(__rhs_mem);
+		      }
+		  }
+		else
+		  this->_M_destructive_move(__rhs_index,
+					    std::move(__rhs_mem));
 	      }
 	    else
-	      {
-		auto __tmp(std::move(__rhs_mem));
-		this->_M_destructive_move(__rhs._M_index, std::move(__tmp));
-	      }
-	  return {};
-	}, __variant_cast<_Types...>(*this), __variant_cast<_Types...>(__rhs));
+	      this->_M_reset();
+	    return {};
+	  }, __variant_cast<_Types...>(__rhs));
 	__glibcxx_assert(this->_M_index == __rhs._M_index);
 	return *this;
       }
@@ -777,7 +787,8 @@ namespace __variant
       : bool_constant<__never_valueless<_Types...>()> {};
 
     static constexpr bool value =
-      is_same_v<_Maybe_variant_cookie, __variant_cookie>
+      (is_same_v<_Maybe_variant_cookie, __variant_cookie>
+       || is_same_v<_Maybe_variant_cookie, __variant_idx_cookie>)
       && !_Variant_never_valueless<__remove_cvref_t<_Variant>>::value;
   };
 
@@ -925,7 +936,13 @@ namespace __variant
       static constexpr decltype(auto)
       __visit_invoke(_Visitor&& __visitor, _Variants... __vars)
       {
-	return std::__invoke(std::forward<_Visitor>(__visitor),
+	if constexpr (is_same_v<_Result_type, __variant_idx_cookie>)
+	  return std::__invoke(std::forward<_Visitor>(__visitor),
+	    __element_by_index_or_cookie<__indices>(
+	      std::forward<_Variants>(__vars))...,
+	      integral_constant<size_t, __indices>()...);
+	else
+	  return std::__invoke(std::forward<_Visitor>(__visitor),
 	    __element_by_index_or_cookie<__indices>(
 	      std::forward<_Variants>(__vars))...);
       }
@@ -1082,25 +1099,25 @@ namespace __variant
 				 const variant<_Types...>& __rhs) \
     { \
       bool __ret = true; \
-      __do_visit([&__ret, &__lhs, __rhs] \
-		 (auto&& __this_mem, auto&& __rhs_mem) mutable	\
-		   -> __detail::__variant::__variant_cookie \
+      __do_visit<__detail::__variant::__visit_with_index>( \
+        [&__ret, &__lhs, __rhs] \
+		 (auto&& __rhs_mem, auto __rhs_index) mutable \
+		   -> __detail::__variant::__variant_idx_cookie \
         { \
-	  if constexpr (!is_same_v< \
-			  remove_reference_t<decltype(__this_mem)>, \
-			  remove_reference_t<decltype(__rhs_mem)>> \
-			|| is_same_v<decltype(__this_mem), \
-			             __detail::__variant::__variant_cookie>) \
-	    __ret = (__lhs.index() + 1) __OP (__rhs.index() + 1); \
-	  else if constexpr (is_same_v< \
-			       remove_reference_t<decltype(__this_mem)>, \
-			       remove_reference_t<decltype(__rhs_mem)>> \
-                             && !is_same_v< \
-	                          remove_reference_t<decltype(__this_mem)>, \
-				  __detail::__variant::__variant_cookie>) \
-	    __ret = __this_mem __OP __rhs_mem; \
+	  if constexpr (__rhs_index != variant_npos) \
+	    { \
+	      if (__lhs.index() == __rhs_index) \
+	        { \
+		  auto& __this_mem = get<__rhs_index>(__lhs); \
+                  __ret = __this_mem __OP __rhs_mem; \
+                } \
+	      else \
+		__ret = (__lhs.index() + 1) __OP (__rhs_index + 1); \
+            } \
+          else \
+            __ret = (__lhs.index() + 1) __OP (__rhs_index + 1); \
 	  return {}; \
-	}, __lhs, __rhs); \
+	}, __rhs); \
       return __ret; \
     } \
 \
@@ -1402,51 +1419,47 @@ namespace __variant
       noexcept((__is_nothrow_swappable<_Types>::value && ...)
 	       && is_nothrow_move_constructible_v<variant>)
       {
-	__do_visit([this, &__rhs](auto&& __this_mem, auto&& __rhs_mem) mutable
-		   -> __detail::__variant::__variant_cookie
+	__do_visit<__detail::__variant::__visit_with_index>(
+	  [this, &__rhs](auto&& __rhs_mem,
+			 auto __rhs_index) mutable
+	    -> __detail::__variant::__variant_idx_cookie
 	  {
-	    if constexpr (is_same_v<
-			    remove_reference_t<decltype(__this_mem)>,
-			    remove_reference_t<decltype(__rhs_mem)>>)
+	    if constexpr (__rhs_index != variant_npos)
 	      {
-		if constexpr (!is_same_v<
-			        remove_reference_t<decltype(__rhs_mem)>,
-			        __detail::__variant::__variant_cookie>)
+		if (this->index() == __rhs_index)
 		  {
+		    auto& __this_mem =
+		      get<__rhs_index>(*this);
 		    using std::swap;
 		    swap(__this_mem, __rhs_mem);
 		  }
+		else
+		  {
+		    if (this->index() != variant_npos)
+		      {
+			auto __tmp(std::move(__rhs_mem));
+			__rhs = std::move(*this);
+			this->_M_destructive_move(__rhs_index,
+						  std::move(__tmp));
+		      }
+		    else
+		      {
+			this->_M_destructive_move(__rhs_index,
+						  std::move(__rhs_mem));
+			__rhs._M_reset();
+		      }
+		  }
 	      }
 	    else
 	      {
-		if constexpr (is_same_v<
-			        remove_reference_t<decltype(__this_mem)>,
-			        __detail::__variant::__variant_cookie>)
+		if (this->index() != variant_npos)
 		  {
-		    this->_M_destructive_move(__rhs.index(),
-					      std::move(__rhs_mem));
-		    __rhs._M_reset();
-		  }
-		else if constexpr (is_same_v<
-			             remove_reference_t<decltype(__rhs_mem)>,
-			             __detail::__variant::__variant_cookie>)
-		  {
-		    __rhs._M_destructive_move(this->index(),
-					      std::move(__this_mem));
+		    __rhs = std::move(*this);
 		    this->_M_reset();
 		  }
-		else
-		  {
-		    auto __tmp(std::move(__rhs_mem));
-		    auto __idx = __rhs.index();
-		    __rhs._M_destructive_move(this->index(),
-					      std::move(__this_mem));
-		    this->_M_destructive_move(__idx,
-					      std::move(__tmp));
-		  }
 	      }
-	  return {};
-	}, *this, __rhs);
+	    return {};
+	  }, __rhs);
       }
 
     private:
@@ -1523,13 +1536,25 @@ namespace __variant
       return __detail::__variant::__get<_Np>(std::move(__v));
     }
 
-  template<typename _Visitor, typename... _Variants>
+  template<bool __use_index, typename _Visitor, typename... _Variants>
+    decltype(auto)
+    __visitor_result_type(_Visitor&& __visitor, _Variants&&... __variants)
+    {
+      if constexpr(__use_index)
+        return __detail::__variant::__variant_idx_cookie{};
+      else
+	return std::forward<_Visitor>(__visitor)(
+	  std::get<0>(std::forward<_Variants>(__variants))...);
+    }
+
+  template<bool __use_index, typename _Visitor, typename... _Variants>
     constexpr decltype(auto)
     __do_visit(_Visitor&& __visitor, _Variants&&... __variants)
     {
       using _Result_type =
-	decltype(std::forward<_Visitor>(__visitor)(
-	    std::get<0>(std::forward<_Variants>(__variants))...));
+	decltype(__visitor_result_type<__use_index>(
+	           std::forward<_Visitor>(__visitor),
+	           std::forward<_Variants>(__variants)...));
 
       constexpr auto& __vtable = __detail::__variant::__gen_vtable<
 	_Result_type, _Visitor&&, _Variants&&...>::_S_vtable;
Paolo Carlini April 1, 2019, 8:45 a.m. | #4
Hi

On 01/04/19 10:43, Ville Voutilainen wrote:
> On Mon, 1 Apr 2019 at 11:30, Paolo Carlini <paolo.carlini@oracle.com> wrote:

>> Hi

>>

>> On 30/03/19 19:00, Ville Voutilainen wrote:

>>> -  template<typename _Visitor, typename... _Variants>

>>> +  template<bool __use_index, typename _Visitor, typename... _Variants>

>>> +    decltype(auto)

>>> +    __visitor_result_type(_Visitor&& __visitor, _Variants&&... __variants)

>>> +    {

>>> +      if constexpr(__use_index)

>>> +        return __detail::__variant::__variant_idx_cookie{};

>>> +      else

>>> +     return std::forward<_Visitor>(__visitor)(

>>> +       std::get<0>(std::forward<_Variants>(__variants))...);

>>> +    }

>> If I'm not misreading something, the new function will be usually

>> compiled/optimized to something very small and isn't constexpr thus

>> normally should be explicitly marked inline. Or the problem is the

>> missing constexpr? (sorry, I didn't really study the new code)

> The only use of this function is to compute its return type. It's

> never called. I should probably comment on that...


Oh, yes, now I see, a few lines below. That's clear enough, I think.

Paolo.
Ville Voutilainen April 1, 2019, 8:50 a.m. | #5
On Mon, 1 Apr 2019 at 11:45, Paolo Carlini <paolo.carlini@oracle.com> wrote:
> >>> +    __visitor_result_type(_Visitor&& __visitor, _Variants&&... __variants)

> >>> +    {

> >>> +      if constexpr(__use_index)

> >>> +        return __detail::__variant::__variant_idx_cookie{};

> >>> +      else

> >>> +     return std::forward<_Visitor>(__visitor)(

> >> If I'm not misreading something, the new function will be usually

> >> compiled/optimized to something very small and isn't constexpr thus

> >> normally should be explicitly marked inline. Or the problem is the

> >> missing constexpr? (sorry, I didn't really study the new code)

> > The only use of this function is to compute its return type. It's

> > never called. I should probably comment on that...

>

> Oh, yes, now I see, a few lines below. That's clear enough, I think.


It's a bit novel, but happens to be much easier to write than
something using std::conditional or
some such. Traits like that may end up evaluating their template
arguments much sooner than
I'd like, but shoving it into a helper function with an if-constexpr
in it makes it trivial and I don't
need to worry about the validity of the branch taken, since it's not
instantiated. This is a new
use case for if-constexpr even for me, but it's a very nice bonus
ability in that already shining-fabulous
language facility. :)
Ville Voutilainen April 1, 2019, 8:51 a.m. | #6
On Mon, 1 Apr 2019 at 11:50, Ville Voutilainen
<ville.voutilainen@gmail.com> wrote:
> in it makes it trivial and I don't

> need to worry about the validity of the branch taken, since it's not

> instantiated. This is a new


I mean the branch *not* taken. :)
Ville Voutilainen April 1, 2019, 9:52 a.m. | #7
On Mon, 1 Apr 2019 at 11:45, Ville Voutilainen
<ville.voutilainen@gmail.com> wrote:
>

> On Sat, 30 Mar 2019 at 20:00, Ville Voutilainen

> <ville.voutilainen@gmail.com> wrote:

> >

> > This patch makes assignments correct, because they need to

> > match indices instead of types. In addition, we cut down the

> > codegen size. The symbols are longer than before, the the amount

> > of them is roughly the same, so there's no longer an explosion

> > in their amount.

> >

> > Relops are the last bit in these fixes, I'll fix them during the weekend.

>

> Here. This does produce 17 symbols instead of 9 for a test with a

> single operator== comparison.

> But it's not 47 like it is with the code before this patch.


Jonathan: I consider this good enough to ship; it doesn't explode the
symbols too much and
nicely gets rid of half of the runtime ifs for valueless state and
index. That's really the perf bonus that visitation
buys, and for swap and relops there is less need to do other
inquiries, although there is that
check for same-index, which is now a run-time check between a
completely-runtime value
and a compile-time constant as opposed to a run-time check between two
completely-runtime
values. Later, as a possible optimization, we can see whether swap and
relops can be made
to use a different generated jump table with just maybe twelve
entries, and if we can dispatch
into it without other additional branches, which I'm not entirely sure we can.
Jonathan Wakely April 1, 2019, 11:55 a.m. | #8
On 01/04/19 11:45 +0300, Ville Voutilainen wrote:
>@@ -570,45 +574,44 @@ namespace __variant

>       operator=(const _Copy_assign_base& __rhs)

> 	  noexcept(_Traits<_Types...>::_S_nothrow_copy_assign)

>       {

>-	__do_visit([this, &__rhs](auto&& __this_mem, auto&& __rhs_mem) mutable

>-		   -> __detail::__variant::__variant_cookie

>+	__do_visit<__visit_with_index>([this](auto&& __rhs_mem,

>+					      auto __rhs_index) mutable

>+	    -> __detail::__variant::__variant_idx_cookie

> 	  {

>-	    if constexpr (is_same_v<

>-			    remove_reference_t<decltype(__this_mem)>,

>-			    remove_reference_t<decltype(__rhs_mem)>>)

>+	    if constexpr (__rhs_index != variant_npos)

> 	      {

>-		if constexpr (!is_same_v<

>-			        remove_reference_t<decltype(__rhs_mem)>,

>-			        __variant_cookie>)

>-		  __this_mem = __rhs_mem;

>-	      }

>-	    else

>-	      {

>-		if constexpr (!is_same_v<

>-			        remove_reference_t<decltype(__rhs_mem)>,

>-			        __variant_cookie>)

>+		if (this->_M_index == __rhs_index)

> 		  {

>-		    using __rhs_type =

>-		      remove_reference_t<decltype(__rhs_mem)>;

>-		    if constexpr (is_nothrow_copy_constructible_v<__rhs_type>

>-		      || !is_nothrow_move_constructible_v<__rhs_type>)

>+		    if constexpr (__rhs_index != variant_npos)

> 		      {

>-			this->_M_destructive_copy(__rhs._M_index, __rhs_mem);

>+			auto& __this_mem =

>+			  __get<__rhs_index>(*this);


Qualify this as __variant::__get please.

>+			if constexpr (is_same_v<

>+				      remove_reference_t<decltype(__this_mem)>,

>+				      remove_reference_t<decltype(__rhs_mem)>>)

>+			  __this_mem = __rhs_mem;

> 		      }

>+		  }

>+		else

>+		  {

>+		    using __rhs_type =

>+		      remove_reference_t<decltype(__rhs_mem)>;

>+		    if constexpr

>+		      (is_nothrow_copy_constructible_v<__rhs_type>

>+		       || !is_nothrow_move_constructible_v<__rhs_type>)

>+			this->_M_destructive_copy(__rhs_index, __rhs_mem);

> 		    else

> 		      {

> 			auto __tmp(__rhs_mem);

>-			this->_M_destructive_move(__rhs._M_index,

>+			this->_M_destructive_move(__rhs_index,

> 						  std::move(__tmp));

> 		      }

> 		  }

>-		else

>-		  {

>-		    this->_M_reset();

>-		  }

> 	      }

>-	  return {};

>-	}, __variant_cast<_Types...>(*this), __variant_cast<_Types...>(__rhs));

>+	    else

>+	      this->_M_reset();

>+	    return {};

>+	  }, __variant_cast<_Types...>(__rhs));

> 	__glibcxx_assert(this->_M_index == __rhs._M_index);

> 	return *this;

>       }

>@@ -641,25 +644,32 @@ namespace __variant

>       operator=(_Move_assign_base&& __rhs)

> 	  noexcept(_Traits<_Types...>::_S_nothrow_move_assign)

>       {

>-	__do_visit([this, &__rhs](auto&& __this_mem, auto&& __rhs_mem) mutable

>-		   -> __detail::__variant::__variant_cookie

>+	__do_visit<__visit_with_index>([this](auto&& __rhs_mem,

>+					      auto __rhs_index) mutable

>+	    -> __detail::__variant::__variant_idx_cookie

> 	  {

>-	    if constexpr (is_same_v<

>-			    remove_reference_t<decltype(__this_mem)>,

>-			    remove_reference_t<decltype(__rhs_mem)>>)

>+	    if constexpr (__rhs_index != variant_npos)

> 	      {

>-		if constexpr (!is_same_v<

>-			        remove_reference_t<decltype(__rhs_mem)>,

>-			        __variant_cookie>)

>-		  __this_mem = std::move(__rhs_mem);

>+		if (this->_M_index == __rhs_index)

>+		  {

>+		    if constexpr (__rhs_index != variant_npos)

>+		      {

>+			auto& __this_mem =

>+			  __get<__rhs_index>(*this);


And here.

>+			if constexpr (is_same_v<

>+				      remove_reference_t<decltype(__this_mem)>,

>+				      remove_reference_t<decltype(__rhs_mem)>>)

>+			  __this_mem = std::move(__rhs_mem);

>+		      }

>+		  }

>+		else

>+		  this->_M_destructive_move(__rhs_index,

>+					    std::move(__rhs_mem));

> 	      }

> 	    else

>-	      {

>-		auto __tmp(std::move(__rhs_mem));

>-		this->_M_destructive_move(__rhs._M_index, std::move(__tmp));

>-	      }

>-	  return {};

>-	}, __variant_cast<_Types...>(*this), __variant_cast<_Types...>(__rhs));

>+	      this->_M_reset();

>+	    return {};

>+	  }, __variant_cast<_Types...>(__rhs));

> 	__glibcxx_assert(this->_M_index == __rhs._M_index);

> 	return *this;

>       }

>@@ -1082,25 +1099,25 @@ namespace __variant

> 				 const variant<_Types...>& __rhs) \

>     { \

>       bool __ret = true; \

>-      __do_visit([&__ret, &__lhs, __rhs] \

>-		 (auto&& __this_mem, auto&& __rhs_mem) mutable	\

>-		   -> __detail::__variant::__variant_cookie \

>+      __do_visit<__detail::__variant::__visit_with_index>( \

>+        [&__ret, &__lhs, __rhs] \

>+		 (auto&& __rhs_mem, auto __rhs_index) mutable \

>+		   -> __detail::__variant::__variant_idx_cookie \

>         { \

>-	  if constexpr (!is_same_v< \

>-			  remove_reference_t<decltype(__this_mem)>, \

>-			  remove_reference_t<decltype(__rhs_mem)>> \

>-			|| is_same_v<decltype(__this_mem), \

>-			             __detail::__variant::__variant_cookie>) \

>-	    __ret = (__lhs.index() + 1) __OP (__rhs.index() + 1); \

>-	  else if constexpr (is_same_v< \

>-			       remove_reference_t<decltype(__this_mem)>, \

>-			       remove_reference_t<decltype(__rhs_mem)>> \

>-                             && !is_same_v< \

>-	                          remove_reference_t<decltype(__this_mem)>, \

>-				  __detail::__variant::__variant_cookie>) \

>-	    __ret = __this_mem __OP __rhs_mem; \

>+	  if constexpr (__rhs_index != variant_npos) \

>+	    { \

>+	      if (__lhs.index() == __rhs_index) \

>+	        { \

>+		  auto& __this_mem = get<__rhs_index>(__lhs); \


And std::get here.

>+                  __ret = __this_mem __OP __rhs_mem; \

>+                } \

>+	      else \

>+		__ret = (__lhs.index() + 1) __OP (__rhs_index + 1); \

>+            } \

>+          else \

>+            __ret = (__lhs.index() + 1) __OP (__rhs_index + 1); \

> 	  return {}; \

>-	}, __lhs, __rhs); \

>+	}, __rhs); \

>       return __ret; \

>     } \

> \

>@@ -1402,51 +1419,47 @@ namespace __variant

>       noexcept((__is_nothrow_swappable<_Types>::value && ...)

> 	       && is_nothrow_move_constructible_v<variant>)

>       {

>-	__do_visit([this, &__rhs](auto&& __this_mem, auto&& __rhs_mem) mutable

>-		   -> __detail::__variant::__variant_cookie

>+	__do_visit<__detail::__variant::__visit_with_index>(

>+	  [this, &__rhs](auto&& __rhs_mem,

>+			 auto __rhs_index) mutable

>+	    -> __detail::__variant::__variant_idx_cookie

> 	  {

>-	    if constexpr (is_same_v<

>-			    remove_reference_t<decltype(__this_mem)>,

>-			    remove_reference_t<decltype(__rhs_mem)>>)

>+	    if constexpr (__rhs_index != variant_npos)

> 	      {

>-		if constexpr (!is_same_v<

>-			        remove_reference_t<decltype(__rhs_mem)>,

>-			        __detail::__variant::__variant_cookie>)

>+		if (this->index() == __rhs_index)

> 		  {

>+		    auto& __this_mem =

>+		      get<__rhs_index>(*this);


And here.

OK with those four qualifications, thanks very much.
Jonathan Wakely April 1, 2019, 11:55 a.m. | #9
On 01/04/19 12:52 +0300, Ville Voutilainen wrote:
>On Mon, 1 Apr 2019 at 11:45, Ville Voutilainen

><ville.voutilainen@gmail.com> wrote:

>>

>> On Sat, 30 Mar 2019 at 20:00, Ville Voutilainen

>> <ville.voutilainen@gmail.com> wrote:

>> >

>> > This patch makes assignments correct, because they need to

>> > match indices instead of types. In addition, we cut down the

>> > codegen size. The symbols are longer than before, the the amount

>> > of them is roughly the same, so there's no longer an explosion

>> > in their amount.

>> >

>> > Relops are the last bit in these fixes, I'll fix them during the weekend.

>>

>> Here. This does produce 17 symbols instead of 9 for a test with a

>> single operator== comparison.

>> But it's not 47 like it is with the code before this patch.

>

>Jonathan: I consider this good enough to ship; it doesn't explode the

>symbols too much and

>nicely gets rid of half of the runtime ifs for valueless state and

>index. That's really the perf bonus that visitation

>buys, and for swap and relops there is less need to do other

>inquiries, although there is that

>check for same-index, which is now a run-time check between a

>completely-runtime value

>and a compile-time constant as opposed to a run-time check between two

>completely-runtime

>values. Later, as a possible optimization, we can see whether swap and

>relops can be made

>to use a different generated jump table with just maybe twelve

>entries, and if we can dispatch

>into it without other additional branches, which I'm not entirely sure we can.


Yes, this is a very satisfactory improvement in codegen.

Patch

diff --git a/libstdc++-v3/include/std/variant b/libstdc++-v3/include/std/variant
index 7fd6947..3ee1cbd 100644
--- a/libstdc++-v3/include/std/variant
+++ b/libstdc++-v3/include/std/variant
@@ -138,7 +138,7 @@  namespace __variant
     constexpr variant_alternative_t<_Np, variant<_Types...>> const&&
     get(const variant<_Types...>&&);
 
-  template<typename _Visitor, typename... _Variants>
+  template<bool __use_index=false, typename _Visitor, typename... _Variants>
     constexpr decltype(auto)
     __do_visit(_Visitor&& __visitor, _Variants&&... __variants);
 
@@ -175,6 +175,10 @@  namespace __variant
 
   // used for raw visitation
   struct __variant_cookie {};
+  // used for raw visitation with indices passed in
+  struct __variant_idx_cookie {};
+  // a more explanatory name than 'true'
+  inline constexpr auto __visit_with_index = bool_constant<true>{};
 
   // _Uninitialized<T> is guaranteed to be a literal type, even if T is not.
   // We have to do this, because [basic.types]p10.5.3 (n4606) is not implemented
@@ -570,45 +574,44 @@  namespace __variant
       operator=(const _Copy_assign_base& __rhs)
 	  noexcept(_Traits<_Types...>::_S_nothrow_copy_assign)
       {
-	__do_visit([this, &__rhs](auto&& __this_mem, auto&& __rhs_mem) mutable
-		   -> __detail::__variant::__variant_cookie
+	__do_visit<__visit_with_index>([this](auto&& __rhs_mem,
+					      auto __rhs_index) mutable
+	    -> __detail::__variant::__variant_idx_cookie
 	  {
-	    if constexpr (is_same_v<
-			    remove_reference_t<decltype(__this_mem)>,
-			    remove_reference_t<decltype(__rhs_mem)>>)
+	    if constexpr (__rhs_index != variant_npos)
 	      {
-		if constexpr (!is_same_v<
-			        remove_reference_t<decltype(__rhs_mem)>,
-			        __variant_cookie>)
-		  __this_mem = __rhs_mem;
-	      }
-	    else
-	      {
-		if constexpr (!is_same_v<
-			        remove_reference_t<decltype(__rhs_mem)>,
-			        __variant_cookie>)
+		if (this->_M_index == __rhs_index)
 		  {
-		    using __rhs_type =
-		      remove_reference_t<decltype(__rhs_mem)>;
-		    if constexpr (is_nothrow_copy_constructible_v<__rhs_type>
-		      || !is_nothrow_move_constructible_v<__rhs_type>)
+		    if constexpr (__rhs_index != variant_npos)
 		      {
-			this->_M_destructive_copy(__rhs._M_index, __rhs_mem);
+			auto& __this_mem =
+			  __get<__rhs_index>(*this);
+			if constexpr (is_same_v<
+				      remove_reference_t<decltype(__this_mem)>,
+				      remove_reference_t<decltype(__rhs_mem)>>)
+			  __this_mem = __rhs_mem;
 		      }
+		  }
+		else
+		  {
+		    using __rhs_type =
+		      remove_reference_t<decltype(__rhs_mem)>;
+		    if constexpr
+		      (is_nothrow_copy_constructible_v<__rhs_type>
+		       || !is_nothrow_move_constructible_v<__rhs_type>)
+			this->_M_destructive_copy(__rhs_index, __rhs_mem);
 		    else
 		      {
 			auto __tmp(__rhs_mem);
-			this->_M_destructive_move(__rhs._M_index,
+			this->_M_destructive_move(__rhs_index,
 						  std::move(__tmp));
 		      }
 		  }
-		else
-		  {
-		    this->_M_reset();
-		  }
 	      }
-	  return {};
-	}, __variant_cast<_Types...>(*this), __variant_cast<_Types...>(__rhs));
+	    else
+	      this->_M_reset();
+	    return {};
+	  }, __variant_cast<_Types...>(__rhs));
 	__glibcxx_assert(this->_M_index == __rhs._M_index);
 	return *this;
       }
@@ -641,25 +644,32 @@  namespace __variant
       operator=(_Move_assign_base&& __rhs)
 	  noexcept(_Traits<_Types...>::_S_nothrow_move_assign)
       {
-	__do_visit([this, &__rhs](auto&& __this_mem, auto&& __rhs_mem) mutable
-		   -> __detail::__variant::__variant_cookie
+	__do_visit<__visit_with_index>([this](auto&& __rhs_mem,
+					      auto __rhs_index) mutable
+	    -> __detail::__variant::__variant_idx_cookie
 	  {
-	    if constexpr (is_same_v<
-			    remove_reference_t<decltype(__this_mem)>,
-			    remove_reference_t<decltype(__rhs_mem)>>)
+	    if constexpr (__rhs_index != variant_npos)
 	      {
-		if constexpr (!is_same_v<
-			        remove_reference_t<decltype(__rhs_mem)>,
-			        __variant_cookie>)
-		  __this_mem = std::move(__rhs_mem);
+		if (this->_M_index == __rhs_index)
+		  {
+		    if constexpr (__rhs_index != variant_npos)
+		      {
+			auto& __this_mem =
+			  __get<__rhs_index>(*this);
+			if constexpr (is_same_v<
+				      remove_reference_t<decltype(__this_mem)>,
+				      remove_reference_t<decltype(__rhs_mem)>>)
+			  __this_mem = std::move(__rhs_mem);
+		      }
+		  }
+		else
+		  this->_M_destructive_move(__rhs_index,
+					    std::move(__rhs_mem));
 	      }
 	    else
-	      {
-		auto __tmp(std::move(__rhs_mem));
-		this->_M_destructive_move(__rhs._M_index, std::move(__tmp));
-	      }
-	  return {};
-	}, __variant_cast<_Types...>(*this), __variant_cast<_Types...>(__rhs));
+	      this->_M_reset();
+	    return {};
+	  }, __variant_cast<_Types...>(__rhs));
 	__glibcxx_assert(this->_M_index == __rhs._M_index);
 	return *this;
       }
@@ -777,7 +787,8 @@  namespace __variant
       : bool_constant<__never_valueless<_Types...>()> {};
 
     static constexpr bool value =
-      is_same_v<_Maybe_variant_cookie, __variant_cookie>
+      (is_same_v<_Maybe_variant_cookie, __variant_cookie>
+       || is_same_v<_Maybe_variant_cookie, __variant_idx_cookie>)
       && !_Variant_never_valueless<__remove_cvref_t<_Variant>>::value;
   };
 
@@ -925,7 +936,13 @@  namespace __variant
       static constexpr decltype(auto)
       __visit_invoke(_Visitor&& __visitor, _Variants... __vars)
       {
-	return std::__invoke(std::forward<_Visitor>(__visitor),
+	if constexpr (is_same_v<_Result_type, __variant_idx_cookie>)
+	  return std::__invoke(std::forward<_Visitor>(__visitor),
+	    __element_by_index_or_cookie<__indices>(
+	      std::forward<_Variants>(__vars))...,
+	      integral_constant<size_t, __indices>()...);
+	else
+	  return std::__invoke(std::forward<_Visitor>(__visitor),
 	    __element_by_index_or_cookie<__indices>(
 	      std::forward<_Variants>(__vars))...);
       }
@@ -1402,51 +1419,47 @@  namespace __variant
       noexcept((__is_nothrow_swappable<_Types>::value && ...)
 	       && is_nothrow_move_constructible_v<variant>)
       {
-	__do_visit([this, &__rhs](auto&& __this_mem, auto&& __rhs_mem) mutable
-		   -> __detail::__variant::__variant_cookie
+	__do_visit<__detail::__variant::__visit_with_index>(
+	  [this, &__rhs](auto&& __rhs_mem,
+			 auto __rhs_index) mutable
+	    -> __detail::__variant::__variant_idx_cookie
 	  {
-	    if constexpr (is_same_v<
-			    remove_reference_t<decltype(__this_mem)>,
-			    remove_reference_t<decltype(__rhs_mem)>>)
+	    if constexpr (__rhs_index != variant_npos)
 	      {
-		if constexpr (!is_same_v<
-			        remove_reference_t<decltype(__rhs_mem)>,
-			        __detail::__variant::__variant_cookie>)
+		if (this->index() == __rhs_index)
 		  {
+		    auto& __this_mem =
+		      get<__rhs_index>(*this);
 		    using std::swap;
 		    swap(__this_mem, __rhs_mem);
 		  }
+		else
+		  {
+		    if (this->index() != variant_npos)
+		      {
+			auto __tmp(std::move(__rhs_mem));
+			__rhs = std::move(*this);
+			this->_M_destructive_move(__rhs_index,
+						  std::move(__tmp));
+		      }
+		    else
+		      {
+			this->_M_destructive_move(__rhs_index,
+						  std::move(__rhs_mem));
+			__rhs._M_reset();
+		      }
+		  }
 	      }
 	    else
 	      {
-		if constexpr (is_same_v<
-			        remove_reference_t<decltype(__this_mem)>,
-			        __detail::__variant::__variant_cookie>)
+		if (this->index() != variant_npos)
 		  {
-		    this->_M_destructive_move(__rhs.index(),
-					      std::move(__rhs_mem));
-		    __rhs._M_reset();
-		  }
-		else if constexpr (is_same_v<
-			             remove_reference_t<decltype(__rhs_mem)>,
-			             __detail::__variant::__variant_cookie>)
-		  {
-		    __rhs._M_destructive_move(this->index(),
-					      std::move(__this_mem));
+		    __rhs = std::move(*this);
 		    this->_M_reset();
 		  }
-		else
-		  {
-		    auto __tmp(std::move(__rhs_mem));
-		    auto __idx = __rhs.index();
-		    __rhs._M_destructive_move(this->index(),
-					      std::move(__this_mem));
-		    this->_M_destructive_move(__idx,
-					      std::move(__tmp));
-		  }
 	      }
-	  return {};
-	}, *this, __rhs);
+	    return {};
+	  }, __rhs);
       }
 
     private:
@@ -1523,13 +1536,25 @@  namespace __variant
       return __detail::__variant::__get<_Np>(std::move(__v));
     }
 
-  template<typename _Visitor, typename... _Variants>
+  template<bool __use_index, typename _Visitor, typename... _Variants>
+    decltype(auto)
+    __visitor_result_type(_Visitor&& __visitor, _Variants&&... __variants)
+    {
+      if constexpr(__use_index)
+        return __detail::__variant::__variant_idx_cookie{};
+      else
+	return std::forward<_Visitor>(__visitor)(
+	  std::get<0>(std::forward<_Variants>(__variants))...);
+    }
+
+  template<bool __use_index, typename _Visitor, typename... _Variants>
     constexpr decltype(auto)
     __do_visit(_Visitor&& __visitor, _Variants&&... __variants)
     {
       using _Result_type =
-	decltype(std::forward<_Visitor>(__visitor)(
-	    std::get<0>(std::forward<_Variants>(__variants))...));
+	decltype(__visitor_result_type<__use_index>(
+	           std::forward<_Visitor>(__visitor),
+	           std::forward<_Variants>(__variants)...));
 
       constexpr auto& __vtable = __detail::__variant::__gen_vtable<
 	_Result_type, _Visitor&&, _Variants&&...>::_S_vtable;