sub-optimum map implemtnation VC6 
Author Message
 sub-optimum map implemtnation VC6

I've been tracking down a performance problem which rather strangely occured
when destroying a map.  It takes 5 minutes!

Ok, it's a big map!  I do realise that this is not a bug, merely sub-optimal
performance.  The reason it took me so long to find the problem was due to
my huge reluctance to conclude that STL could be the problem.  It is
normally so fantastically efficient.  (P.J. my hat goes off to you)

However I noticed that the VC6 implementation of map has the clear method
implemented by erase(begin(),end());  The problem with this is that it
rebalances the red-black tree for every position in the iteration sequence.

I have noticed that the SGI implementation is optimised for the clear() case
and in fact calls the clear method if the erase method is called with
begin(), end().

Is this improved in VC7?  Or is there a patch I can download?

Regards,
Neil Groves
Irrational Daffodil Ltd



Sun, 16 May 2004 11:58:50 GMT  
 sub-optimum map implemtnation VC6

Quote:

> I've been tracking down a performance problem which rather strangely
occured
> when destroying a map.  It takes 5 minutes!

> Ok, it's a big map!  I do realise that this is not a bug, merely
sub-optimal
> performance.  The reason it took me so long to find the problem was due to
> my huge reluctance to conclude that STL could be the problem.  It is
> normally so fantastically efficient.  (P.J. my hat goes off to you)

> However I noticed that the VC6 implementation of map has the clear method
> implemented by erase(begin(),end());  The problem with this is that it
> rebalances the red-black tree for every position in the iteration
sequence.

> I have noticed that the SGI implementation is optimised for the clear()
case
> and in fact calls the clear method if the erase method is called with
> begin(), end().

> Is this improved in VC7?  Or is there a patch I can download?

You can try STLport. It is a free stl implementation that works a lot like
the SGI one since it build on it. Find it here:
http://www.stlport.com

/Daniel



Sun, 16 May 2004 21:00:35 GMT  
 sub-optimum map implemtnation VC6
Would this happen to be on Windows 2000?


Quote:
> I've been tracking down a performance problem which rather strangely
occured
> when destroying a map.  It takes 5 minutes!

> Ok, it's a big map!  I do realise that this is not a bug, merely
sub-optimal
> performance.  The reason it took me so long to find the problem was due to
> my huge reluctance to conclude that STL could be the problem.  It is
> normally so fantastically efficient.  (P.J. my hat goes off to you)

> However I noticed that the VC6 implementation of map has the clear method
> implemented by erase(begin(),end());  The problem with this is that it
> rebalances the red-black tree for every position in the iteration
sequence.

> I have noticed that the SGI implementation is optimised for the clear()
case
> and in fact calls the clear method if the erase method is called with
> begin(), end().

> Is this improved in VC7?  Or is there a patch I can download?



Sun, 16 May 2004 23:10:01 GMT  
 sub-optimum map implemtnation VC6


Quote:
> I've been tracking down a performance problem which rather strangely
occured
> when destroying a map.  It takes 5 minutes!

> Ok, it's a big map!  I do realise that this is not a bug, merely
sub-optimal
> performance.  The reason it took me so long to find the problem was due to
> my huge reluctance to conclude that STL could be the problem.  It is
> normally so fantastically efficient.  (P.J. my hat goes off to you)

> However I noticed that the VC6 implementation of map has the clear method
> implemented by erase(begin(),end());  The problem with this is that it
> rebalances the red-black tree for every position in the iteration
sequence.

> I have noticed that the SGI implementation is optimised for the clear()
case
> and in fact calls the clear method if the erase method is called with
> begin(), end().

> Is this improved in VC7?  Or is there a patch I can download?

Does the destructor take long to execute?  If not, using

typedef std::map< ... > MapType;

MapType().swap(map_to_clear);

will work without needing a patch.

marco



Sun, 16 May 2004 23:34:20 GMT  
 sub-optimum map implemtnation VC6

Quote:

> I've been tracking down a performance problem which rather strangely occured
> when destroying a map.  It takes 5 minutes!

> Ok, it's a big map!  I do realise that this is not a bug, merely sub-optimal
> performance.  The reason it took me so long to find the problem was due to
> my huge reluctance to conclude that STL could be the problem.  It is
> normally so fantastically efficient.  (P.J. my hat goes off to you)

> However I noticed that the VC6 implementation of map has the clear method
> implemented by erase(begin(),end());  The problem with this is that it
> rebalances the red-black tree for every position in the iteration sequence.

> I have noticed that the SGI implementation is optimised for the clear() case
> and in fact calls the clear method if the erase method is called with
> begin(), end().

> Is this improved in VC7?  Or is there a patch I can download?

Long since been fixed. The V3.08 upgrade library we license directly erases
a tree without intermediate rebalancing. And, of course, V7.0 does the same.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com



Mon, 17 May 2004 00:20:11 GMT  
 
 [ 5 post ] 

 Relevant Pages 

1. Sub Sub Projects in VC4.2

2. Error with map typedef, porting from VC6 project

3. tons of vc6++ map warnings

4. vc6 and map and operator<

5. Delphi v. Optima++

6. Optima++ or Visual C++

7. Optima++

8. Delphi v. Optima++

9. Optima++

10. Optimum hash functions ?

11. New Release:: Optima++ (based on Watcom C/C++)

12. need optimum hash generator

 

 
Powered by phpBB® Forum Software