In a previous blog entry, I discussed the difficulties associated with implementing left-leaning red-black trees. A couple of readers commented that treaps might be superior to red-black trees, and as part of some recent jemalloc optimization work, I had occasion to implement treaps in order to measure tree operation overhead.

Most of this article discusses performance, but let me first mention implementation difficulty. It took me about 90 hours to design/implement/test/benchmark left-leaning red-black trees, and less than 10 hours for treaps. Search/insert/delete for red-black trees is O(lg n), versus O(n) for treaps. However, the average case for treaps is (lg n), and the chances of worst case behavior are vanishingly small, thanks to (pseudo-)randomness. Thus, real-world performance differences are only incremental. To be fair, I made red-black trees harder by avoiding recursion. Regardless however, treaps are way easier to implement than red-black trees.

As for benchmarking, I wrote functionally identical benchmark programs for three red-black tree implementations and two treap implementations. The tree implementations are:

• rb_new: Left-leaning red-black trees.
• rb_old: Standard red-black trees.
• RB: Standard red-black trees, as implemented by the *BSD sys/tree.h.
• trp_hash: Treaps, with priorities computed via pointer hashing.
• trp_prng: Treaps, with priorities computed via pseudo-random number generation (PRNG).

The benchmark programs iteratively generate permutations of NNODES nodes, for NSETS node sets. For each node set, the programs iteratively build and tear down a tree using the first [1..NNODES] nodes in the set. Each insert/remove operation is accompanied by NSEARCH rounds of searching for every object in the tree, and NITER rounds of iterating over every object in the tree. Don’t worry too much about the details; in short the benchmark programs can be configured to predominantly benchmark insertion/deletion, searching, and/or iteration.

The following table summarizes benchmark results as measured on a 2.2 GHz amd64 Ubuntu 8.10 system. The benchmarks were all compiled with “gcc -O3”, and the times are user+system time (fastest of three runs):

Insertion/deletion is fastest for the red-black tree implementations that do lazy fixup (rb_old and RB). rb_new uses a single-pass algorithm, which requires more work. trp_prng is about the same speed as rb_new, but trp_hash is way slower, due to the repeated hash computations that are required to avoid explicitly storing node priorities.

Search performance is similar for all implementations, which indicates that there are no major disparities in tree balance.

Iteration performance is similar for all implementations, even though they use substantially different algorithms. If tree size were much larger, rb_old and RB would suffer, since they use an O(n lg n) algorithm, whereas rb_new and trp_* use O(n) algorithms. rb_new uses a rather complicated iterative algorithm, but trp_* use recursion and callback functions due to the weak upper bound on tree depth.

Sadly, there is no decisive winner, though any of the five tree implementations is perfectly adequate for the vast majority of applications. The winners according to various criteria are:

• Space: rb_new and trp_hash.
• Speed (insertion/deletion): rb_old and RB.
• Ease of implementation: trp_prng

Comments

At September 27, 2008 7:35 PM, Calvin said…

Great post… I was in search for a best data structure for my data grouping engine :) i think RB would be the best than AVL, AA, Skip list and all others..

Thanks.

At July 5, 2009 1:44 PM, Anonymous said…

Jason,

You pulled a comment about a week ago from one of our devs that looked at your non-recursive llrb tree implementation.

There were some issues w/ it leaning far left on ordered dataset insertion. If you’d like to take a look at our test cases, please just provide some contact info.

We would have contacted you directly before posting, but you don’t list any email or contact info.

Always looking for good work in the data structures space & we have a common interest in optimizing for C vs. C++.

Thanx!

-Tomas http://fuel7.com/

At July 5, 2009 2:15 PM, Jason said…

Tomas,

The comment you referred to provided no details on what might be wrong, and looked suspiciously like blog comment spam, so I removed it.

I’m interested in further details, and if there is in fact a problem, I definitely want to fix it. Are you aware that left-leaning red-black trees have a looser bound on tree height than standard red-black trees? Standard red-black trees have a maximum height that is (2lg n), where n is the number of tree nodes, whereas the maximum height for left-leaning red-black trees is (3lg n). If I recall correctly, ordered left-to-right insertion will exercise the worst case.

You can find links to test and benchmark programs on my red-black tree web page, as well as my email address.

Thanks, Jason