Since 2004, I and my research collaborators have been studying the
performance of different priority queues for different sets of
operations to be supported. At the theoretical level, we have measured
the goodness in terms of the comparison complexity of different
operations. As the other optimization criteria, we have considered how
to reduce the number of instructions, branch mispredictions, cache
misses, and element moves. At the practical level, we have used the
actual running time as the key performance indicator. We have done
most of our experiments on synthetic operation sequences, but we have
also done some application engineering.
In this talk I will briefly survey the theoretical results obtained
and I will discuss the methodological issues encountered when
performing the practical experiments. As a teaser, consider the
What is the best priority queue?
- When to implement a data structure?
- Does a factor of two matter?
- Does the space efficiency matter?
- What is the effect of different hardware phenomena?
- How to measure the practical performance?
- What to do next?
It goes without saying that I do not have complete answers to these questions.