Optimization of std::deque implementation

Message ID 29660d37-28e6-56aa-1435-bfcece57df96@gmail.com
State New
Headers show
Series
  • Optimization of std::deque implementation
Related show

Commit Message

Fran├žois Dumont Nov. 6, 2018, 9:42 a.m.
Here is a patch similar to what has been done to other containers like 
std::vector.

It optimizes the swap operation, the allocator extended move constructor 
and some other methods where I just bypass intermediate calls.

I reproduced the noexcept qualification on _Deque_impl_data/_Deque_impl 
even if they are not necessary as long as the std:deque always allocate 
on instantiation.

I also removed some _M_map checks as, once again, it can't be null for 
the moment. I just kept the one in the destructor as I'd like to commit 
a patch after this one to avoid allocations on move which will make this 
check necessary.

Tested under Linux x86_64 Default and C++98 modes, w/o version namespace.

Still time to commit ?

Fran├žois

Patch

diff --git a/libstdc++-v3/include/bits/stl_deque.h b/libstdc++-v3/include/bits/stl_deque.h
index 8e4defbcf26..c49b6852324 100644
--- a/libstdc++-v3/include/bits/stl_deque.h
+++ b/libstdc++-v3/include/bits/stl_deque.h
@@ -398,7 +398,6 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	_Map_alloc_type;
       typedef __gnu_cxx::__alloc_traits<_Map_alloc_type> _Map_alloc_traits;
 
-    public:
       typedef _Alloc		  allocator_type;
 
       allocator_type
@@ -409,11 +408,9 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       typedef _Deque_iterator<_Tp, const _Tp&, _Ptr_const>   const_iterator;
 
       _Deque_base()
-      : _M_impl()
       { _M_initialize_map(0); }
 
       _Deque_base(size_t __num_elements)
-      : _M_impl()
       { _M_initialize_map(__num_elements); }
 
       _Deque_base(const allocator_type& __a, size_t __num_elements)
@@ -425,6 +422,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       { /* Caller must initialize map. */ }
 
 #if __cplusplus >= 201103L
+    private:
       _Deque_base(_Deque_base&& __x, false_type)
       : _M_impl(__x._M_move_impl())
       { }
@@ -433,84 +431,100 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       : _M_impl(std::move(__x._M_get_Tp_allocator()))
       {
 	_M_initialize_map(0);
-	if (__x._M_impl._M_map)
 	this->_M_impl._M_swap_data(__x._M_impl);
       }
 
+    protected:
       _Deque_base(_Deque_base&& __x)
       : _Deque_base(std::move(__x), typename _Alloc_traits::is_always_equal{})
       { }
 
+      _Deque_base(_Deque_base&& __x, const allocator_type& __a)
+      : _M_impl(std::move(__x._M_impl), _Tp_alloc_type(__a))
+      { __x._M_initialize_map(0); }
+
       _Deque_base(_Deque_base&& __x, const allocator_type& __a, size_t __n)
       : _M_impl(__a)
       {
 	if (__x.get_allocator() == __a)
-	  {
-	    if (__x._M_impl._M_map)
 	  {
 	    _M_initialize_map(0);
 	    this->_M_impl._M_swap_data(__x._M_impl);
 	  }
-	  }
 	else
-	  {
 	  _M_initialize_map(__n);
       }
-      }
 #endif
 
       ~_Deque_base() _GLIBCXX_NOEXCEPT;
 
-    protected:
       typedef typename iterator::_Map_pointer _Map_pointer;
 
