You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@directory.apache.org by Kiran Ayyagari <ay...@gmail.com> on 2008/03/01 14:59:28 UTC

AVLTree performance numbers

hi,

     Below given are some of the numbers obtained by comparing the 
current implementation of AVL tree against the RB tree underlying
     the java.util.HashSet.
     
Comparison of Insert operation in milli seconds
No. of Nodes    1000     10,000   100,000
HashSet              1            10           425
AVLTree           18           68           624

The time taken for both lookup and remove operations is same for both 
AVLTree and RBTree

Configuration of my system is - 512MB RAM and Celeron processor 
(ThinkPad R51 running Ubuntu 6.06)

Please suggest, should this be improved further?
-- 
- Kiran Ayyagari


Re: AVLTree performance numbers

Posted by Emmanuel Lecharny <el...@gmail.com>.
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



Re: AVLTree performance numbers

Posted by Alex Karasulu <ak...@apache.org>.
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.

Alex

On Sun, Mar 2, 2008 at 12:01 PM, Kiran Ayyagari <ay...@gmail.com>
wrote:

>
> hey guys,
>
>      I encountered an issue at the end with balancing the tree after
> removal, so I didn't release a patch for the code which produced the
> below results.
>
>      I have just created few more patches to the old code with a little
> improvement. The test cases comparing the AVLTree with RBTree are present
>
>      in the file AVLTreePerfTest.java (
> https://issues.apache.org/jira/browse/DIRSERVER-1138 )
>
>      The main hot spot is the balancing operation, The implementation
> currently calculates it recursively for every insert/delete operation
>      The below given performance numbers not applicable for the code
> present in the repo.
>
>      Will try to fix this? Any ideas/suggestions please share.
>
> thanks,
> --
> - Kiran Ayyagari
>
>
> Alan D. Cabrera wrote:
> > Yeah, me in both cases.  Very interesting stuff.  Sorry, I jumped in
> > the middle of this.  Is this the same effort?  I wanted to look at the
> > benchmarking code.
> >
> >
> > Regards,
> > Alan
> >
> > On Mar 1, 2008, at 11:02 AM, Alex Karasulu wrote:
> >
> >> Is this this Alan Cabrera bot? Same response to 2 emails :).
> >>
> >> Alex
> >>
> >> On Sat, Mar 1, 2008 at 1:04 PM, Alan D. Cabrera <list@toolazydogs.com
> >> <ma...@toolazydogs.com>> wrote:
> >>
> >>
> >>     On Mar 1, 2008, at 5:59 AM, Kiran Ayyagari wrote:
> >>
> >>     >
> >>     > hi,
> >>     >
> >>     >    Below given are some of the numbers obtained by comparing the
> >>     > current implementation of AVL tree against the RB tree underlying
> >>     >    the java.util.HashSet.
> >>     >    Comparison of Insert operation in milli seconds
> >>     > No. of Nodes    1000     10,000   100,000
> >>     > HashSet              1            10           425
> >>     > AVLTree           18           68           624
> >>     >
> >>     > The time taken for both lookup and remove operations is same for
> >>     > both AVLTree and RBTree
> >>     >
> >>     > Configuration of my system is - 512MB RAM and Celeron processor
> >>     > (ThinkPad R51 running Ubuntu 6.06)
> >>     >
> >>     > Please suggest, should this be improved further?
> >>
> >>     Very interesting.  Can you check in this work in a sandbox?
> >>
> >>
> >>     Regards,
> >>     Alan
> >>
> >>
> >
>
>

Re: AVLTree performance numbers

Posted by Kiran Ayyagari <ay...@gmail.com>.
hey guys,
 
      I encountered an issue at the end with balancing the tree after 
removal, so I didn't release a patch for the code which produced the 
below results.
 
      I have just created few more patches to the old code with a little 
improvement. The test cases comparing the AVLTree with RBTree are present

      in the file AVLTreePerfTest.java ( 
https://issues.apache.org/jira/browse/DIRSERVER-1138 )

      The main hot spot is the balancing operation, The implementation 
currently calculates it recursively for every insert/delete operation
      The below given performance numbers not applicable for the code 
present in the repo.

      Will try to fix this? Any ideas/suggestions please share.

thanks,
-- 
- Kiran Ayyagari


Alan D. Cabrera wrote:
> Yeah, me in both cases.  Very interesting stuff.  Sorry, I jumped in 
> the middle of this.  Is this the same effort?  I wanted to look at the 
> benchmarking code.
>
>
> Regards,
> Alan
>
> On Mar 1, 2008, at 11:02 AM, Alex Karasulu wrote:
>
>> Is this this Alan Cabrera bot? Same response to 2 emails :).
>>
>> Alex
>>
>> On Sat, Mar 1, 2008 at 1:04 PM, Alan D. Cabrera <list@toolazydogs.com 
>> <ma...@toolazydogs.com>> wrote:
>>
>>
>>     On Mar 1, 2008, at 5:59 AM, Kiran Ayyagari wrote:
>>
>>     >
>>     > hi,
>>     >
>>     >    Below given are some of the numbers obtained by comparing the
>>     > current implementation of AVL tree against the RB tree underlying
>>     >    the java.util.HashSet.
>>     >    Comparison of Insert operation in milli seconds
>>     > No. of Nodes    1000     10,000   100,000
>>     > HashSet              1            10           425
>>     > AVLTree           18           68           624
>>     >
>>     > The time taken for both lookup and remove operations is same for
>>     > both AVLTree and RBTree
>>     >
>>     > Configuration of my system is - 512MB RAM and Celeron processor
>>     > (ThinkPad R51 running Ubuntu 6.06)
>>     >
>>     > Please suggest, should this be improved further?
>>
>>     Very interesting.  Can you check in this work in a sandbox?
>>
>>
>>     Regards,
>>     Alan
>>
>>
>


