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]

Re: Updated patch for std::list: Performance and memory usage improvements.


Gabriel Dos Reis wrote:

Gawain Bolton <gbolton@free.fr> writes:

| Once again this is an updated patch (see attached), this time for
| std::list. The original patch was posted a while back:
| | http://gcc.gnu.org/ml/libstdc++/2003-02/msg00179.html
| | Here's the suggested change log entry:
| | 2003-07-05 Gawain Bolton <gp.bolton@computer.org>
| | * include/bits/stl_list.h: Performance and memory usage
| improvements.
| * include/bits/list.tcc: Likewise.



Please, could you name the functions/classes/data you're touching in your patches? The above entry isn't really helpful :-(

The patch changed the std::list class. The main change is to the behaviour of the constructor and destructor as the list header node is no longer dynamically allocated/de-allocated. This improves performance and saves memory.


Do you have any measurements regarding your improvements?




Yes, using the attached performance test program here are some numbers tested on i686-pc-linux-gnu.

Before the patch:

* Compile flags: None
o list_create_fill_sort.cc Iterations: 10000000 Size: 1 1692r 1135u 8s 648mem 3pf
o list_create_fill_sort.cc Iterations: 1000000 Size: 10 9090r 6269u 29s 792mem 0pf
o list_create_fill_sort.cc Iterations: 100000 Size: 100 6160r 4267u 22s 840mem 0pf
o list_create_fill_sort.cc Iterations: 10000 Size: 1000 7570r 4998u 25s 15264mem 0pf


* Compile flags: -O2
o list_create_fill_sort.cc Iterations: 10000000 Size: 1 461r 389u 0s 648mem 3pf
o list_create_fill_sort.cc Iterations: 1000000 Size: 10 1991r 1588u 7s 792mem 0pf
o list_create_fill_sort.cc Iterations: 100000 Size: 100 1040r 848u 5s 840mem 0pf
o list_create_fill_sort.cc Iterations: 10000 Size: 1000 1725r 931u 1s 15264mem 0pf


After the patch:

* Compile flags: None
o list_create_fill_sort.cc Iterations: 10000000 Size: 1 1035r 864u 4s 648mem 3pf
o list_create_fill_sort.cc Iterations: 1000000 Size: 10 5517r 4561u 16s 0mem 0pf
o list_create_fill_sort.cc Iterations: 100000 Size: 100 4924r 4096u 16s 792mem 0pf
o list_create_fill_sort.cc Iterations: 10000 Size: 1000 5927r 4889u 21s 14368mem 0pf


* Compile flags: -O2
o list_create_fill_sort.cc Iterations: 10000000 Size: 1 353r 290u 3s 648mem 3pf
o list_create_fill_sort.cc Iterations: 1000000 Size: 10 1229r 1014u 6s 0mem 0pf
o list_create_fill_sort.cc Iterations: 100000 Size: 100 1020r 851u 3s 792mem 0pf
o list_create_fill_sort.cc Iterations: 10000 Size: 1000 1255r 1006u 2s 14368mem 0pf


Once again these performance improvements are worst case because the list used is for an integer type. A list with a large type having a constructor which actually does some work will show larger improvements!

Cheers,


Gawain


--
Gawain Bolton
Coignieres, France
PGP Info: Key server: http://wwwkeys.pgp.net
         Key id: 6EBEDEA6
         Fingerprint: 65C0 0030 21D1 7A01 546A  E7DB D60F 47E0 6EBE DEA6

// 2003-07-07 gp dot bolton at computer dot org

// Copyright (C) 2003 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 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 COPYING.  If not, write to the Free
// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
// USA.

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


static void create_and_fill_and_sort(const unsigned int n)
{
  typedef std::list<int>  List;
  List                    l;
  
  for (unsigned int i = 0; i < n; ++i)
  {
      l.push_back(n - i);
  }
  l.sort();
}


int main()
{
  using namespace std;
  using namespace __gnu_cxx_test;

  time_counter time;
  resource_counter resource;
  char comment[80];

  for (unsigned int n = 1; n <= 1000; n *= 10)
  {
      const unsigned int iterations = 10000000/n;

      start_counters(time, resource);

      for (unsigned int i = 0; i < iterations; ++i)
      {
	  create_and_fill_and_sort( n );
      }
      stop_counters(time, resource);

      sprintf(comment,"Iterations: %8u  Size: %8u",iterations,n);
      report_performance(__FILE__, comment, time, resource);
  }
  return 0;
}

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