4 ms·
I agree with the fundamental point in the article, but isn't it well known that when you consider multiple levels of the memory hierarchy as a whole, big O nota
by sn41 10y ago
I agree with the fundamental point in the article, but isn't it well known that when you consider multiple levels of the memory hierarchy as a whole, big O notation needs to be modified to take into account the relative cost of access?
I think the problem is not so much the big-O notation, but that the underlying assumption that the data access is from an "all main memory" model with no cache or secondary storage is often forgotten.
For example, in database algorithms, all memory operations are often considered to be unit cost since they are an order cheaper when compared to accessing the disk storage?
- geophile 10y agoBig O notation is typically counting comparisons, and ignores constant factors. It isn't that memory hierarchy is ignored so much as the equating of comparison growth (in n) with performance. The field of cache oblivious algorithms is focused explicitly on memory hierarchy, and accounts for cache misses.
- SamReidHughes 10y agoIt's typically not counting comparisons, there are none when inserting elements. But sometimes it pretends that comparisons are O(1).
- SamReidHughes 10y agoThat depends on whether you expect the data to already be in memory or not. If it's already in memory, you would care a lot about cache locality. And in general, you don't want to spuriously lose on some benchmark if there's anything you can do about it.