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

[Michal 'vorner' Vaner]

Hello

On Wed, Mar 06, 2013 at 04:11:57PM +0530, Mukund Sivaraman wrote:
> On Wed, Mar 06, 2013 at 10:58:03AM +0100, Michal 'vorner' Vaner wrote:
> > 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.
> 
> In the main AVL branch, the size of the node is the same. We use
> different bits in the flags_ member variable, but otherwise, data size
> is unchanged. Text segment changes, but nothing in the query path is
> different from the RB tree as both are BSTs and the find() operation is
> identical.

You probably misunderstood what I meant. When you're creating the nodes, they
are probably allocated one after another, so they reside consequitively in the
memory (well, this won't be true every time, but we can expect most of them will
live like this in the memory:

 [Node 1][Node 2][Node 3][Node 4]

And it may be faster to transfer them if they are grouped in the tree like:

 1
  \
   2
    \
     3
      \
       4

Then when they are grouped:

 1
  \
   3
    \
     2
      \
       4

The AVL balances slightly differently than the RB tree, so it may happen the
relative memory locations of the nodes are less favorable for CPU cache or
predictor.

With regards

-- 
I've already told you more than I know.

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/dd7da771/attachment.bin>