directory-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Emmanuel Lecharny <elecha...@gmail.com>
Subject Re: AVLTree performance numbers
Date Wed, 05 Mar 2008 08:53:31 GMT
Alex Karasulu wrote:
> Here's the results I get when I run the performance test which I 
> committed today:
>
> total time for inserting 100000 items into the RBTree-->56.0 msec
> total time took to read an item from set 0.0 msec
> total time took to remove an item from set 0.0 msec
> total time for inserting 100000 items into the AVLTree-->481.0 msec
> total time took to read an item from tree 0.0 msec
> total time took to remove an item from AVLTree 0.0 msec
> total time taken for serializing HashSet ->820.0 msec
> total time taken for reconstructing a serialized HashSet ->506.0 msec
> total time taken for serializing AVLTree ->156.0 msec
> total time taken for reconstructing a serialized AVLTree ->141.0 msec
>
> Note I have a 4-way 2.6 GHz Opteron running an up to date ubuntu 7.10.
>
> From the looks of this it seems we're 10X slower on inserts but 5X 
> faster on serialization and 3.5X faster on deserialization.  I ran 
> this a few times and the numbers were pretty consistent. 
Thanks Alex !

Here is some mathematical background :

"Both AVL trees and red-black trees are self-balancing binary search 
trees, so they are very similar mathematically. The operations to 
balance the trees are different, but both occur in constant time. The 
real difference between the two is the limiting height. For a tree of 
size /n/:

    * an AVL tree's height is limited to 1.44 \cdot \lg n
    * a red-black tree's height is limited to 2 \cdot \lg n


The AVL tree is more rigidly balanced than Red-Black trees, leading to 
slower insertion and removal but faster retrieval."

(http://en.wikipedia.org/wiki/AVL_tree#_note-0)

As the height is lower in an AVL tree, searches are clearly faster. Now, 
it would be interesting to get the real numbers (how slower is it to 
insert an element in an AVL tree # in a RB tree, and what is the % of 
insertion relative to searches).

I'm also just wondering if we can spare this square(2) using a real 
binary tree, instead of a balanced tree, if searches represent a large 
part of the requests.

We also have to keep in mind that if those data structures are used for 
cursors, in the vast majority of cases we will only go forward. The cost 
of building a tree might be overwhelming in this case. A doule linked 
list should be just enough.

But I don't have all the elements in my head, so please feel free to 
corrct me if I'm wrong.

PS : I gonna instanciate those perf tests on our perf platform, with 
more realistic numbers (millions of elements, to get bigger timing : 
when you get something like 400 ms, you may get something like 2700 ms 
for 10 x the number of elements.)

-- 
--
cordialement, regards,
Emmanuel L├ęcharny
www.iktek.com
directory.apache.org



Mime
View raw message