4 ms·

Modern CPUs do exactly this right now. If you are using a powerful x86 (not an old atom), it will process your software out of order. Both your compiler and the

Modern CPUs do exactly this right now. If you are using a powerful x86 (not an old atom), it will process your software out of order. Both your compiler and the CPU itself are aggressively trying to execute as many LOADs as possible before work can't continue. Or were you describing something more than that?

nkurz 11y ago
I'm arguing that modern superscalar out-of-order hardware supports lots of parallelism, but that modern compilers (and software practices) leave a lot of performance on the table. The key to overcoming latency is concurrency, and current software rarely manages to reach its potential. This makes it look like hardware isn't getting faster, but really it's just not getting faster at running software targeted at earlier in-order CPU's. Consider performing a series of simplified hash table lookups based a list of strings. You hash the first string, use the prefix of the hash as an array offset to look up another pointer, use the pointer to access a variable length array, and then check whether you have a matching element. Then you hash the second string, and repeat. Third, fourth, etc. To achieve high performance, you need to overlap the lookups, so that the latencies are shared rather than sequential. But I don't know of any compilers (although I'm only familiar with GCC, Intel, and Clang) smart enough to do so. The hardware tries to get out ahead, but will almost always experience a branch prediction error before it can start working on the next iteration. And if it does manage, it will usually get at most a single iteration ahead. By contrast, if you were to do 8 hashes in parallel (often just as fast with AVX2), and then issue 8 loads, then chase those 8 pointers in parallel, you've increased your throughput almost 8x. Little's Law is the low-hanging fruit, and you don't need to figure out how to do cycle accurate synchronization between cores. I realize I probably sound like a quack. Here's a more formal paper describing some similar approaches with a Cuckoo Hash: http://www.cs.columbia.edu/~orestis/sigmod15.pdf http://www.cs.columbia.edu/~orestis/sigmod15.pdf
- fmstephe 11y ago
  I'm glad I commented on your comment. You certainly were describing much more that out-of-order execution. Good food for thought :)
  - nkurz 11y ago
    Just came across a good paper that discusses these issues: http://arxiv.org/pdf/1509.05053v1 http://arxiv.org/pdf/1509.05053v1 The approach it from a different angle, but come to similar conclusions: Our conclusion is contrary to our expectations and to previous findings and goes against conventional wisdom, which states that accesses to RAM are slow, and should be minimized. A more accurate statement, that accounts for our findings, is that accesses to RAM have high latency and this latency needs to be mitigated. ... Our results show that, in a processor that has speculative execution, one can obtain many of the benefits of runahead even on processors that do not specifically implement it. While this may not be news to hardware experts, to the best of our knowledge, we are unaware of any algorithms (or even implementations) that deliberately make use of it. I would suggest this is a very fruitful direction to pursue.
    - fmstephe 11y ago
      Great paper, I am building a red-black tree at the moment (well, rebuilding one I wrote earlier), so I will try test out some of the techniques described here and see if I can get any speed out of it. If I get any clear results, I'll ping you back here. Cheers.
    - deleted 11y ago
      [deleted]

nkurz 11y ago

I'm arguing that modern superscalar out-of-order hardware supports lots of parallelism, but that modern compilers (and software practices) leave a lot of performance on the table. The key to overcoming latency is concurrency, and current software rarely manages to reach its potential. This makes it look like hardware isn't getting faster, but really it's just not getting faster at running software targeted at earlier in-order CPU's. Consider performing a series of simplified hash table lookups based a list of strings. You hash the first string, use the prefix of the hash as an array offset to look up another pointer, use the pointer to access a variable length array, and then check whether you have a matching element. Then you hash the second string, and repeat. Third, fourth, etc. To achieve high performance, you need to overlap the lookups, so that the latencies are shared rather than sequential. But I don't know of any compilers (although I'm only familiar with GCC, Intel, and Clang) smart enough to do so. The hardware tries to get out ahead, but will almost always experience a branch prediction error before it can start working on the next iteration. And if it does manage, it will usually get at most a single iteration ahead. By contrast, if you were to do 8 hashes in parallel (often just as fast with AVX2), and then issue 8 loads, then chase those 8 pointers in parallel, you've increased your throughput almost 8x. Little's Law is the low-hanging fruit, and you don't need to figure out how to do cycle accurate synchronization between cores. I realize I probably sound like a quack. Here's a more formal paper describing some similar approaches with a Cuckoo Hash: http://www.cs.columbia.edu/~orestis/sigmod15.pdf http://www.cs.columbia.edu/~orestis/sigmod15.pdf

fmstephe 11y ago
I'm glad I commented on your comment. You certainly were describing much more that out-of-order execution. Good food for thought :)
- nkurz 11y ago
  Just came across a good paper that discusses these issues: http://arxiv.org/pdf/1509.05053v1 http://arxiv.org/pdf/1509.05053v1 The approach it from a different angle, but come to similar conclusions: Our conclusion is contrary to our expectations and to previous findings and goes against conventional wisdom, which states that accesses to RAM are slow, and should be minimized. A more accurate statement, that accounts for our findings, is that accesses to RAM have high latency and this latency needs to be mitigated. ... Our results show that, in a processor that has speculative execution, one can obtain many of the benefits of runahead even on processors that do not specifically implement it. While this may not be news to hardware experts, to the best of our knowledge, we are unaware of any algorithms (or even implementations) that deliberately make use of it. I would suggest this is a very fruitful direction to pursue.
  - fmstephe 11y ago
    Great paper, I am building a red-black tree at the moment (well, rebuilding one I wrote earlier), so I will try test out some of the techniques described here and see if I can get any speed out of it. If I get any clear results, I'll ping you back here. Cheers.
  - deleted 11y ago
    [deleted]