This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Context diff for: Suggested improvement to std::list


Sorry for resending this but a context diff was requested.  See attached
file.

Hello,

I would like to humbly suggest an improvement to the std::list container
class.  This improvement does the following:

   * reduces amount of memory required
        o the _List_alloc_base class contains a _List_node_base member
          rather than using _List_node<_Tp>.
   * improve performance when creating and destroying lists
        o the constructor no longer allocates memory, since the _M_node
          member in  the _List_alloc_base class is not a pointer.
        o this offers a big improvement when creating temporary list
          objects

Where's the catch?  Well, the swap() function is seriously more
complicated.  That said, it is still constant time and cannot generate
an exception.  Is it reasonable to accept the hit for swap?  I believe
so.  The one function which makes heavy use of swap() is sort().  But
this function gets a big improvement because the 65 temporary list
objects are going to take much less time to be created and destroyed.

Please find attached the proposed patch for stl_list.h based on the
version in GCC 3.2.2.

This has been tested with all the list_* tests in
gcc-3.2.2/libstdc++-v3/testsuite/23_containers on Solaris.

A similar thing can be done for std::map, std::multimap, std::set and
std::multiset by changing the _M_header field in the _Rb_tree_alloc_base
class in stl_tree.h.  Even better, the swap() function would still be
very simple.  If people thing this is worth doing I would happy to
submit a patch.

Cheers,


Gawain

--
-------------------------------------------------------------------------------
Gawain Bolton                     | E-mail: boltong@nortelnetworks.com
Section 4808                      | Internal mail stop: CT45
UMTS Development                  |
Nortel Networks                   | Voice:  ESN 579-3763   +33
1.39.44.37.63
Guyancourt, France                | FAX:    ESN 579-3009   +33
1.39.44.30.09
-------------------------------------------------------------------------------
*** /home/boltong/gcc/include/c++/3.2.2/bits/stl_list.h.orig	Fri Feb  7 12:13:08 2003
--- /home/boltong/gcc/include/c++/3.2.2/bits/stl_list.h	Wed Feb 12 17:18:17 2003
***************
*** 122,128 ****
        typedef _Ref reference;
        typedef _List_node<_Tp> _Node;
  
!       _List_iterator(_Node* __x)
        : _List_iterator_base(__x)
        { }
  
--- 122,128 ----
        typedef _Ref reference;
        typedef _List_node<_Tp> _Node;
  
!       _List_iterator(_List_node_base* __x)
        : _List_iterator_base(__x)
        { }
  
***************
*** 210,216 ****
        typename _Alloc_traits<_List_node<_Tp>, _Allocator>::allocator_type
                 _Node_allocator;
  
!       _List_node<_Tp>* _M_node;
      };
  
    // Specialization for instanceless allocators.
--- 210,216 ----
        typename _Alloc_traits<_List_node<_Tp>, _Allocator>::allocator_type
                 _Node_allocator;
  
!       _List_node_base _M_node;
      };
  
    // Specialization for instanceless allocators.
***************
*** 242,248 ****
        { _Alloc_type::deallocate(__p, 1); }
  
      protected:
!       _List_node<_Tp>* _M_node;
      };
  
    template<typename _Tp, typename _Alloc>
--- 242,248 ----
        { _Alloc_type::deallocate(__p, 1); }
  
      protected:
!       _List_node_base _M_node;
      };
  
    template<typename _Tp, typename _Alloc>
***************
*** 259,273 ****
        _List_base(const allocator_type& __a)
        : _Base(__a)
        {
!         _M_node = _M_get_node();
!         _M_node->_M_next = _M_node;
!         _M_node->_M_prev = _M_node;
        }
  
        ~_List_base()
        {
          clear();
-         _M_put_node(_M_node);
        }
  
        void clear();
--- 259,271 ----
        _List_base(const allocator_type& __a)
        : _Base(__a)
        {
!         _M_node._M_next = &_M_node;
!         _M_node._M_prev = &_M_node;
        }
  
        ~_List_base()
        {
          clear();
        }
  
        void clear();
***************
*** 362,380 ****
  
        iterator
        begin()
!       { return static_cast<_Node*>(_M_node->_M_next); }
  
        const_iterator
        begin() const
!       { return static_cast<_Node*>(_M_node->_M_next); }
  
        iterator
        end()
!       { return _M_node; }
  
        const_iterator
        end() const
!       { return _M_node; }
  
        reverse_iterator
        rbegin() 
--- 360,378 ----
  
        iterator
        begin()
!       { return _M_node._M_next; }
  
        const_iterator
        begin() const
!       { return _M_node._M_next; }
  
        iterator
        end()
!       { return &_M_node; }
  
        const_iterator
        end() const
!       { return const_cast<_List_node_base*>(&_M_node); }
  
        reverse_iterator
        rbegin() 
***************
*** 394,400 ****
  
        bool
        empty() const
!       { return _M_node->_M_next == _M_node; }
  
        size_type
        size() const
--- 392,398 ----
  
        bool
        empty() const
!       { return _M_node._M_next == &_M_node; }
  
        size_type
        size() const
***************
*** 421,428 ****
        { return *(--end()); }
  
        void
