directory-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Kiran Ayyagari <ayyagariki...@gmail.com>
Subject Re: AVLTree performance numbers
Date Sun, 02 Mar 2008 17:01:04 GMT

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