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

[Mukund Sivaraman]

On Sat, Mar 02, 2013 at 11:43:23PM +0530, Mukund Sivaraman wrote:
> On Sat, Mar 02, 2013 at 10:58:19PM +0530, Mukund Sivaraman wrote:
> > Comments are welcome. Please test query and zone loading performance of
> > this branch (AVL implementation) vs. the point where it was branched off
> > master (red-black implementation), if you have a BIND 10 benchmark
> > environment.
> 
> For a million+ names top-level (under .) DomainTree, the following
> tree heights (in subtree under .) were observed:
> 
>   red-black: 24 (random insertion), 38 (ordered insertion)
>         AVL: 24 (random insertion), 21 (ordered insertion)

Here is a benchmark result, run with the dnsperf tool.

Config
------

* 12 million domain unique names were created under an example.org. zone
  using the Linux words list (Moby project). Some were hyphenated,
  concatenated, etc. Some sample records are:

stofler-irreliability                           A       1.2.3.4
disillusionized                                 A       1.2.3.4
galleriies                                      A       1.2.3.4
sportance                                       A       1.2.3.4
unidentifiable                                  A       1.2.3.4
lemonadelimequat                                A       1.2.3.4
orbdebary                                       A       1.2.3.4
digitinerved                                    A       1.2.3.4
character                                       A       1.2.3.4
adstipulating                                   A       1.2.3.4
carps                                           A       1.2.3.4

* Two zones were prepared, one with names in sorted order and another
  with a random order.
* 10 million queries were configured as queryperf input in random order.
* A single queryperf client was used.
* A single auth instance was used.
* b10-auth had a resident size of ~1.4 GB after loading a single
  example.org. zone.
* Against advice, both dnsperf and b10-auth were run on a single box (as
  I did not have two physical machines switched on during the testing).


Test results
------------

Rows are individual runs.

example.org. zone with names listed in sorted order in file:

avl_ord_time avl_ord_qps      rb_ord_time rb_ord_qps
191.455319   52231.5078642448 193.198696  51760.1837229792
191.663357   52174.8139890924 191.51159   52216.1609122456
189.991672   52633.8859736968 192.14696   52043.4983722875
188.520171   53044.7216706588 192.397784  51975.6506135227

example.org. zone with names listed in random order in file:

avl_rand_time avl_rand_qps     rb_rand_time rb_rand_qps
188.086994    53166.8872330428 181.326135   55149.2480661985
188.298732    53107.1021763439 179.666615   55658.6430929308
185.193476    53997.5825066321 180.222328   55487.0204539806
188.724055    52987.4159391075 178.789986   55931.5441749629

A plot with this data is attached as an image.


Comments
--------

* There doesn't seem to be a lot of difference between red-black tree
  and AVL implementations in query performance. A guess is that other
  factors count more than the height of the tree during query
  processing.

* Red-black trees performed slightly better than AVL trees when data was
  given in random order. I am not sure if this was due to the actual
  data itself being very suitable for a red-black tree, but this seems
  strange. Can someone else run such tests?

* In sorted order, AVL trees were very slightly faster.

* This is just a query performance test. We'd also need to measure
  insert performance, though it's not as important as query
  performance. AVL trees are expected to be slower than red-black trees
  in this case, but it may not make a major difference in our case.

* These are performance differences, but the major advantage AVL tree
  brings us is in code.

		Mukund
-------------- next part --------------
A non-text attachment was scrubbed...
Name: benchmark.png
Type: image/png
Size: 3825 bytes
Desc: not available
URL: <https://lists.isc.org/pipermail/bind10-dev/attachments/20130303/90c9eee4/attachment.png>
-------------- 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/20130303/90c9eee4/attachment.bin>