-      //This struct encapsulates the implementation of the std::deque
-      //standard container and at the same time makes use of the EBO
-      //for empty allocators.
-      struct _Deque_impl
-      : public _Tp_alloc_type
+      struct _Deque_impl_data
       {
 	_Map_pointer _M_map;
 	size_t _M_map_size;
 	iterator _M_start;
 	iterator _M_finish;
 
-	_Deque_impl()
-	: _Tp_alloc_type(), _M_map(), _M_map_size(0),
-	  _M_start(), _M_finish()
+	_Deque_impl_data() _GLIBCXX_NOEXCEPT
+	: _M_map(), _M_map_size(), _M_start(), _M_finish()
+	{ }
+
+#if __cplusplus >= 201103L
+	_Deque_impl_data(const _Deque_impl_data&) = default;
+	_Deque_impl_data&
+	operator=(const _Deque_impl_data&) = default;
+
+	_Deque_impl_data(_Deque_impl_data&& __x) noexcept
+	: _Deque_impl_data(__x)
+	{ __x = _Deque_impl_data(); }
+#endif
+
+	void
+	_M_swap_data(_Deque_impl_data& __x) _GLIBCXX_NOEXCEPT
+	{
+	  // Do not use std::swap(_M_start, __x._M_start), etc as it loses
+	  // information used by TBAA.
+	  std::swap(*this, __x);
+	}
+      };
+
+      // This struct encapsulates the implementation of the std::deque
+      // standard container and at the same time makes use of the EBO
+      // for empty allocators.
+      struct _Deque_impl
+      : public _Tp_alloc_type, public _Deque_impl_data
+      {
+	_Deque_impl() _GLIBCXX_NOEXCEPT_IF(
+	  is_nothrow_default_constructible<_Tp_alloc_type>::value)
+	: _Tp_alloc_type()
 	{ }
 
 	_Deque_impl(const _Tp_alloc_type& __a) _GLIBCXX_NOEXCEPT
-	: _Tp_alloc_type(__a), _M_map(), _M_map_size(0),
-	  _M_start(), _M_finish()
+	: _Tp_alloc_type(__a)
 	{ }
 
 #if __cplusplus >= 201103L
 	_Deque_impl(_Deque_impl&&) = default;
 
 	_Deque_impl(_Tp_alloc_type&& __a) noexcept
-	: _Tp_alloc_type(std::move(__a)), _M_map(), _M_map_size(0),
-	  _M_start(), _M_finish()
+	: _Tp_alloc_type(std::move(__a))
 	{ }
-#endif
 
-	void _M_swap_data(_Deque_impl& __x) _GLIBCXX_NOEXCEPT
-	{
-	  using std::swap;
-	  swap(this->_M_start, __x._M_start);
-	  swap(this->_M_finish, __x._M_finish);
-	  swap(this->_M_map, __x._M_map);
-	  swap(this->_M_map_size, __x._M_map_size);
-	}
+	_Deque_impl(_Deque_impl&& __d, _Tp_alloc_type&& __a)
+	: _Tp_alloc_type(std::move(__a)), _Deque_impl_data(std::move(__d))
+	{ }
+#endif
       };
 
       _Tp_alloc_type&
       _M_get_Tp_allocator() _GLIBCXX_NOEXCEPT
-      { return *static_cast<_Tp_alloc_type*>(&this->_M_impl); }
+      { return this->_M_impl; }
 
       const _Tp_alloc_type&
       _M_get_Tp_allocator() const _GLIBCXX_NOEXCEPT
-      { return *static_cast<const _Tp_alloc_type*>(&this->_M_impl); }
+      { return this->_M_impl; }
 
       _Map_alloc_type
       _M_get_map_allocator() const _GLIBCXX_NOEXCEPT
@@ -544,7 +558,6 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	_Map_alloc_traits::deallocate(__map_alloc, __p, __n);
       }
 
