std::map and std::set based on AVL, not RB trees.

["Daniel K. O." <danielosmari at yahoo dot com dot br>]

Hello.

Some months ago, while having nothing special to do, I modified the 
libstdc++'s RB tree - used in the associative containers - into an AVL tree.

After making some tests, I noticed some interesting results; I was 
expecting it to be a bit slower than the original RB tree, but it 
performed faster for some operations. After that some friends asked me 
to make a library. It's now at http://sourceforge.net/projects/stlavlmap/

Here are some numbers:

System: Windows 98 SE, 256 MB RAM, MinGW/GCC 3.4.2

Test:   Ascending sorted insertion
AVL:      4830 (4.83 s)
RB:       6650 (6.65 s)

Test:   Descending sorted insertion
AVL:      5340 (5.34 s)
RB:       7400 (7.4 s)

Generating random numbers (be patient)...Done
Test:   Random insertion
AVL:      1580 (1.58 s)
RB:       1660 (1.66 s)

Test:   Traverse ascending
AVL:      5220 (5.22 s)
RB:       5270 (5.27 s)

Test:   Traverse descending
AVL:      5770 (5.77 s)
RB:       6100 (6.1 s)

Test:   Random deletion
AVL:      2640 (2.64 s)
RB:       2670 (2.67 s)



In the tests ( 
http://cvs.sourceforge.net/viewcvs.py/stlavlmap/stlavlmap/tests ) I'm 
using a copy of the libstdc++ tree.cpp with the RB tree, to make sure 
that both AVL and RB operations are compiled with the have the same 
optimization flags.
The tests use the std::set container with the __gnu_cxx::__pool_alloc 
allocator, to minimize the allocation overhead. The sets contain ints to 
minimize the comparision and copy operations. This was intended to 
measure only the tree operations.

The AVL operations are in the tree.cpp:
http://cvs.sourceforge.net/viewcvs.py/stlavlmap/stlavlmap/lib/tree.cpp?rev=1.1.1.1&view=markup
Any other changes in the headers are just to replace the _Rb_ prefix by 
_avl_.

I don't know the dirty details on how to make accurate cross-platform 
tests; so I'm posting this message for 2 reasons:
1. Get some hints from the GCC developers on how to improve my 
benchmarks, and maybe even the tree implementation.
2. If the developers conclude that the AVL tree is better, they may be 
interested in replace the RB tree.


Any comment is welcome.

Thanks for your atention.
Daniel K. O.