[Patch] Performance and memory usage improvements for stl_tree.h

[Gawain Bolton]

Benjamin Kosnik wrote:

>>>So here is yet another patch using static_cast<> for the new code.  The 
>>>existing code could be cleaned up in several ways, such as using 
>>>static_cast<> elsewhere rather than C style casts.  I have tried to 
>>>refrain from doing this to keep the purppose of this patch focused.  I 
>>>am also trying to figure out how to contribute improvements to libstdc++ 
>>>and  so want to start with something simple.
>>>      
>>>
>
>Well, this is a good start, thanks.
>
>We need something to add as a performance metric for this kind of
>change. What did you do tests with? How are you measuring the
>performance improvement?
>  
>
I'm not trying to be facetious, but you do not even need to measure the 
performance to see that the patch supplied will improve it.  The header 
node is no longer dynamically allocated and de-allocated, so the 
performance of construction and destruction can only be improved.

The problem with providing performance measurements is that the time 
required to dynamically allocate memory depends on:

   1. The underlying operating system.
   2. The amount of memory fragmentation at the time of the test.
   3. The amount of memory requested.

So yes you can measure performance, but your mileage will vary depending 
on the above.

Here are some numbers for i686-pc-linux-gnu using RedHat Linx 7.3 with 
kernel 2.4.18-24.7.x using gprof.  The test is performed for 10 million 
iterations using std::map with both the key and value as "int":

    * Without patch (revision 1.19)
          o Constructor: 4.74 seconds
          o Destructor: 1.58 seconds
    * With last supplied patch:
          o Constructor: 2.78 seconds
          o Destructor: 0.53 seconds

Please find attached the test program used, as well as the numbers given 
by gprof.

These numbers give a performance improvement of 41% for the constructor 
and 66% for the destructor.  The type used for both the key and value 
was only "int" so this means that the header node will not require much 
memory to be allocated.  As such these numbers can be considered to be 
lower bound or "worst case" performance improvements.

The performance improvement may not be important in a lot of cases, but 
it may well be in some cases.  All programs will benefit by the reduced 
memory requirements though.  The amount of memory saved will depend on 
the number of std::map, std::set, std::multimap and std::multiset 
objects as well as the size of the template parameters.


Gawain

-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: map_performance.cc
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20030301/46d32e08/attachment.cc>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: old_map_performance.txt
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20030301/46d32e08/attachment.txt>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: new_map_performance.txt
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20030301/46d32e08/attachment-0001.txt>