std::forward_list optim for always equal allocator

Hi

     Here is the patch to implement the always equal alloc optimization 
for forward_list. With this version there is no abi issue.

     I also prefer to implement the _Fwd_list_node_base move operator 
for consistency with the move constructor and used it where applicable.


     * include/bits/forward_list.h
     (_Fwd_list_node_base& operator=(_Fwd_list_node_base&&)): Implement.
     (_Fwd_list_impl(_Fwd_list_impl&&, _Node_alloc_type&&)): New.
     (_Fwd_list_base(_Fwd_list_base&&, _Node_alloc_type&&, std::true_type)):
     New, use latter.
     (forward_list(forward_list&&, _Node_alloc_type&&, std::false_type)):
     New.
     (forward_list(forward_list&&, _Node_alloc_type&&, std::true_type)):
     New.
     (forward_list(forward_list&&, const _Alloc&)): Adapt to use latters.
     * include/bits/forward_list.tcc
     (_Fwd_list_base(_Fwd_list_base&&, _Node_alloc_type&&)): Adapt to use
     _M_impl._M_head move assignment.
     (forward_list<>::merge(forward_list<>&&, _Comp)): Likewise.

Tested under Linux x86_64, ok to commit ?

François

2017-07-17 22:10 GMT+02:00 François Dumont <frs.dumont@gmail.com>:
> Hi
>
>     Here is the patch to implement the always equal alloc optimization for
> forward_list. With this version there is no abi issue.
>
>     I also prefer to implement the _Fwd_list_node_base move operator for
> consistency with the move constructor and used it where applicable.
>
>
>     * include/bits/forward_list.h
>     (_Fwd_list_node_base& operator=(_Fwd_list_node_base&&)): Implement.
>     (_Fwd_list_impl(_Fwd_list_impl&&, _Node_alloc_type&&)): New.
>     (_Fwd_list_base(_Fwd_list_base&&, _Node_alloc_type&&, std::true_type)):
>     New, use latter.
>     (forward_list(forward_list&&, _Node_alloc_type&&, std::false_type)):
>     New.
>     (forward_list(forward_list&&, _Node_alloc_type&&, std::true_type)):
>     New.
>     (forward_list(forward_list&&, const _Alloc&)): Adapt to use latters.
>     * include/bits/forward_list.tcc
>     (_Fwd_list_base(_Fwd_list_base&&, _Node_alloc_type&&)): Adapt to use
>     _M_impl._M_head move assignment.
>     (forward_list<>::merge(forward_list<>&&, _Comp)): Likewise.
>
> Tested under Linux x86_64, ok to commit ?

Out of curiosity: Shouldn't

_Fwd_list_node_base&
operator=(_Fwd_list_node_base&& __x);

be declared noexcept?

Thanks,

- Daniel

Hi

     Any news for this patch ?

     It does remove a constructor:
-        _Fwd_list_impl(const _Node_alloc_type& __a)
-        : _Node_alloc_type(__a), _M_head()

      It was already unused before the patch. Do you think it has ever 
been used and so do I need to restore it ?

     I eventually restore the _M_head() in _Fwd_list_impl constructors 
cause IMO it is the inline init of _M_next in _Fwd_list_node_base which 
should be removed. But I remember Jonathan that you didn't want to do so 
because gcc was not good enough in detecting usage of uninitialized 
variables, is it still true ?

François


On 17/07/2017 22:10, François Dumont wrote:
> Hi
>
>     Here is the patch to implement the always equal alloc optimization 
> for forward_list. With this version there is no abi issue.
>
>     I also prefer to implement the _Fwd_list_node_base move operator 
> for consistency with the move constructor and used it where applicable.
>
>
>     * include/bits/forward_list.h
>     (_Fwd_list_node_base& operator=(_Fwd_list_node_base&&)): Implement.
>     (_Fwd_list_impl(_Fwd_list_impl&&, _Node_alloc_type&&)): New.
>     (_Fwd_list_base(_Fwd_list_base&&, _Node_alloc_type&&, 
> std::true_type)):
>     New, use latter.
>     (forward_list(forward_list&&, _Node_alloc_type&&, std::false_type)):
>     New.
>     (forward_list(forward_list&&, _Node_alloc_type&&, std::true_type)):
>     New.
>     (forward_list(forward_list&&, const _Alloc&)): Adapt to use latters.
>     * include/bits/forward_list.tcc
>     (_Fwd_list_base(_Fwd_list_base&&, _Node_alloc_type&&)): Adapt to use
>     _M_impl._M_head move assignment.
>     (forward_list<>::merge(forward_list<>&&, _Comp)): Likewise.
>
> Tested under Linux x86_64, ok to commit ?
>
> François
>
diff --git a/libstdc++-v3/include/bits/forward_list.h b/libstdc++-v3/include/bits/forward_list.h
index 9d86fcc..772e9a0 100644
--- a/libstdc++-v3/include/bits/forward_list.h
+++ b/libstdc++-v3/include/bits/forward_list.h
@@ -54,6 +54,20 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
   struct _Fwd_list_node_base
   {
     _Fwd_list_node_base() = default;
+    _Fwd_list_node_base(_Fwd_list_node_base&& __x) noexcept
+      : _M_next(__x._M_next)
+    { __x._M_next = nullptr; }
+
+    _Fwd_list_node_base(const _Fwd_list_node_base&) = delete;
+    _Fwd_list_node_base& operator=(const _Fwd_list_node_base&) = delete;
+
+    _Fwd_list_node_base&
+    operator=(_Fwd_list_node_base&& __x) noexcept
+    {
+      _M_next = __x._M_next;
+      __x._M_next = nullptr;
+      return *this;
+    }
 
     _Fwd_list_node_base* _M_next = nullptr;
 
@@ -68,7 +82,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	  __end->_M_next = _M_next;
 	}
       else
