[bind10-dev] Using AVL tree instead of red-black tree in DomainTree

[Mukund Sivaraman]

On Wed, Mar 06, 2013 at 10:58:03AM +0100, Michal 'vorner' Vaner wrote:
> Hello
> 
> On Wed, Mar 06, 2013 at 03:14:25PM +0530, Mukund Sivaraman wrote:
> > Though there is no difference in time complexity (maximum O(log N)), AVL
> > trees are better balanced and should be faster to lookup in general when
> > compared to red-black trees.  Unless some other code influences query
> > performance, AVL implementation should show better performance. This is
> > the case in the branch, so the results are suspicious (could it be a bug
> > in the AVL implementation?)
> 
> There could be, but that's hard to believe if the average depth is lower. Maybe
> you could implement some „check“ function that would verify the invariants
> about depths and run it from the tests?

I did, and posted results to the list in an earlier reply. AVL trees are
equal to RB in the random case, and almost 2 times shallower than RB
trees in the ordered case. This is why I feel the results in the ~12
million names zone are suspect.

The zone and query files are here for anyone else who wants to try this:

https://staff.banu.com/~muks/tmp/bind10/zones/

Each zone contains ~12 million records and each corresponding query file
contains 10 million queries.

You can run either the Nominum dnsperf tool against b10-auth, or the
src/bin/auth/benchmarks/query_bench tool with this data directly.

		Mukund
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 801 bytes
Desc: not available
URL: <https://lists.isc.org/pipermail/bind10-dev/attachments/20130306/dcfa7eb8/attachment.bin>