How to design a performance comparison between two data structures

Question

I want to compare the performance of two search trees of integers (an AVL tree and a RedBlack tree). How should I design/engineer the tests to accomplish this? For example, let's consider the insert operation; what steps should I follow in order to state that on average this operation is faster in the RB case? What considerations should I take to correctly measure CPU time? Should both implementations be optimized, or may I compare an optimized implementation of AVL vs a straightforward implementation of RB?

Any links or papers would be very helpful.

Answer 1

It highly depends on what you plan to do with the data structure. If you will end up filling it with a certain structured input, then you should also test it that way.

If you don't know anything about your future inputs and want to measure average performance, then remember that complexity theory calculates average performance based on randomized inputs (using a normal distribution). Hence, average-case performance test should include many runs with varying random inputs.

Depending on the data structures themselves, you may also be interested in comparing certain input structures that are known to be very good/bad for one of the data structures. Nevertheless, your future application of the data structure may almost never create such inputs, in which case you may well ignore the performance comparison of these cases. (Intuitive Example: comparing sort algorithms in a context, where you often try to sort an already sorted sequence could throw many quicksort implementations off.)

As for your optimization point, the answer again is: It depends. Are you aiming for using this data structure in exactly that one project right now? Then I'd go for optimized versions. Are you aiming at a comparison to get a general idea on which one might be more suitable for a planned project? Then try to compare reference implementations, but do not waste time on creating super-efficient implementations. Of course, the context in which you execute the tests has to be comparable, so don't try to f.ex. compare implementations in different programming languages to each other. Probably obvious, but I just thought I'd make sure to mention it.

Answer 2

Be careful with terminology. Data structures don't have performance; algorithms do. It's true that some data structures are designed specifically to enable their corresponding algorithms, but it's still a good idea to keep the distinction in mind.

For example, you asked about comparing "optimized" AVL to "straightforward" RB. If you think in terms of algorithms, then you're just comparing one algorithm to another. You can compare all the different flavors of algorithms that do the same task: optimized AVL insertion, straightforward AVL insertion, optimized RB insertion, straightforward RB insertion, heap insertion, linked list insertion, etc. They all accomplish similar goals, so comparing them is useful.

A typical way to do this sort of thing is to build a test harness that will run each algorithm the same way using the same data the same number of times. For example, you might write a function that takes a function (the algorithm), a data set, and a number of repetitions as parameters. The function would then run the algorithm using the data for that number of reps, and return the elapsed time.

Answer 3

Algorithms can be compared by identifying some basic operation, such as comparisons, and counting them, as a function of the amount of input data.

Programs are much more difficult to compare, because you can't make a fair comparison without controlling all sorts of extraneous variables. On top of that, if any two programmers write programs to do the same thing, one will take longer than the other, by reason of silly little design decisions. I've never seen a significant program that, as first written, didn't have a lot of room for speedup. It's like dipping a towel in water. It comes out sopping wet. If you squeeze it (tune it) you can get a lot of the water out. If you squeeze it harder, you can get more water out. If you squeeze it really hard, you can get most of the water out, but it will still be damp. There's a tradeoff between the program's speed and how hard you try to tune it, and that's a variable that's hard to control between programs.