This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: std::forward_list optim for always equal allocator
- From: François Dumont <frs dot dumont at gmail dot com>
- To: "libstdc++ at gcc dot gnu dot org" <libstdc++ at gcc dot gnu dot org>, gcc-patches <gcc-patches at gcc dot gnu dot org>
- Date: Thu, 23 Nov 2017 22:22:38 +0100
- Subject: Re: std::forward_list optim for always equal allocator
- Authentication-results: sourceware.org; auth=none
- References: <c199ddfe-3292-f42e-a2ce-aa3ef92e5910@gmail.com> <f8941efc-9020-c64e-f31a-d4ca483f74a3@gmail.com>
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;
+}