-	__begin->_M_next = 0;
+	__begin->_M_next = nullptr;
       _M_next = __keep;
       return __end;
     }
@@ -173,7 +187,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	if (_M_node)
 	  return _Fwd_list_iterator(_M_node->_M_next);
 	else
-          return _Fwd_list_iterator(0);
+	  return _Fwd_list_iterator(nullptr);
       }
 
       _Fwd_list_node_base* _M_node;
@@ -244,7 +258,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	if (this->_M_node)
 	  return _Fwd_list_const_iterator(_M_node->_M_next);
 	else
-          return _Fwd_list_const_iterator(0);
+	  return _Fwd_list_const_iterator(nullptr);
       }
 
       const _Fwd_list_node_base* _M_node;
@@ -285,11 +299,14 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	_Fwd_list_node_base _M_head;
 
 	_Fwd_list_impl()
+	  noexcept( noexcept(_Node_alloc_type()) )
 	: _Node_alloc_type(), _M_head()
 	{ }
 
-        _Fwd_list_impl(const _Node_alloc_type& __a)
-        : _Node_alloc_type(__a), _M_head()
+	_Fwd_list_impl(_Fwd_list_impl&&) = default;
+
+	_Fwd_list_impl(_Fwd_list_impl&& __fl, _Node_alloc_type&& __a)
+	: _Node_alloc_type(std::move(__a)), _M_head(std::move(__fl._M_head))
 	{ }
 
 	_Fwd_list_impl(_Node_alloc_type&& __a)
@@ -312,26 +329,26 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       _M_get_Node_allocator() const noexcept
       { return this->_M_impl; }
 
-      _Fwd_list_base()
-      : _M_impl() { }
+      _Fwd_list_base() = default;
 
       _Fwd_list_base(_Node_alloc_type&& __a)
       : _M_impl(std::move(__a)) { }
 
+      // When allocators are always equal.
+      _Fwd_list_base(_Fwd_list_base&& __lst, _Node_alloc_type&& __a,
+		     std::true_type)
+      : _M_impl(std::move(__lst._M_impl), std::move(__a))
+      { }
+
+      // When allocators are not always equal.
       _Fwd_list_base(_Fwd_list_base&& __lst, _Node_alloc_type&& __a);
 
-      _Fwd_list_base(_Fwd_list_base&& __lst)
-      : _M_impl(std::move(__lst._M_get_Node_allocator()))
-      {
-	this->_M_impl._M_head._M_next = __lst._M_impl._M_head._M_next;
-	__lst._M_impl._M_head._M_next = 0;
-      }
+      _Fwd_list_base(_Fwd_list_base&&) = default;
 
       ~_Fwd_list_base()
-      { _M_erase_after(&_M_impl._M_head, 0); }
+      { _M_erase_after(&_M_impl._M_head, nullptr); }
 
     protected:
-
       _Node*
       _M_get_node()
       {
@@ -437,10 +454,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       /**
        *  @brief  Creates a %forward_list with no elements.
        */
-      forward_list()
-      noexcept(is_nothrow_default_constructible<_Node_alloc_type>::value)
-      : _Base()
-      { }
+      forward_list() = default;
 
       /**
        *  @brief  Creates a %forward_list with no elements.
@@ -451,7 +465,6 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       : _Base(_Node_alloc_type(__al))
       { }
 
-
       /**
        *  @brief  Copy constructor with allocator argument.
        *  @param  __list  Input list to copy.
@@ -461,14 +474,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       : _Base(_Node_alloc_type(__al))
       { _M_range_initialize(__list.begin(), __list.end()); }
 
-      /**
-       *  @brief  Move constructor with allocator argument.
-       *  @param  __list  Input list to move.
-       *  @param  __al    An allocator object.
-       */
-      forward_list(forward_list&& __list, const _Alloc& __al)
-      noexcept(_Node_alloc_traits::_S_always_equal())
-      : _Base(std::move(__list), _Node_alloc_type(__al))
+    private:
+      forward_list(forward_list&& __list, _Node_alloc_type&& __al,
+		   std::false_type)
+      : _Base(std::move(__list), std::move(__al))
       {
 	// If __list is not empty it means its allocator is not equal to __a,
 	// so we need to move from each element individually.
@@ -477,6 +486,24 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 		     std::__make_move_if_noexcept_iterator(__list.end()));
       }
 
