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]

Some performance info for: Suggested improvement to std::list


Yes I've done some performance testing on sparc-sun-solaris2.6 and can
tell you that roughly:

  1. Default std::list constructor is 2 orders of magnitude faster.
  2. std::list::swap() is 4 times slower.

Your mileage will vary, according to how expensive it is to allocate
dynamic memory on your system and how fragmented your system's memory is
at the time of the test.

I've attached a simple performance test program to test the performance
when constructing temporary lists and the performance of sort.

Here are the crude before and after results I get using GCC 3.2.2 and
the UNIX "time" command:

Performance when creating temporary lists [i.e. only executing test01()]

   * Using no compiler optimization
        o Before: 15.62u 0.00s 0:18.62 83.8%
        o After: 4.90u 0.01s 0:05.48 89.5%
   * Using -O2 optimization
        o Before: 5.87u 0.00s 0:07.54 77.8%
        o After: 0.79u 0.00s 0:00.88 89.7%.

Performance of sort() [i.e. only executing test02()]

   * Using no compiler optimization
        o Before: 18.72u 0.21s 0:22.33 84.7%
        o After: 18.59u 0.24s 0:22.13 85.0%
   * Using -O2 optimization
        o Before: 3.37u 0.25s 0:03.94 91.8%
        o After: 3.46u 0.24s 0:04.60 80.4%

As can be seen above, the performance when creating temporary lists is
far superior of sort() is even so slightly worse with -O2.

It's not clear cut, because the performance of sort() is no doubt
superior for lists up to a certain size because it can create the 65
temporary list objects more efficiently.  Beyond a certain size the
performance will be worse because of swap() being more complicated.


Gawain

"Stephen M. Webb" wrote:

> On February 12, 2003 12:15 pm, Gawain Bolton wrote:
> >
> > 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.
>
> Do you have before and after timing stats?
>
> --
> Stephen M. Webb

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




// Copyright (C) 2001 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 2, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without Pred 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 COPYING.  If not, write to the Free
// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
// USA.

// 23.2.2.2 list capacity [lib.list.capacity]

#include <list>
#include <testsuite_hooks.h>

bool test = true;

std::list<int> create_list(unsigned int n)
{
  std::list<int> a;

  while ( n )
  {
      a.push_back( n );
      --n;
  }
  return a;
}


// This test verifies the performance when constructing and destroying
// temporary lists.
//
void
test01()
{
  unsigned int i;

  for (i = 0; i < 10000000; ++i)
  {
      create_list(0);
  }
}


void
test02()
{
  unsigned int i;
  std::list<int> a;

  a = create_list(2);
  a.sort();

  a = create_list(10);
  a.sort();

  a = create_list(100);
  a.sort();

  a = create_list(1000);
  a.sort();

  a = create_list(10000);
  a.sort();

  a = create_list(100000);
  a.sort();

  a = create_list(1000000);
  a.sort();
}


int
main(int argc, char* argv[])
{
#if 0
    test01();
#endif

#if 1
    test02();
#endif

    return !test;
}

// vi:set sw=2 ts=2:


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