2 ms·

> Without prefetching, a MODERN processor will NOT "stall" on the load instruction. A modern processor will execute out-of-order, branch predict the next iterat

> Without prefetching, a MODERN processor will NOT "stall" on the load instruction. A modern processor will execute out-of-order, branch predict the next iteration (its an inner loop, so its probably always taken), and then effectively achieve the same throughput anyway. It's a hash-table insertion. That's usually poorly predictable. The post explicitly talks about out of order execution, and why it's of limited help here. See the second "Hypothesis" paragraph. And then talks about how to change the code to allow to utilize out of order execution.

dragontamer 7y ago
> The post explicitly talks about out of order execution... I understand that. But there's no time in the post that demonstrates that prefetching was useful or not. > It's a hash-table insertion. That's usually poorly predictable. If he is always inserting 8 elements, the CPU (might) be able to figure out that it needs to insert 8-elements in that loop. The hash-table insertion itself will fail to be predicted. But there's nothing the programmer can really do about that. However, by having a constant 8-buffer sized "insertion batch", you provide an easily predicted loop to the CPU. There will almost always be 8-elements inserted into the hash table, and CPUs can accurately predict constant-sized loops under 20-iterations or so... maybe 30-iterations depending on how recent your CPU is. These 8x insertions WILL be predicted. That means your CPU will be OoO executing these 8x insertions. Each insertion may be unpredictable from a branch-prediction perspective (rehash 0x, 1x, or 2x? Depends on the hash table, probably unpredictable), but that doesn't change the dependency graph, so I expect the CPU to OoO the next iteration anyway. -------------- In any case, I think prefetching is an open question still. I think this is a good blog post, but I'm curious if the author did any prefetching experiments.
- atq2119 7y ago
  > Each insertion may be unpredictable from a branch-prediction perspective (rehash 0x, 1x, or 2x? Depends on the hash table, probably unpredictable), but that doesn't change the dependency graph, so I expect the CPU to OoO the next iteration anyway. This does matter, actually. As soon as the first branch inside an individual item's insertion is mispredicted, all the following instructions will be discarded and must be re-executed. The out-of-order logic in the CPU cannot tell that there is a subset of inflight instructions that will be executed regardless of the outcome of the branch. The re-execution is likely cheaper though, because the earlier speculative execution ensures that the relevant caches are already populated.

dragontamer 7y ago

> The post explicitly talks about out of order execution... I understand that. But there's no time in the post that demonstrates that prefetching was useful or not. > It's a hash-table insertion. That's usually poorly predictable. If he is always inserting 8 elements, the CPU (might) be able to figure out that it needs to insert 8-elements in that loop. The hash-table insertion itself will fail to be predicted. But there's nothing the programmer can really do about that. However, by having a constant 8-buffer sized "insertion batch", you provide an easily predicted loop to the CPU. There will almost always be 8-elements inserted into the hash table, and CPUs can accurately predict constant-sized loops under 20-iterations or so... maybe 30-iterations depending on how recent your CPU is. These 8x insertions WILL be predicted. That means your CPU will be OoO executing these 8x insertions. Each insertion may be unpredictable from a branch-prediction perspective (rehash 0x, 1x, or 2x? Depends on the hash table, probably unpredictable), but that doesn't change the dependency graph, so I expect the CPU to OoO the next iteration anyway. -------------- In any case, I think prefetching is an open question still. I think this is a good blog post, but I'm curious if the author did any prefetching experiments.

atq2119 7y ago
> Each insertion may be unpredictable from a branch-prediction perspective (rehash 0x, 1x, or 2x? Depends on the hash table, probably unpredictable), but that doesn't change the dependency graph, so I expect the CPU to OoO the next iteration anyway. This does matter, actually. As soon as the first branch inside an individual item's insertion is mispredicted, all the following instructions will be discarded and must be re-executed. The out-of-order logic in the CPU cannot tell that there is a subset of inflight instructions that will be executed regardless of the outcome of the branch. The re-execution is likely cheaper though, because the earlier speculative execution ensures that the relevant caches are already populated.