Hacker News Reader

Comment by stiff | Hacker News Reader

http://en.wikipedia.org/wiki/Asymptotically_optimal_algorith...

Sometimes vague or implicit assumptions can make it unclear whether an algorithm is asymptotically optimal. For example, a lower bound theorem might assume a particular abstract machine model, as in the case of comparison sorts, or a particular organization of memory. By violating these assumptions, a new algorithm could potentially asymptotically outperform the lower bound and the "asymptotically optimal" algorithms.

http://en.wikipedia.org/wiki/Random-access_stored-program_ma...

http://en.wikipedia.org/wiki/Cache-oblivious_model

etc.

As far as I know all asymptotic analysis has to be done using some abstract machine model.

View on HN

Sure, but how do modern architectures not fit into the RASP machine model? You can view the cache contents as being part of the state (rather than the memory); you can similarly view instructions as being part of sequences, so that a single instruction can mean different things depending on the state from which it is fetched. Other modern features can be similarly approached (with the exception of CPUs whose behavior depends on environmental factors like temperature, but that is an edge case).

Really, if you doubt that the RASP model is appropriate for modern architectures, you can test it (a typical exercise in an algorithms course) -- see if, as the input size grows, the timing follows the asymptotic analysis. That is basically what the article you linked to does, and the results are not all that surprising -- where things are linear time in theory, they are linear time in practice; where they are quadratic time in theory, they are quadratic time in practice. It is worth pointing out that in all but the last example, the list and vector operations had the same complexity (because of the linear search), so it was really a comparison between constant factors.

Asymptotically, sure, you're right. Constant factors are often important in practice, and simple cost models (e.g. ones that don't model cache locality) will no longer give you a decent estimate of constant-factor differences in performance between algorithms.

I think the issue here is that, in the past, with shallower cache hierarchies, models that assumed a constant cost per memory access would maybe be off by smallish factor (I don't know, maybe 50%).

However, now memory access is frequently the limiting factor for an algorithm, and there can easily be an order of magnitude in variation between the average memory access latency for different algorithms (i.e. cache-smart versus cache-dumb).

Reply on news.ycombinator.com