How to model execution time of algorithms?

Question

Which models of algorithm running time exist?

We all expect mergesort to be faster than bublesort, and note that mergesort makes O(n log n) comparisons vs. O(n²) for bubblesort.

For other algorithms, you count other operations (than compares and swaps), such as pointer dereference, array lookup, arithmetic on fixed-size integers, etc.

What other ways to model execution time are there?

One I know of myself is counting the number of block read from and written to disk; see my answer to http://stackoverflow.com/questions/941283/when-does-big-o-notation-fail for a lengthy description.

Another is counting the number of cache misses. This expands on the I/O model by looking at all levels of the memory hierarchy.

A third, for distributed algorithms (such as in secure multiparty computation) is to count the amount of data transmitted across the network (commonly measured in rounds of communication or number of messages).

Which other interesting things are there to count (and not count!) in order to predict the performance of an algorithm?

Also, how good are these models? As far as I've heard, cache oblivious algorithms are competitive with I/O-efficient algorithms for data on disk, but not for in-memory algorithms.

In particular: in which specific instances do these models mispredict relative performance? According to my own experiments, Fibonacci heaps don't speed up Dijstra's shortest path (versus binary heaps) when the data is small enough to fit in memory.

Answer 1

I think that whatever your basis for modelling execution time/space using O(n...) notations, you are assuming a normalized environment. I would think that whatever model you specify, and no matter how many variables you measure to determine it ... it only applies in a normalized environment. So when disk I/O is low in competition terms O(n...) may not be required to factor in those overheads ... if you see my point.

So O(n) models typical performance in a normalized environment on the input n.

By extension you can say disk reads are in the order O(n) or that memory allocations are order O(n) and so on. External events that add pressure (such as scheduling) shouldn't play a part in the model of typical time/space/occurrence of anything.

Or maybe I am missing your point (Which I suspect I might be).

Answer 2

You have to define a computational model, give an estimation of the cost of each operation and then analyse your algorithm in term of those costs; of course, the costs are determined by the particular environment and the characteristics of the underlying machine where you want to deploy your algorithm, so the question is really too generic.

In an algorithm course, we just assume that each operation costs 1, so we just count how many times we loop; in algorithms that works with main memory, we assume that each operations, apart read/write from I/O, costs 0 (and read/write 1), and so on.

Are those models tight with the reality? It depends on the reality: your environment and your machine.

Your calculation with cache misses could be correct on a core duo, but wrong with a cell processor, where you have to transfer manually the contents of the memory of SPEs, for example.

Answer 3

For the realtime platforms I work on, lately I find that copying largeish amounts of data (eg: in the KB range, not the MB range) is actually way quicker than I've been trained to expect. Probably this has to do with the large caches in use today, or perhaps just the blazing fast processor speed. But the effect is that one really shouldn't bother to pervert one's code too badly anymore just to avoid data copies.

Instead, the things I really have to look out for are device accesses and context switches. The fewer of those, the better.

The days when "zero buffer" device drivers were synonomous with speed are over.