Too much locality for stores to forward

This is a great little article. I find too many programmers don't understand the value of batches, at every level of code. Batching is super important, both to amortize fixed costs and to reduce serialized blocking for "IO" (this case, if we define IO as "operations which fetch data from a slower data source than the one upon which we're operating").

There's another mistake programmers are prone to make after learning about the importance of batching. If batches of ten are good, why not a hundred? Why not a million? Lots of people make the mistake, after learning the value of batches, of assuming that bigger is always better. This isn't the case either. There are a few reasons why too large batches can also cause problems. For streaming work, large batches hurt latencies of initial results. Access locality can also be harmed when batches are too big. If your cache can fit a hundred of your objects and you perform operations batch-wise in batches of a thousand, you have to fetch each object from main memory per batch. If you worked in units of a hundred instead, then you would fetch each object from main memory once.

I find there are a couple of good rules of thumb for batching. Batches should be as small as possible, as long as they are large enough to solve the issues I mentioned earlier. I like to target batch sizes that are large enough that the fixed costs are no more than about 5% of the total costs of executing the batch. In the case of CPU-local work like the one described in this article, you would pick batch size s.t. operation 0 and associated fetches have finished on batch element 0 before you loop back to it to begin work on operation 1. In network situations where tracking batch completion and context switching is less expensive, this doesn't make as much sense. Just make it so that multiple batches can run concurrently, and issue multiple network requests to handle each one.

Backtrace hires thoughtful people. (Disclosure: didn't hire me. :-) It seems to come from the top: Sami al-Bahra is thoughtful.

Backtrace does what was to me a surprising service: they aggregate crash dumps and stack tracebacks, in bulk, from their customers' customers' failed programs, so that the causative bug can be identified and fixed.

> 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.

I just started reading, but why does it say "(semi)group" instead of "semigroup / monoid"? I've never heard of inversion being used to perform a fold.