+      forward_list(forward_list&& __list, _Node_alloc_type&& __al,
+		   std::true_type)
+      noexcept
+      : _Base(std::move(__list), _Node_alloc_type(__al), std::true_type{})
+      { }
+
+    public:
+      /**
+       *  @brief  Move constructor with allocator argument.
+       *  @param  __list  Input list to move.
+       *  @param  __al    An allocator object.
+       */
+      forward_list(forward_list&& __list, const _Alloc& __al)
+      noexcept(_Node_alloc_traits::_S_always_equal())
+      : forward_list(std::move(__list), _Node_alloc_type(__al),
+		     typename _Node_alloc_traits::is_always_equal{})
+      { }
+
       /**
        *  @brief  Creates a %forward_list with default constructed elements.
        *  @param  __n   The number of elements to initially create.
@@ -533,15 +560,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
       /**
        *  @brief  The %forward_list move constructor.
-       *  @param  __list  A %forward_list of identical element and allocator
-       *                  types.
+       *  @param  A %forward_list of identical element and allocator types.
        *
-       *  The newly-created %forward_list contains the exact contents of @a
-       *  __list. The contents of @a __list are a valid, but unspecified
-       *  %forward_list.
+       *  The newly-created %forward_list contains the exact contents of the
+       *  moved instance. The contents of the moved instance are a valid, but
+       *  unspecified %forward_list.
        */
-      forward_list(forward_list&& __list) noexcept
-      : _Base(std::move(__list)) { }
+      forward_list(forward_list&&) = default;
 
       /**
        *  @brief  Builds a %forward_list from an initializer_list
@@ -707,7 +732,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        */
       iterator
       end() noexcept
-      { return iterator(0); }
+      { return iterator(nullptr); }
 
       /**
        *  Returns a read-only iterator that points one past the last
@@ -716,7 +741,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        */
       const_iterator
       end() const noexcept
-      { return const_iterator(0); }
+      { return const_iterator(nullptr); }
 
       /**
        *  Returns a read-only (constant) iterator that points to the
@@ -743,7 +768,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        */
       const_iterator
       cend() const noexcept
-      { return const_iterator(0); }
+      { return const_iterator(nullptr); }
 
       /**
        *  Returns true if the %forward_list is empty.  (Thus begin() would
@@ -751,7 +776,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        */
       bool
       empty() const noexcept
-      { return this->_M_impl._M_head._M_next == 0; }
+      { return this->_M_impl._M_head._M_next == nullptr; }
 
       /**
        *  Returns the largest possible number of elements of %forward_list.
@@ -1056,7 +1081,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        */
       void
       clear() noexcept
-      { this->_M_erase_after(&this->_M_impl._M_head, 0); }
+      { this->_M_erase_after(&this->_M_impl._M_head, nullptr); }
 
       // 23.3.4.6 forward_list operations:
 
diff --git a/libstdc++-v3/include/bits/forward_list.tcc b/libstdc++-v3/include/bits/forward_list.tcc
index 64bd9c4..f13e959 100644
--- a/libstdc++-v3/include/bits/forward_list.tcc
+++ b/libstdc++-v3/include/bits/forward_list.tcc
@@ -41,12 +41,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
     : _M_impl(std::move(__a))
     {
       if (__lst._M_get_Node_allocator() == _M_get_Node_allocator())
-	{
-	  this->_M_impl._M_head._M_next = __lst._M_impl._M_head._M_next;
-	  __lst._M_impl._M_head._M_next = 0;
-	}
-      else
-	this->_M_impl._M_head._M_next = 0;
+	this->_M_impl._M_head = std::move(__lst._M_impl._M_head);
     }
 
   template<typename _Tp, typename _Alloc>
@@ -364,11 +359,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 					__list._M_impl._M_head._M_next);
 	    __node = __node->_M_next;
 	  }
+
 	if (__list._M_impl._M_head._M_next)
-          {
-            __node->_M_next = __list._M_impl._M_head._M_next;
-            __list._M_impl._M_head._M_next = 0;
-          }
+	  *__node = std::move(__list._M_impl._M_head);
       }
 
   template<typename _Tp, typename _Alloc>
@@ -399,7 +392,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       forward_list<_Tp, _Alloc>::
       sort(_Comp __comp)
       {
-        // If `next' is 0, return immediately.
+	// If `next' is nullptr, return immediately.
 	_Node* __list = static_cast<_Node*>(this->_M_impl._M_head._M_next);
 	if (!__list)
 	  return;
@@ -409,8 +402,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	while (1)
 	  {
 	    _Node* __p = __list;
-            __list = 0;
-            _Node* __tail = 0;
+	    __list = nullptr;
+	    _Node* __tail = nullptr;
 
 	    // Count number of merges we do in this pass.
 	    unsigned long __nmerges = 0;
@@ -478,7 +471,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 		// Now p has stepped `insize' places along, and q has too.
 		__p = __q;
 	      }
-            __tail->_M_next = 0;
+	    __tail->_M_next = nullptr;
 
 	    // If we have done only one merge, we're finished.
 	    // Allow for nmerges == 0, the empty list case.
@@ -498,4 +491,3 @@ _GLIBCXX_END_NAMESPACE_VERSION
 } // namespace std
 
 #endif /* _FORWARD_LIST_TCC */