Re: AVLTree performance numbers

Posted by "Alan D. Cabrera" <li...@toolazydogs.com>.
Yeah, me in both cases.  Very interesting stuff.  Sorry, I jumped in  
the middle of this.  Is this the same effort?  I wanted to look at the  
benchmarking code.


Regards,
Alan

On Mar 1, 2008, at 11:02 AM, Alex Karasulu wrote:

> Is this this Alan Cabrera bot? Same response to 2 emails :).
>
> Alex
>
> On Sat, Mar 1, 2008 at 1:04 PM, Alan D. Cabrera  
> <li...@toolazydogs.com> wrote:
>
> On Mar 1, 2008, at 5:59 AM, Kiran Ayyagari wrote:
>
> >
> > hi,
> >
> >    Below given are some of the numbers obtained by comparing the
> > current implementation of AVL tree against the RB tree underlying
> >    the java.util.HashSet.
> >    Comparison of Insert operation in milli seconds
> > No. of Nodes    1000     10,000   100,000
> > HashSet              1            10           425
> > AVLTree           18           68           624
> >
> > The time taken for both lookup and remove operations is same for
> > both AVLTree and RBTree
> >
> > Configuration of my system is - 512MB RAM and Celeron processor
> > (ThinkPad R51 running Ubuntu 6.06)
> >
> > Please suggest, should this be improved further?
>
> Very interesting.  Can you check in this work in a sandbox?
>
>
> Regards,
> Alan
>
>


Re: AVLTree performance numbers

Posted by Alex Karasulu <ak...@apache.org>.
Is this this Alan Cabrera bot? Same response to 2 emails :).

Alex

On Sat, Mar 1, 2008 at 1:04 PM, Alan D. Cabrera <li...@toolazydogs.com>
wrote:

>
> On Mar 1, 2008, at 5:59 AM, Kiran Ayyagari wrote:
>
> >
> > hi,
> >
> >    Below given are some of the numbers obtained by comparing the
> > current implementation of AVL tree against the RB tree underlying
> >    the java.util.HashSet.
> >    Comparison of Insert operation in milli seconds
> > No. of Nodes    1000     10,000   100,000
> > HashSet              1            10           425
> > AVLTree           18           68           624
> >
> > The time taken for both lookup and remove operations is same for
> > both AVLTree and RBTree
> >
> > Configuration of my system is - 512MB RAM and Celeron processor
> > (ThinkPad R51 running Ubuntu 6.06)
> >
> > Please suggest, should this be improved further?
>
> Very interesting.  Can you check in this work in a sandbox?
>
>
> Regards,
> Alan
>
>

Re: AVLTree performance numbers

Posted by "Alan D. Cabrera" <li...@toolazydogs.com>.
On Mar 1, 2008, at 5:59 AM, Kiran Ayyagari wrote:

>
> hi,
>
>    Below given are some of the numbers obtained by comparing the  
> current implementation of AVL tree against the RB tree underlying
>    the java.util.HashSet.
>    Comparison of Insert operation in milli seconds
> No. of Nodes    1000     10,000   100,000
> HashSet              1            10           425
> AVLTree           18           68           624
>
> The time taken for both lookup and remove operations is same for  
> both AVLTree and RBTree
>
> Configuration of my system is - 512MB RAM and Celeron processor  
> (ThinkPad R51 running Ubuntu 6.06)
>
> Please suggest, should this be improved further?

Very interesting.  Can you check in this work in a sandbox?


Regards,
Alan


Re: AVLTree performance numbers

Posted by Emmanuel Lecharny <el...@gmail.com>.
Kiran Ayyagari wrote:
>
> hi,
>
>     Below given are some of the numbers obtained by comparing the 
> current implementation of AVL tree against the RB tree underlying
>     the java.util.HashSet.
>     Comparison of Insert operation in milli seconds
> No. of Nodes    1000     10,000   100,000
> HashSet              1            10           425
> AVLTree           18           68           624
>
> The time taken for both lookup and remove operations is same for both 
> AVLTree and RBTree
>
> Configuration of my system is - 512MB RAM and Celeron processor 
> (ThinkPad R51 running Ubuntu 6.06)
>
> Please suggest, should this be improved further?
Just for completness, I would like to see a test with 10 000 000 
elements... Is it possible ?

Also, that would be interesting to test with other JVMs (I guess you are 
using SUN 1.6 JVM), like :
- Sun 1.5.0_14
- Sun 1.6.0_b4
- Sun 1.7
- IBM 5.0
- IBM 6.0
- JRockit 5.0
- JRockit 6.0

I have all those JVMs installed somewhere on a server, I can run the 
test if you post the code !

Thanks :)


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