directory-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Alex Karasulu" <akaras...@apache.org>
Subject Re: AVLTree performance numbers
Date Tue, 04 Mar 2008 14:39:45 GMT
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 <ayyagarikiran@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
> >> <mailto:list@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
> >>
> >>
> >
>
>

Mime
View raw message