-
diff --git a/libstdc++-v3/testsuite/23_containers/forward_list/allocator/default_init.cc b/libstdc++-v3/testsuite/23_containers/forward_list/allocator/default_init.cc
new file mode 100644
index 0000000..b56c9cc
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/forward_list/allocator/default_init.cc
@@ -0,0 +1,67 @@
+// Copyright (C) 2017 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-do run { target c++11 } }
+// { dg-options "-O0" }
+// { dg-xfail-run-if "PR c++/65816" { *-*-* } }
+
+#include <forward_list>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+#include <ext/aligned_buffer.h>
+
+using T = int;
+
+using __gnu_test::default_init_allocator;
+
+void test01()
+{
+  typedef default_init_allocator<T> alloc_type;
+  typedef std::forward_list<T, alloc_type> test_type;
+
+  __gnu_cxx::__aligned_buffer<test_type> buf;
+  __builtin_memset(buf._M_addr(), ~0, sizeof(test_type));
+
+  test_type *tmp = ::new(buf._M_addr()) test_type;
+
+  VERIFY( tmp->get_allocator().state == 0 );
+
+  tmp->~test_type();
+}
+
+void test02()
+{
+  typedef default_init_allocator<T> alloc_type;
+  typedef std::forward_list<T, alloc_type> test_type;
+
+  __gnu_cxx::__aligned_buffer<test_type> buf;
+  __builtin_memset(buf._M_addr(), ~0, sizeof(test_type));
+
+  test_type *tmp = ::new(buf._M_addr()) test_type();
+
+  VERIFY( tmp->get_allocator().state == 0 );
+
+  tmp->~test_type();
+}
+
+int main()
+{
+  test01();
+  test02();
+  return 0;
+}

On 28/08/17 21:09 +0200, François Dumont wrote:
>Hi
>
>    Any news for this patch ?
>
>    It does remove a constructor:
>-        _Fwd_list_impl(const _Node_alloc_type& __a)
>-        : _Node_alloc_type(__a), _M_head()
>
>     It was already unused before the patch. Do you think it has ever 
>been used and so do I need to restore it ?
>
>    I eventually restore the _M_head() in _Fwd_list_impl constructors 
>cause IMO it is the inline init of _M_next in _Fwd_list_node_base 
>which should be removed. But I remember Jonathan that you didn't want 
>to do so because gcc was not good enough in detecting usage of 
>uninitialized variables, is it still true ?

Why should it be removed?

On 08/09/2017 18:19, Jonathan Wakely wrote:
> On 28/08/17 21:09 +0200, François Dumont wrote:
>> Hi
>>
>>    Any news for this patch ?
>>
>>    It does remove a constructor:
>> -        _Fwd_list_impl(const _Node_alloc_type& __a)
>> -        : _Node_alloc_type(__a), _M_head()
>>
>>     It was already unused before the patch. Do you think it has ever 
>> been used and so do I need to restore it ?
>>
>>    I eventually restore the _M_head() in _Fwd_list_impl constructors 
>> cause IMO it is the inline init of _M_next in _Fwd_list_node_base 
>> which should be removed. But I remember Jonathan that you didn't want 
>> to do so because gcc was not good enough in detecting usage of 
>> uninitialized variables, is it still true ?
>
> Why should it be removed?
>
>
>
When user declare a container iterator like that:

std::forward_list<int>::iterator it;

There is no reason to initialize it with a null node pointer. It is just 
an uninitialized iterator which is invalid to use except to initialize it.

I once proposed to do the same simplification for the unordered 
containers _Hash_node_base. But you said that detection of the usage of 
uninitialized variable is not good enough in gcc to leave variables 
uninitialized this way.

2017-09-11 7:12 GMT+02:00 François Dumont <frs.dumont@gmail.com>:
> When user declare a container iterator like that:
>
> std::forward_list<int>::iterator it;
>
> There is no reason to initialize it with a null node pointer. It is just an
> uninitialized iterator which is invalid to use except to initialize it.

While that is correct, for every forward iterator (and
std::forward_list<int>::iterator meets these requirements), it is also
required that a value-initialized iterator can be compared against
other initialized iterators, so this reduces the amount of freedom to
define a default constructor for such iterators even when used to
default-initialize. This is not meant as a showstopper argument, since
I have not fully understood of what you are planning, but just a
reminder.

- Daniel

On 11/09/17 07:44 +0200, Daniel Krügler wrote:
>2017-09-11 7:12 GMT+02:00 François Dumont <frs.dumont@gmail.com>:
>> When user declare a container iterator like that:
>>
>> std::forward_list<int>::iterator it;
>>
>> There is no reason to initialize it with a null node pointer. It is just an
>> uninitialized iterator which is invalid to use except to initialize it.
>
>While that is correct, for every forward iterator (and
>std::forward_list<int>::iterator meets these requirements), it is also
>required that a value-initialized iterator can be compared against
>other initialized iterators, so this reduces the amount of freedom to
>define a default constructor for such iterators even when used to
>default-initialize. This is not meant as a showstopper argument, since
>I have not fully understood of what you are planning, but just a
>reminder.

