News for hackers. Stuff that matters.
Re:Searching 20 GB/sec: Systems Engineering Before Algorithms by dekhn on Monday May 12, 2014 @08:58AM (#7732415)
I have a hard time working between statements that say "O(n4) growth" and then reference cache lines- to me, cache lines are just faster RAM.

http://lemire.me/blog/archives/2013/07/11/big-o-notation-and...

I always think of big-O in terms of algorithm analysis, while real-world performance is more a function of operation costs/memory costs. Its use in the latter is more colloquial but I get what you mean now.

Re:Searching 20 GB/sec: Systems Engineering Before Algorithms by hvidgaard on Wednesday May 14, 2014 @03:53AM (#7742670)
As long as you do not have algorithmic dependence within the data in a cache line, you can regard calculation on that data as a constant that is dependent on the size of the data in the cache line. Even more so if you can utilize SIMD instructions. I know what I wrote wasn't clear on this, I was writing it in a hurry, sorry about that.

The reason I talk in cache lines, is because it's taking the real world aspect into the analysis of the algorithm. A theoretical analysis, while valuable in some aspects, are very far from the real world scenarios. I have done countless theoretical analysis of algorithms, found the actual (hidden) constants in big-O ect. but it just doesn't model the real world very well. This is the exact reason you see many fast algorithms use a naive, but cache friendly algorithm once the input is sufficiently small (e.g. with a divide and conquer algorithm).