-    protected:
       void _M_initialize_map(size_t);
       void _M_create_nodes(_Map_pointer __nstart, _Map_pointer __nfinish);
       void _M_destroy_nodes(_Map_pointer __nstart,
@@ -558,9 +571,6 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       _Deque_impl
       _M_move_impl()
       {
-	if (!_M_impl._M_map)
-	  return std::move(_M_impl);
-
 	// Create a copy of the current allocator.
 	_Tp_alloc_type __alloc{_M_get_Tp_allocator()};
 	// Put that copy in a moved-from state.
@@ -788,7 +798,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       typedef ptrdiff_t					difference_type;
       typedef _Alloc					allocator_type;
 
-    protected:
+    private:
       static size_t _S_buffer_size() _GLIBCXX_NOEXCEPT
       { return __deque_buf_size(sizeof(_Tp)); }
 
@@ -815,7 +825,11 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       /**
        *  @brief  Creates a %deque with no elements.
        */
-      deque() : _Base() { }
+#if __cplusplus >= 201103L
+      deque() = default;
+#else
+      deque() { }
+#endif
 
       /**
        *  @brief  Creates a %deque with no elements.
@@ -884,13 +898,13 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 #if __cplusplus >= 201103L
       /**
        *  @brief  %Deque move constructor.
-       *  @param  __x  A %deque of identical element and allocator types.
        *
-       *  The newly-created %deque contains the exact contents of @a __x.
-       *  The contents of @a __x are a valid, but unspecified %deque.
+       *  The newly-created %deque contains the exact contents of the
+       *  moved instance.
+       *  The contents of the moved instance are a valid, but unspecified
+       *  %deque.
        */
-      deque(deque&& __x)
-      : _Base(std::move(__x)) { }
+      deque(deque&&) = default;
 
       /// Copy constructor with alternative allocator
       deque(const deque& __x, const allocator_type& __a)
@@ -901,9 +915,18 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
       /// Move constructor with alternative allocator
       deque(deque&& __x, const allocator_type& __a)
+      : deque(std::move(__x), __a, typename _Alloc_traits::is_always_equal{})
+      { }
+
+    private:
+      deque(deque&& __x, const allocator_type& __a, true_type)
+      : _Base(std::move(__x), __a)
+      { }
+
+      deque(deque&& __x, const allocator_type& __a, false_type)
       : _Base(std::move(__x), __a, __x.size())
       {
-	if (__x.get_allocator() != __a)
+	if (__x.get_allocator() != __a && !__x.empty())
 	  {
 	    std::__uninitialized_move_a(__x.begin(), __x.end(),
 					this->_M_impl._M_start,
@@ -912,6 +935,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	  }
       }
 
+    public:
       /**
        *  @brief  Builds a %deque from an initializer list.
        *  @param  __l  An initializer_list.
@@ -953,7 +977,10 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	deque(_InputIterator __first, _InputIterator __last,
 	      const allocator_type& __a = allocator_type())
 	: _Base(__a)
-	{ _M_initialize_dispatch(__first, __last, __false_type()); }
+	{
+	  _M_range_initialize(__first, __last,
+			      std::__iterator_category(__first));
+	}
 #else
       template<typename _InputIterator>
 	deque(_InputIterator __first, _InputIterator __last,
@@ -1054,7 +1081,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	       typename = std::_RequireInputIter<_InputIterator>>
 	void
 	assign(_InputIterator __first, _InputIterator __last)
-	{ _M_assign_dispatch(__first, __last, __false_type()); }
+	{ _M_assign_aux(__first, __last, std::__iterator_category(__first)); }
 #else
       template<typename _InputIterator>
 	void
@@ -1240,14 +1267,6 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        */
       void
       resize(size_type __new_size, const value_type& __x)
-      {
-	const size_type __len = size();
-	if (__new_size > __len)
-	  _M_fill_insert(this->_M_impl._M_finish, __new_size - __len, __x);
-	else if (__new_size < __len)
-	  _M_erase_at_end(this->_M_impl._M_start
-			  + difference_type(__new_size));
-      }
 #else
       /**
        *  @brief  Resizes the %deque to the specified number of elements.
@@ -1262,6 +1281,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        */
       void
       resize(size_type __new_size, value_type __x = value_type())
+#endif
       {
 	const size_type __len = size();
 	if (__new_size > __len)
@@ -1270,7 +1290,6 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	  _M_erase_at_end(this->_M_impl._M_start
 			  + difference_type(__new_size));
       }
-#endif
 
 #if __cplusplus >= 201103L
       /**  A non-binding request to reduce memory use.  */
@@ -1599,6 +1618,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        *  @brief  Inserts an initializer list into the %deque.
        *  @param  __p  An iterator into the %deque.
        *  @param  __l  An initializer_list.
+       *  @return  An iterator that points to the inserted data.
        *
        *  This function will insert copies of the data in the
        *  initializer_list @a __l into the %deque before the location
@@ -1612,9 +1632,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 			    std::random_access_iterator_tag());
 	return begin() + __offset;
       }
-#endif
 
-#if __cplusplus >= 201103L
       /**
        *  @brief  Inserts a number of copies of given data into the %deque.
        *  @param  __position  A const_iterator into the %deque.
@@ -1666,8 +1684,8 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	       _InputIterator __last)
 	{
 	  difference_type __offset = __position - cbegin();
-	  _M_insert_dispatch(__position._M_const_cast(),
-			     __first, __last, __false_type());
+	  _M_range_insert_aux(__position._M_const_cast(), __first, __last,
+			      std::__iterator_category(__first));
 	  return begin() + __offset;
 	}
 #else
@@ -1773,6 +1791,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
     protected:
       // Internal constructor functions follow.
 
+#if __cplusplus < 201103L || !_GLIBCXX_INLINE_VERSION
       // called by the range constructor to implement [23.1.1]/9
 
       // _GLIBCXX_RESOLVE_LIB_DEFECTS
@@ -1786,6 +1805,17 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	  _M_fill_initialize(__x);
 	}
 
+      // called by the range constructor to implement [23.1.1]/9
+      template<typename _InputIterator>
+	void
+	_M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
+			       __false_type)
+	{
+	  _M_range_initialize(__first, __last,
+			      std::__iterator_category(__first));
+	}
+#endif
+
       static size_t
       _S_check_init_len(size_t __n, const allocator_type& __a)
       {
@@ -1803,16 +1833,6 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	return (std::min)(__diffmax, __allocmax);
       }
 
-      // called by the range constructor to implement [23.1.1]/9
-      template<typename _InputIterator>
-	void
-	_M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
-			       __false_type)
-	{
-	  _M_range_initialize(__first, __last,
-			      std::__iterator_category(__first));
-	}
-
       // called by the second initialize_dispatch above
       //@{
       /**
@@ -1859,6 +1879,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       // Internal assign functions follow.  The *_aux functions do the actual
       // assignment work for the range versions.
 
+#if __cplusplus < 201103L || !_GLIBCXX_INLINE_VERSION
       // called by the range assign to implement [23.1.1]/9
 
       // _GLIBCXX_RESOLVE_LIB_DEFECTS
@@ -1874,6 +1895,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	_M_assign_dispatch(_InputIterator __first, _InputIterator __last,
 			   __false_type)
 	{ _M_assign_aux(__first, __last, std::__iterator_category(__first)); }
+#endif
 
       // called by the second assign_dispatch above
       template<typename _InputIterator>
@@ -1939,6 +1961,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       // Internal insert functions follow.  The *_aux functions do the actual
       // insertion work when all shortcuts fail.
 
+#if __cplusplus < 201103L || !_GLIBCXX_INLINE_VERSION
       // called by the range insert to implement [23.1.1]/9
 
       // _GLIBCXX_RESOLVE_LIB_DEFECTS
@@ -1959,6 +1982,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	  _M_range_insert_aux(__pos, __first, __last,
 			      std::__iterator_category(__first));
 	}
+#endif
 
       // called by the second insert_dispatch above
       template<typename _InputIterator>
diff --git a/libstdc++-v3/testsuite/23_containers/deque/allocator/default_init.cc b/libstdc++-v3/testsuite/23_containers/deque/allocator/default_init.cc
new file mode 100644
index 00000000000..5cb58865faa
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/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 <deque>
+#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::deque<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::deque<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;
+}