Right, which means that 

std::forward_list<int>::iterator it = {};

must initialize the node pointer to nullptr. If we remove the
initialization of _Fwd_list_iterator<T>::_M_node from the default
constructor then it would be left uninitialized.

But I'm confused, François was talking about removing the
initialization of _Fwd_list_node_base::_M_next, what has that got to
do with forward_list<T>::iterator? Thee is no node-base in the
iterator.

So I'm still wondering why the initialization of _M_next should be
removed.

On 11/09/2017 14:11, Jonathan Wakely wrote:
> On 11/09/17 07:44 +0200, Daniel Krügler wrote:
>> 2017-09-11 7:12 GMT+02:00 François Dumont <frs.dumont@gmail.com>:
>>> When user declare a container iterator like that:
>>>
>>> std::forward_list<int>::iterator it;
>>>
>>> There is no reason to initialize it with a null node pointer. It is 
>>> just an
>>> uninitialized iterator which is invalid to use except to initialize it.
>>
>> While that is correct, for every forward iterator (and
>> std::forward_list<int>::iterator meets these requirements), it is also
>> required that a value-initialized iterator can be compared against
>> other initialized iterators, so this reduces the amount of freedom to
>> define a default constructor for such iterators even when used to
>> default-initialize. This is not meant as a showstopper argument, since
>> I have not fully understood of what you are planning, but just a
>> reminder.
>
> Right, which means that
> std::forward_list<int>::iterator it = {};
>
> must initialize the node pointer to nullptr. If we remove the
> initialization of _Fwd_list_iterator<T>::_M_node from the default
> constructor then it would be left uninitialized.
>
> But I'm confused, François was talking about removing the
> initialization of _Fwd_list_node_base::_M_next, what has that got to
> do with forward_list<T>::iterator? Thee is no node-base in the
> iterator.
>
> So I'm still wondering why the initialization of _M_next should be
> removed.
>
Indeed, the iterator contains a _Fwd_list_node_base*.

So my remark was rather for the:

       _Fwd_list_iterator() noexcept
       : _M_node() { }

that could simply be

     _Fwd_list_iterator() = default;

no ?

François

2017-09-11 22:36 GMT+02:00 François Dumont <frs.dumont@gmail.com>:
[..]
> So my remark was rather for the:
>
>       _Fwd_list_iterator() noexcept
>       : _M_node() { }
>
> that could simply be
>
>     _Fwd_list_iterator() = default;
>
> no ?

Yes, that should be fine.

- Daniel

On 11/09/17 22:39 +0200, Daniel Krügler wrote:
>2017-09-11 22:36 GMT+02:00 François Dumont <frs.dumont@gmail.com>:
>[..]
>> So my remark was rather for the:
>>
>>       _Fwd_list_iterator() noexcept
>>       : _M_node() { }
>>
>> that could simply be
>>
>>     _Fwd_list_iterator() = default;
>>
>> no ?
>
>Yes, that should be fine.

I'm not sure there's much benefit to that change.

On 12/09/2017 00:10, Jonathan Wakely wrote:
> On 11/09/17 22:39 +0200, Daniel Krügler wrote:
>> 2017-09-11 22:36 GMT+02:00 François Dumont <frs.dumont@gmail.com>:
>> [..]
>>> So my remark was rather for the:
>>>
>>>       _Fwd_list_iterator() noexcept
>>>       : _M_node() { }
>>>
>>> that could simply be
>>>
>>>     _Fwd_list_iterator() = default;
>>>
>>> no ?
>>
>> Yes, that should be fine.
>
> I'm not sure there's much benefit to that change 
Sure, it would be a minor change.

Which is moreover not part of this patch proposal. Is the patch ok to 
commit ?

François

Gentle reminder for this patch.

I looked when the constructor got unused and I think it is back in June 
2015 in git commit:

commit debb6aabb771ed02cb7256a7719555e5fbd7d3f7
Author: redi <redi@138bc75d-0d04-0410-961f-82ee72b054a4>
Date:   Wed Jun 17 17:45:45 2015 +0000

         * include/bits/forward_list.h
         (_Fwd_list_base(const _Node_alloc_type&)): Change parameter to
         rvalue-reference.

If you fear abi breaking change I can restore it in a 
!_GLIBCXX_INLINE_VERSION section.

François


