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

[Gawain Bolton]

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

-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: list_create_fill_sort.cc
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20030708/c4c8cf8d/attachment.cc>