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

[Michal 'vorner' Vaner]

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 have another idea why it might be and that is memory layout. If it happened by
accident that the RB tree often had two nodes accessed soon after each other in
the same memory line, while the AVL doesn't, then it could make the RB faster
even if the AVL was shallower.

With regards

-- 
The cost of living is going up, and the chance of living is going down.

Michal 'vorner' Vaner
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 198 bytes
Desc: Digital signature
URL: <https://lists.isc.org/pipermail/bind10-dev/attachments/20130306/cd5b37d0/attachment.bin>