On 28/08/2017 21:09, François Dumont wrote:
> Hi
>
>     Any news for this patch ?
>
>     It does remove a constructor:
> -        _Fwd_list_impl(const _Node_alloc_type& __a)
> -        : _Node_alloc_type(__a), _M_head()
>
>      It was already unused before the patch. Do you think it has ever 
> been used and so do I need to restore it ?
>
>     I eventually restore the _M_head() in _Fwd_list_impl constructors 
> cause IMO it is the inline init of _M_next in _Fwd_list_node_base 
> which should be removed. But I remember Jonathan that you didn't want 
> to do so because gcc was not good enough in detecting usage of 
> uninitialized variables, is it still true ?
>
> François
>
>
> On 17/07/2017 22:10, François Dumont wrote:
>> Hi
>>
>>     Here is the patch to implement the always equal alloc 
>> optimization for forward_list. With this version there is no abi issue.
>>
>>     I also prefer to implement the _Fwd_list_node_base move operator 
>> for consistency with the move constructor and used it where applicable.
>>
>>
>>     * include/bits/forward_list.h
>>     (_Fwd_list_node_base& operator=(_Fwd_list_node_base&&)): Implement.
>>     (_Fwd_list_impl(_Fwd_list_impl&&, _Node_alloc_type&&)): New.
>>     (_Fwd_list_base(_Fwd_list_base&&, _Node_alloc_type&&, 
>> std::true_type)):
>>     New, use latter.
>>     (forward_list(forward_list&&, _Node_alloc_type&&, std::false_type)):
>>     New.
>>     (forward_list(forward_list&&, _Node_alloc_type&&, std::true_type)):
>>     New.
>>     (forward_list(forward_list&&, const _Alloc&)): Adapt to use latters.
>>     * include/bits/forward_list.tcc
>>     (_Fwd_list_base(_Fwd_list_base&&, _Node_alloc_type&&)): Adapt to use
>>     _M_impl._M_head move assignment.
>>     (forward_list<>::merge(forward_list<>&&, _Comp)): Likewise.
>>
>> Tested under Linux x86_64, ok to commit ?
>>
>> François
>>
>
diff --git a/libstdc++-v3/include/bits/forward_list.h b/libstdc++-v3/include/bits/forward_list.h
index 9d86fcc..772e9a0 100644
--- a/libstdc++-v3/include/bits/forward_list.h
+++ b/libstdc++-v3/include/bits/forward_list.h
@@ -54,6 +54,20 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
   struct _Fwd_list_node_base
   {
     _Fwd_list_node_base() = default;
+    _Fwd_list_node_base(_Fwd_list_node_base&& __x) noexcept
+      : _M_next(__x._M_next)
+    { __x._M_next = nullptr; }
+
+    _Fwd_list_node_base(const _Fwd_list_node_base&) = delete;
+    _Fwd_list_node_base& operator=(const _Fwd_list_node_base&) = delete;
+
+    _Fwd_list_node_base&
+    operator=(_Fwd_list_node_base&& __x) noexcept
+    {
+      _M_next = __x._M_next;
+      __x._M_next = nullptr;
+      return *this;
+    }
 
     _Fwd_list_node_base* _M_next = nullptr;
 
@@ -68,7 +82,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	  __end->_M_next = _M_next;
 	}
       else
-	__begin->_M_next = 0;
+	__begin->_M_next = nullptr;
       _M_next = __keep;
       return __end;
     }
@@ -173,7 +187,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	if (_M_node)
 	  return _Fwd_list_iterator(_M_node->_M_next);
 	else
-          return _Fwd_list_iterator(0);
+	  return _Fwd_list_iterator(nullptr);
       }
 
       _Fwd_list_node_base* _M_node;
@@ -244,7 +258,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	if (this->_M_node)
 	  return _Fwd_list_const_iterator(_M_node->_M_next);
 	else
-          return _Fwd_list_const_iterator(0);
+	  return _Fwd_list_const_iterator(nullptr);
       }
 
       const _Fwd_list_node_base* _M_node;
@@ -285,11 +299,14 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	_Fwd_list_node_base _M_head;
 
 	_Fwd_list_impl()
+	  noexcept( noexcept(_Node_alloc_type()) )
 	: _Node_alloc_type(), _M_head()
 	{ }
 
-        _Fwd_list_impl(const _Node_alloc_type& __a)
-        : _Node_alloc_type(__a), _M_head()
+	_Fwd_list_impl(_Fwd_list_impl&&) = default;
+
+	_Fwd_list_impl(_Fwd_list_impl&& __fl, _Node_alloc_type&& __a)
+	: _Node_alloc_type(std::move(__a)), _M_head(std::move(__fl._M_head))
 	{ }
 
 	_Fwd_list_impl(_Node_alloc_type&& __a)
@@ -312,26 +329,26 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       _M_get_Node_allocator() const noexcept
       { return this->_M_impl; }
 
-      _Fwd_list_base()
-      : _M_impl() { }
+      _Fwd_list_base() = default;
 
       _Fwd_list_base(_Node_alloc_type&& __a)
       : _M_impl(std::move(__a)) { }
 
+      // When allocators are always equal.
+      _Fwd_list_base(_Fwd_list_base&& __lst, _Node_alloc_type&& __a,
+		     std::true_type)
+      : _M_impl(std::move(__lst._M_impl), std::move(__a))
+      { }
+
+      // When allocators are not always equal.
       _Fwd_list_base(_Fwd_list_base&& __lst, _Node_alloc_type&& __a);
 
-      _Fwd_list_base(_Fwd_list_base&& __lst)
-      : _M_impl(std::move(__lst._M_get_Node_allocator()))
-      {
-	this->_M_impl._M_head._M_next = __lst._M_impl._M_head._M_next;
-	__lst._M_impl._M_head._M_next = 0;
-      }
+      _Fwd_list_base(_Fwd_list_base&&) = default;
 
       ~_Fwd_list_base()
