News for hackers. Stuff that matters.
Re:Searching 20 GB/sec: Systems Engineering Before Algorithms by hvidgaard on Friday May 09, 2014 @03:34AM (#7719794)
When analyzing big data algorithms, the amount of computation by the CPU is often irrelevant. It's ignored. What matters is disk reads and disk access patterns. If you can make a scanning algorithm that start at byte 0, and reads everything once in a sequential manner, you can make O(n^4) computation with it. The CPU will be long finished with the inefficient computation by the time the next set of data is retrieved from the (spinning) disk.

And on using Java. It's actually pretty fast, and certainly fast enough for a prototype. Once you have the stack build, you can benchmark and optimize the bits that needs to be optimized, usually this means C or handcrafted ASM.

Re:Searching 20 GB/sec: Systems Engineering Before Algorithms by dekhn on Friday May 09, 2014 @08:19AM (#7720429)
I don't think I've ever heard anybody claim that streaming algorithms permit O(n4) computation. That seems implausible. Most streaming algorithms are linear, or sublinear. I'm not sure what you meant by O or n or 4, however.
Re:Searching 20 GB/sec: Systems Engineering Before Algorithms by raphaelj on Friday May 09, 2014 @08:55AM (#7720552)
Indeed, there will always be an instant, given that "n" is increasing toward infinity, when the computation time will take over the streaming time.

Systems complexity are always bounded by their algorithm having the greatest complexity. As streaming is linear, there will always be a value of "n" after which the computation will take over, even with a very quasi-linear complexity (even an O(n^1.00000001) computation will be slower than the streaming for very very large values of n).

Re:Searching 20 GB/sec: Systems Engineering Before Algorithms by hvidgaard on Monday May 12, 2014 @04:18AM (#7731648)
I should have mentioned that it implies that you can work on sufficiently small values of n, usually measured in how many cache lines it takes up. Saying that "there will always be a value of "n" after which the computation will take over" is, while true, completely theoretical. Not that it have its uses, but I have yet to see a IO heavy process being limited by the CPU. If it's streaming, it's usually also quite simple to process, and if it's random access the CPU is doing something else most of the time.
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).

Re:Searching 20 GB/sec: Systems Engineering Before Algorithms by hvidgaard on Monday May 12, 2014 @04:30AM (#7731670)
I wrote it in a hurry. O(n^4) is only for the size of the current chunk of data being operated on, usually measured in cache lines. I guess it should have been m, as n is usually used for the total input size. It's not unusual to see O(m^c * log n) algorithms or even O(m^c * log log n) if you can use vEB search structure, where m is the number of cache lines the algorithm works on, c is an algorithm specific constant, and n is the total input size.
Re:Searching 20 GB/sec: Systems Engineering Before Algorithms by dekhn on Monday May 12, 2014 @08:53AM (#7732398)
Ah, OK. So you meant space overhead in practical terms

I would think that a greater than constant time overhead would not be compatible with a real time streaming operation. just a guess, though.

Thanks for mentioning http://en.wikipedia.org/wiki/Van_Emde_Boas_tree as I hadn't heard of that. The last paragraph on the page gives some nice pointers (use a trie or randomized hash table).