Re: libavl 2.0.3 slower than 1.4.1

[Ben Pfaff]

On Fri, Nov 21, 2014 at 09:59:56AM +0100, Daniel Brahneborg wrote:
> In one of our applications we're using right-threaded AVL
> trees from libavl 1.4.1. Now I found version 2.0.3, saw
> that red-black trees might be faster, and made some tests.
> Version 1.4.1 has worked fine, but better performance is
> always welcome. :)
> 
> Our data is almost always inserted in order, but sometimes
> items needs to be pushed back a bit. Thus, AVL trees. The
> only operations we do on this are "insert" and "extract first".
> 
> With version 1.4.1 adding 10M items and extracting them
> from two threads takes 19 seconds. With the red-black trees
> from version 2.0.3 this takes 31 seconds. Shouldn't RB trees
> be faster?

Have you read my paper at http://benpfaff.org/papers/libavl.pdf?  I
think that you would be interested in this conclusion from section 6.1:

    In the best case for unbalanced BSTs, that is, insertion of items in
    random order, unbalanced trees are the best choice because of their
    low time and space overhead. If items are normally inserted in
    random order but include occasional runs in sorted order, then
    red-black trees are preferred to AVL trees because their more
    relaxed balancing rule does less work attempting to balance already
    random data. Splay trees are undesirable, because of the cost of
    splaying on every access.

    In the worst case for unbalanced BSTs, that is, insertion of items
    in sorted order, splay trees are the best choice as long as
    subsequent accesses tend to be somewhat sequential (as in the VMA
    experiment in section 5.1) or clustered (as in the cross-reference
    experiment in section 5.3). Splay trees should not, how- ever, be
    used if bounded performance guarantees are required. Otherwise, AVL
    trees are a better choice because they tend to keep the maximum path
    length below that for red-black trees, although the internal path
    length for AVL and red-black trees is comparable. Unbalanced BSTs
    should not be considered.

    Real-world situations fall somewhere between the two extremes: in
    two of our experiments red-black performance was better than AVL
    performance and in the other one it was the reverse; in one, splay
    trees were better than either. The choice of data structure can then
    be made based on which extreme is thought more likely or for which
    performance is more important, or based on actual tests