-      { _M_erase_after(&_M_impl._M_head, 0); }
+      { _M_erase_after(&_M_impl._M_head, nullptr); }
 
     protected:
-
       _Node*
       _M_get_node()
       {
@@ -437,10 +454,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       /**
        *  @brief  Creates a %forward_list with no elements.
        */
-      forward_list()
-      noexcept(is_nothrow_default_constructible<_Node_alloc_type>::value)
-      : _Base()
-      { }
+      forward_list() = default;
 
       /**
        *  @brief  Creates a %forward_list with no elements.
@@ -451,7 +465,6 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       : _Base(_Node_alloc_type(__al))
       { }
 
-
       /**
        *  @brief  Copy constructor with allocator argument.
        *  @param  __list  Input list to copy.
@@ -461,14 +474,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       : _Base(_Node_alloc_type(__al))
       { _M_range_initialize(__list.begin(), __list.end()); }
 
-      /**
-       *  @brief  Move constructor with allocator argument.
-       *  @param  __list  Input list to move.
-       *  @param  __al    An allocator object.
-       */
-      forward_list(forward_list&& __list, const _Alloc& __al)
-      noexcept(_Node_alloc_traits::_S_always_equal())
-      : _Base(std::move(__list), _Node_alloc_type(__al))
+    private:
+      forward_list(forward_list&& __list, _Node_alloc_type&& __al,
+		   std::false_type)
+      : _Base(std::move(__list), std::move(__al))
       {
 	// If __list is not empty it means its allocator is not equal to __a,
 	// so we need to move from each element individually.
@@ -477,6 +486,24 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 		     std::__make_move_if_noexcept_iterator(__list.end()));
       }
 
+      forward_list(forward_list&& __list, _Node_alloc_type&& __al,
+		   std::true_type)
+      noexcept
+      : _Base(std::move(__list), _Node_alloc_type(__al), std::true_type{})
+      { }
+
+    public:
+      /**
+       *  @brief  Move constructor with allocator argument.
+       *  @param  __list  Input list to move.
+       *  @param  __al    An allocator object.
+       */
+      forward_list(forward_list&& __list, const _Alloc& __al)
+      noexcept(_Node_alloc_traits::_S_always_equal())
+      : forward_list(std::move(__list), _Node_alloc_type(__al),
+		     typename _Node_alloc_traits::is_always_equal{})
+      { }
+
       /**
        *  @brief  Creates a %forward_list with default constructed elements.
        *  @param  __n   The number of elements to initially create.
@@ -533,15 +560,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
       /**
        *  @brief  The %forward_list move constructor.
-       *  @param  __list  A %forward_list of identical element and allocator
-       *                  types.
+       *  @param  A %forward_list of identical element and allocator types.
        *
-       *  The newly-created %forward_list contains the exact contents of @a
-       *  __list. The contents of @a __list are a valid, but unspecified
-       *  %forward_list.
+       *  The newly-created %forward_list contains the exact contents of the
+       *  moved instance. The contents of the moved instance are a valid, but
+       *  unspecified %forward_list.
        */
-      forward_list(forward_list&& __list) noexcept
-      : _Base(std::move(__list)) { }
+      forward_list(forward_list&&) = default;
 
       /**
        *  @brief  Builds a %forward_list from an initializer_list
@@ -707,7 +732,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        */
       iterator
       end() noexcept
-      { return iterator(0); }
+      { return iterator(nullptr); }
 
       /**
        *  Returns a read-only iterator that points one past the last
@@ -716,7 +741,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        */
       const_iterator
       end() const noexcept
-      { return const_iterator(0); }
+      { return const_iterator(nullptr); }
 
       /**
        *  Returns a read-only (constant) iterator that points to the
@@ -743,7 +768,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        */
       const_iterator
       cend() const noexcept
-      { return const_iterator(0); }
+      { return const_iterator(nullptr); }
 
       /**
        *  Returns true if the %forward_list is empty.  (Thus begin() would
@@ -751,7 +776,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        */
       bool
       empty() const noexcept
-      { return this->_M_impl._M_head._M_next == 0; }
+      { return this->_M_impl._M_head._M_next == nullptr; }
 
       /**
        *  Returns the largest possible number of elements of %forward_list.
@@ -1056,7 +1081,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        */
       void
       clear() noexcept
-      { this->_M_erase_after(&this->_M_impl._M_head, 0); }
+      { this->_M_erase_after(&this->_M_impl._M_head, nullptr); }
 
       // 23.3.4.6 forward_list operations:
 
diff --git a/libstdc++-v3/include/bits/forward_list.tcc b/libstdc++-v3/include/bits/forward_list.tcc
index 64bd9c4..f13e959 100644
--- a/libstdc++-v3/include/bits/forward_list.tcc
+++ b/libstdc++-v3/include/bits/forward_list.tcc
@@ -41,12 +41,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
     : _M_impl(std::move(__a))
     {
       if (__lst._M_get_Node_allocator() == _M_get_Node_allocator())
-	{
-	  this->_M_impl._M_head._M_next = __lst._M_impl._M_head._M_next;
-	  __lst._M_impl._M_head._M_next = 0;
-	}
-      else
-	this->_M_impl._M_head._M_next = 0;
+	this->_M_impl._M_head = std::move(__lst._M_impl._M_head);
     }
 
   template<typename _Tp, typename _Alloc>