!       swap(list<_Tp, _Alloc>& __x)
!       { std::swap(_M_node, __x._M_node); }
  
        iterator
        insert(iterator __position, const _Tp& __x)
--- 419,425 ----
        { return *(--end()); }
  
        void
!       swap(list<_Tp, _Alloc>& __x);
  
        iterator
        insert(iterator __position, const _Tp& __x)
***************
*** 709,726 ****
      void _List_base<_Tp,_Alloc>::
      clear() 
      {
!       _List_node<_Tp>* __cur = static_cast<_List_node<_Tp>*>(_M_node->_M_next);
!       while (__cur != _M_node) {
          _List_node<_Tp>* __tmp = __cur;
          __cur = static_cast<_List_node<_Tp>*>(__cur->_M_next);
          _Destroy(&__tmp->_M_data);
          _M_put_node(__tmp);
        }
!       _M_node->_M_next = _M_node;
!       _M_node->_M_prev = _M_node;
      }
  
    template<typename _Tp, typename _Alloc>
      template <typename _InputIter>
        void list<_Tp, _Alloc>::
        _M_insert_dispatch(iterator __position, _InputIter __first, _InputIter __last,
--- 706,756 ----
      void _List_base<_Tp,_Alloc>::
      clear() 
      {
!       _List_node<_Tp>* __cur = static_cast<_List_node<_Tp>*>(_M_node._M_next);
!       while (__cur != &_M_node) {
          _List_node<_Tp>* __tmp = __cur;
          __cur = static_cast<_List_node<_Tp>*>(__cur->_M_next);
          _Destroy(&__tmp->_M_data);
          _M_put_node(__tmp);
        }
!       _M_node._M_next = &_M_node;
!       _M_node._M_prev = &_M_node;
      }
  
    template<typename _Tp, typename _Alloc>
+     void list<_Tp, _Alloc>::
+     swap(list<_Tp, _Alloc>& __x)
+     {
+       if ( _M_node._M_next == &_M_node )
+       {
+         if ( __x._M_node._M_next != &__x._M_node )
+         {
+           _M_node._M_next = __x._M_node._M_next;
+           _M_node._M_prev = __x._M_node._M_prev;
+           
+           _M_node._M_next->_M_prev = _M_node._M_prev->_M_next = &_M_node;
+           __x._M_node._M_next = __x._M_node._M_prev = &__x._M_node;
+         }
+       }
+       else if ( __x._M_node._M_next == &__x._M_node )
+       {
+         __x._M_node._M_next = _M_node._M_next;
+         __x._M_node._M_prev = _M_node._M_prev;
+         
+         __x._M_node._M_next->_M_prev = __x._M_node._M_prev->_M_next = &__x._M_node;
+         _M_node._M_next = _M_node._M_prev = &_M_node;
+       }
+       else
+       {
+         std::swap(_M_node._M_next,__x._M_node._M_next);
+         std::swap(_M_node._M_prev,__x._M_node._M_prev);
+       
+         _M_node._M_next->_M_prev = _M_node._M_prev->_M_next = &_M_node;
+         __x._M_node._M_next->_M_prev = __x._M_node._M_prev->_M_next = &__x._M_node;
+       } 
+     }
+ 
+   template<typename _Tp, typename _Alloc>
      template <typename _InputIter>
        void list<_Tp, _Alloc>::
        _M_insert_dispatch(iterator __position, _InputIter __first, _InputIter __last,
***************
*** 871,877 ****
    template<typename _Tp, typename _Alloc>
    inline void list<_Tp, _Alloc>::
    reverse() 
!   { __List_base_reverse(this->_M_node); }    
  
    template<typename _Tp, typename _Alloc>
      void list<_Tp, _Alloc>::
--- 901,907 ----
    template<typename _Tp, typename _Alloc>
    inline void list<_Tp, _Alloc>::
    reverse() 
!   { __List_base_reverse(&_M_node); }
  
    template<typename _Tp, typename _Alloc>
      void list<_Tp, _Alloc>::
***************
*** 878,884 ****
      sort()
      {
        // Do nothing if the list has length 0 or 1.
!       if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) {
          list<_Tp, _Alloc> __carry;
          list<_Tp, _Alloc> __counter[64];
          int __fill = 0;
--- 908,914 ----
      sort()
      {
        // Do nothing if the list has length 0 or 1.
!       if (_M_node._M_next != &_M_node && _M_node._M_next->_M_next != &_M_node) {
          list<_Tp, _Alloc> __carry;
          list<_Tp, _Alloc> __counter[64];
          int __fill = 0;
***************
*** 958,964 ****
      sort(_StrictWeakOrdering __comp)
      {
        // Do nothing if the list has length 0 or 1.
!       if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) {
          list<_Tp, _Alloc> __carry;
          list<_Tp, _Alloc> __counter[64];
          int __fill = 0;
--- 988,994 ----
      sort(_StrictWeakOrdering __comp)
      {
        // Do nothing if the list has length 0 or 1.
!       if (_M_node._M_next != &_M_node && _M_node._M_next->_M_next != &_M_node) {
          list<_Tp, _Alloc> __carry;
          list<_Tp, _Alloc> __counter[64];
          int __fill = 0;

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]