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]

Suggested improvement to std::list


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
-------------------------------------------------------------------------------


125c125
<       _List_iterator(_Node* __x)
---
>       _List_iterator(_List_node_base* __x)
213c213
<       _List_node<_Tp>* _M_node;
---
>       _List_node_base _M_node;
245c245
<       _List_node<_Tp>* _M_node;
---
>       _List_node_base _M_node;
262,264c262,263
<         _M_node = _M_get_node();
<         _M_node->_M_next = _M_node;
<         _M_node->_M_prev = _M_node;
---
>         _M_node._M_next = &_M_node;
>         _M_node._M_prev = &_M_node;
270d268
<         _M_put_node(_M_node);
365c363
<       { return static_cast<_Node*>(_M_node->_M_next); }
---
>       { return _M_node._M_next; }
369c367
<       { return static_cast<_Node*>(_M_node->_M_next); }
---
>       { return _M_node._M_next; }
373c371
<       { return _M_node; }
---
>       { return &_M_node; }
377c375
<       { return _M_node; }
---
>       { return const_cast<_List_node_base*>(&_M_node); }
397c395
<       { return _M_node->_M_next == _M_node; }
---
>       { return _M_node._M_next == &_M_node; }
424,425c422
<       swap(list<_Tp, _Alloc>& __x)
<       { std::swap(_M_node, __x._M_node); }
---
>       swap(list<_Tp, _Alloc>& __x);
712,713c709,710
<       _List_node<_Tp>* __cur = static_cast<_List_node<_Tp>*>(_M_node->_M_next);
<       while (__cur != _M_node) {
---
>       _List_node<_Tp>* __cur = static_cast<_List_node<_Tp>*>(_M_node._M_next);
>       while (__cur != &_M_node) {
719,720c716,717
<       _M_node->_M_next = _M_node;
<       _M_node->_M_prev = _M_node;
---
>       _M_node._M_next = &_M_node;
>       _M_node._M_prev = &_M_node;
723a721,753
>     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>
874c904
<   { __List_base_reverse(this->_M_node); }    
---
>   { __List_base_reverse(&_M_node); }
881c911
<       if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) {
---
>       if (_M_node._M_next != &_M_node && _M_node._M_next->_M_next != &_M_node) {
961c991
<       if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) {
---
>       if (_M_node._M_next != &_M_node && _M_node._M_next->_M_next != &_M_node) {

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