4 ms·
> In fact, perf showed that the query server as a whole was spending 4% of its CPU time on one instruction in that loop: Looks like 40% to me actually. I think
by dragontamer 7y ago
> In fact, perf showed that the query server as a whole was spending 4% of its CPU time on one instruction in that loop:
Looks like 40% to me actually. I think there's a typo here. EDIT: The tweet is more clear. 4% of the total CPU time for the whole program. The 40% in that line is only for that particular function (I presume the function is taking ~10% total CPU time, and 40% of that is on that singular instruction)
------
> The first thing to note is that instruction-level profiling tends to put the blame on the instruction following the one that triggered a sampling interrupt.
Hmm, in my experience with AMD-based hardware profiling, AMD CPUs may place the blame as far back as ~200 instructions (pathological worst-case) behind the instruction that was interrupted.
This is most obvious on AMD branch mispredictions. A branch mispredict can, by definition, only happen on branch instructions (a cmp/jmp pair, since cmp/jmp turn into a single double-instruction micro-op on both AMD and Intel). But you'll find mispredictions "blamed" on all sorts of non-branching instructions on AMD-hardware. Its a known limitation of AMD's hardware performance counters.
In the first case, the modvqu is almost certainly where the 40% of the time is being spent... later on there is...
9.91 | lea (%r12,%12,4),%rax
0.64 | prefetcht0 (%rdx,%rax,8)
17.04 | cmp %rcx,0x28(%rsp)
I can't imagine that the prefetch0 instruction is taking up 17% of the time of the function. I expect that the 17% here must be something else. In particular, Agner Fog's manuals state that PREFETCHINTA/0/1/2 has 1-latency and 2-instructions/clock throughput: a very fast instruction under Agner Fog's test case on both Intel Skylake and AMD Zen.
AMD has "instruction base sampling", a difficult to understand but more accurate profiling methodology. Intel has PEBS, precision event-based sampling, which helps narrow down the specific instruction to "blame".
This blogpost doesn't say which CPU its using, but unfortunately, these little details do matter. Ultimately, I'd investigate more before concluding the prefetcht0 instruction is actually the problem.
If Store Forwarding might be an issue, then LD_BLOCKS.STORE_FORWARD event on Intel Skylake would be a performance counter to check.
--------------
> and accelerate random accesses to the hash table with software prefetching.
Does prefetching actually help in this case? Have you tested the code without prefetching?
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.
I wouldn't necessarily be "surprised" if prefetching helps in this case... but its not necessarily a given.
- anarazel 7y ago> 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.