@@ -364,11 +359,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 					__list._M_impl._M_head._M_next);
 	    __node = __node->_M_next;
 	  }
+
 	if (__list._M_impl._M_head._M_next)
-          {
-            __node->_M_next = __list._M_impl._M_head._M_next;
-            __list._M_impl._M_head._M_next = 0;
-          }
+	  *__node = std::move(__list._M_impl._M_head);
       }
 
   template<typename _Tp, typename _Alloc>
@@ -399,7 +392,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       forward_list<_Tp, _Alloc>::
       sort(_Comp __comp)
       {
-        // If `next' is 0, return immediately.
+	// If `next' is nullptr, return immediately.
 	_Node* __list = static_cast<_Node*>(this->_M_impl._M_head._M_next);
 	if (!__list)
 	  return;
@@ -409,8 +402,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	while (1)
 	  {
 	    _Node* __p = __list;
-            __list = 0;
-            _Node* __tail = 0;
+	    __list = nullptr;
+	    _Node* __tail = nullptr;
 
 	    // Count number of merges we do in this pass.
 	    unsigned long __nmerges = 0;
@@ -478,7 +471,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 		// Now p has stepped `insize' places along, and q has too.
 		__p = __q;
 	      }
-            __tail->_M_next = 0;
+	    __tail->_M_next = nullptr;
 
 	    // If we have done only one merge, we're finished.
 	    // Allow for nmerges == 0, the empty list case.
@@ -498,4 +491,3 @@ _GLIBCXX_END_NAMESPACE_VERSION
 } // namespace std
 
 #endif /* _FORWARD_LIST_TCC */
-
diff --git a/libstdc++-v3/testsuite/23_containers/forward_list/allocator/default_init.cc b/libstdc++-v3/testsuite/23_containers/forward_list/allocator/default_init.cc
new file mode 100644
index 0000000..b56c9cc
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/forward_list/allocator/default_init.cc
@@ -0,0 +1,67 @@
+// Copyright (C) 2017 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-do run { target c++11 } }
+// { dg-options "-O0" }
+// { dg-xfail-run-if "PR c++/65816" { *-*-* } }
+
+#include <forward_list>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+#include <ext/aligned_buffer.h>
+
+using T = int;
+
+using __gnu_test::default_init_allocator;
+
+void test01()
+{
+  typedef default_init_allocator<T> alloc_type;
+  typedef std::forward_list<T, alloc_type> test_type;
+
+  __gnu_cxx::__aligned_buffer<test_type> buf;
+  __builtin_memset(buf._M_addr(), ~0, sizeof(test_type));
+
+  test_type *tmp = ::new(buf._M_addr()) test_type;
+
+  VERIFY( tmp->get_allocator().state == 0 );
+
+  tmp->~test_type();
+}
+
+void test02()
+{
+  typedef default_init_allocator<T> alloc_type;
+  typedef std::forward_list<T, alloc_type> test_type;
+
+  __gnu_cxx::__aligned_buffer<test_type> buf;
+  __builtin_memset(buf._M_addr(), ~0, sizeof(test_type));
+
+  test_type *tmp = ::new(buf._M_addr()) test_type();
+
+  VERIFY( tmp->get_allocator().state == 0 );
+
+  tmp->~test_type();
+}
+
+int main()
+{
+  test01();
+  test02();
+  return 0;
+}

On 23/11/17 22:22 +0100, François Dumont wrote:
>Gentle reminder for this patch.
>
>I looked when the constructor got unused and I think it is back in 
>June 2015 in git commit:
>
>commit debb6aabb771ed02cb7256a7719555e5fbd7d3f7
>Author: redi <redi@138bc75d-0d04-0410-961f-82ee72b054a4>
>Date:   Wed Jun 17 17:45:45 2015 +0000
>
>        * include/bits/forward_list.h
>        (_Fwd_list_base(const _Node_alloc_type&)): Change parameter to
>        rvalue-reference.

Hmm, I should have put that same change on the gcc-5-branch too.

>If you fear abi breaking change I can restore it in a 
>!_GLIBCXX_INLINE_VERSION section.

I think if there was a problem here my June 2015 change would already
have caused it (when I changed the _Fwd_list_base constructor
signatures).

So let's assume it's OK to remove the constructor.


>@@ -533,15 +560,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> 
>       /**
>        *  @brief  The %forward_list move constructor.
>-       *  @param  __list  A %forward_list of identical element and allocator
>-       *                  types.
>+       *  @param  A %forward_list of identical element and allocator types.

This change is wrong, you can't just remove the parameter name,
because now Doxygen will document a parameter called "A" (and complain
that there is no such parameter).

It would be better to leave the name __list there and just get the
warning.

Otherwise the patch is OK for trunk (please ensure to update the
Copyright dates in the test files to 2018).

Thanks.