BeeOnRope

Really interesting. Normal uops don't work like that, they are always pipelined, so a p06 op with 3-cycle latency would always be 3/0.5, not 3/1.

So the 1-throughput strikes me as a renamer limit, not an execution limit. I.e., these instructions can only flow through the renamer at 1 per cycle.

This could perhaps be tested by interleaving unrelated p06 ops in the same ratio as SHLX, and see if they + SHLX are able to saturate p06, and also trying different interleaving granularities like 1:1 and 5:5 since I would expect those to behave differently in the renamer (but not much different in execution).

How did you test the throughout? Seems quite weird. Does it go to both ports still?

The slow state is when rcx has a special "hidden immediate" attached it, from the `mov rcx, 1` or `add rcx, 1`. If the last option on the register doesn't fit that narrow template, it is fast, so loading from memory in any way, like pop, xrestor, plan load, etc, will be in fast mode.

Yeah I am pretty sure that the renamer adds the tracked immediate(s) to the emitted uop, but that's not inconsistent with tracking "reg offset pairs" is it?

It's true, I was considering only the original mov rax, 1 case, which I'm pretty sure compilers don't generate: it's just a useless encoding of mov eax, 1.

Given that 64-bit immediate math also causes this though, compilers might generate it (I think this is a minor missed optimization by gcc though: it could have used add eax, 1 instead.

Does this also occur with other 3-argument instructions like ANDN?

To rule out alignment you should adding padding to one so the two variations have the same alignment in their long run of SHLX (I don't actually think it's alignment related though).

Worth noting that whether intentional or not, this would be easy to miss and unlikely to move benchmark numbers since compilers won't generate instructions like this: they would use the eax form which is 1 byte shorter and functionally equivalent.

Even some assemblers will optimize this for you.

Division is complicated by the fact that it is a complex micro-coded operation with many component micro-operations. Many or all of those micro-operations may in fact be pipelined (e.g., 3/1 lat/itput) , but the overall effect of executing a large number of them looks not very pipelined at all (e.g., 20 of them on a single EU would have 22/20 lat/itput, basically not pipelined when examined at that level).

We are interested in the software visible performance effects of pipelining. For small benchmarks that don't miss in the predictors or icache, this mostly means execution pipelining. That's the type of pipelining the article is discussing and the type of pipelining considered in instruction performance breakdowns considered by Agner, uops.info, simulated by LLVM-MCA, etc.

I.e., a lot of what you need to model for tight loops only depends on the execution latencies (as little as 1 cycle), and not on the full pipeline end-to-end latency (almost always more than 10 cycles on big OoO, maybe more than 20).

Yes. In the past new HW has been made available to the uops.info authors in order to run their benchmark suite and publish new numbers: I'm not sure if that just hasn't happened for the new stuff, or if they are not interested in updating it.

Division, gather are muti-cycle instructions which have typically had little or no pipelining on x86.

Yes, it applies to different operations. E.g. you could interleave two or three different operations with 3 cycle latency and 1 cycle inv throughput on the same port and get 1 cycle inv throughput in aggregate for all of them. There is no restriction that they must be same operation.

In some cases mixing operations with _different_ latencies on the same execution port will leave you with less throughput than you expect due to "writeback conflicts", i.e., two instructions finishing on the same cycle (e.g., a 2 cycle operation starting on cycle 0 and a 1 cycle operation on cycle 1, will both finish on cycle 2 and in some CPUs this will delay the results of one of the operations by 1 cycle due to a conflict).

I don't think anyone is talking about "fetch, decode, operate, retire" pipelining (though that is certainly called pipelinig): only pipelining within the execution of a instruction that takes multiple cycles just to execute (i.e., latency from input-ready to output-ready).

Pipelining in stages like fetch and decode are mostly hidden in these small benchmarks, but are visible when there are branch misprediction, other types of flushes, I$ misses and so on.

That's true, but another part of the tables show how many "ports" the operation can be executed on, which is enough information to concluded an operation is pipelined.

For example, for many years Intel chips had a multiplier unit on a single port, with a latency of 3 cycles, but an inverse throughput of 1 cycle, so effectively pipelined across 3 stages.

In any case, I think uops.info [1] has replaced Agner for up-to-date and detailed information on instruction execution.

---

[1] https://uops.info/table.html

So does the TV have to scan all RF channels at startup to build a virtual->RF channel map?

> There are also some EC2 instance classes where upgrading instance types in the same "size" are more expensive

An increase in price has been the rule rather than the exception for recent upgrades for vanilla instance types, e.g., c, r, m types in the newest generations (6 -> 7 for x86, 6 -> 7, or -> 8 for Arm types).

The increases have been modest though, perhaps around 10%. You get additional CPU and sometimes minor increases in other resources on the newer types.

Yes it the same for Intel.

One quantitative difference is that tasks assigned to the E cores may run at a sustained frequency much lower than the maximum (3.7x here) while on Intel any sustained load generally results in frequency scaling up over a few 100 ms to a maximum value which is much closer to the absolute max.

They won't be mispredicted nor take predictor resources since the default prediction is "not taken" and these branches are never taken (except perhaps once immediately before an OOB crash if that occurs). So they are free in that sense.

> When that trick can't be used, I think the most efficient method would be to clamp the top of the address so that the max would land on a single guard page.

If you are already doing a cmp + cmov, wouldn't you be better off just doing a cmp + jmp (to OOB handler)? The cmp + jmp can fuse, so it's probably strictly better in an execution cost sense, plus it doesn't add to the critical data-dependent chain of the load address, which would otherwise add a couple of cycles to the address data chain.

Of course, it does require you have these landing pads for the jmp.

> Can you be more specific about "all execution after a mispredict is thrown away". Are you saying even non-dependant instructions?

To clarify, the misprediction happens at some point in the linear instruction stream, and all instructions and results before that in the linear stream are kept and everything after is thrown out. Everything after is wrong because the stream of instructions didn't go down the expected path, so it's not even really about instruction dependencies at that point: the wrong stream of instructions executed in the first place.

In some cases the wrong and good paths join up very quickly, e.g.:

    cmp rax, rax
    jl  over
    inc rax
  over:
    ...

In this case the jump is over a single instruction so even if mispredicted the right stream will vary only in the `inc` instruction, so in principle it seems possible to save some of the further work which doesn't depend on rax, but this is very difficult in practice and no CPU does it in a general way that I know of. I believe some POWER arches could actually internally covert the pattern a above into the moral equivalent of a predicated operation, removing the branch completely, but that's a different thing entirely with a different set of tradeoffs.

Nice article!

Very cool to see both the "independent" and "serially dependent" cases addressed. Microbenchmarks still have lots of ways of giving the wrong answer, but looking at both these cases exposes one of the big variables which cause that.

In my experience looking at container performance you often pass through two distinct regimes (in a microbenchmark!):

Small regime: for small containers, instruction count, instruction dependencies and IPC (including the effect of branch missed) dominate.

In this regime fastest container in a "throughput" sense will often be the one with fewest micro-operations (including those executed on the wrong-path). Fewer operations helps both in raw speed and also in overlapping more multiple independent lookups within the instruction window. Any type of per-lookup misprediction is hugely destructive to performance. For random keys, this often favors hash tables because they can be written to have << 1 mispredict per lookup.

In this small regime the fastest container in a latency sense is the one with the shortest critical path from input to output, again considering mispredicts. The non-memory latency instruction will be very important in this critical path and again mispredicts are very destructive since usually mispredicts add directly to the critical path (not always!). There are lots of tricks to keeping the critical path including hashes with somewhat higher operation counts but smaller critical paths (e.g., a short merge), linear searches which have > 1 independent stream, etc. If the keys are predictable, hashes containers can look bad because they tend to have a long data-dependency from the hash through the lookup to the output. Tree-like containers tend to replace those with control, so the data-dependent critical path can be very short! With random keys, hashes win again because mispredicts are so destructive.

Then in the large regime, a lot of the same themes repeat but instead of applying to "all instructions", it's mostly about memory access. I.e., the winning throughput containers are the ones that can get the highest useful MLP, and the winning latency containers are the ones with the shortest critical path of data-dependent memory accesses, mostly ignoring everything else. Instructions still matter because MLP is often dependent on how many accesses you can stuff into the processors OoOE execution window, and the size of that structure is (roughly speaking) counted in instructions. Software prefetching can help a ton with stuffing the right memory accesses in the OoOE window.

For random keys and "usually hit", hashes again tend to win in this regime, because they can usually get down to 1 miss per lookup, and that's math the other structures just can't overcome. For non-random keys, the field is wide open, it depends heavily on the key distribution. For lookups which often miss there are plenty of ways to break the 1 miss-per-lookup barrier too.

I guess we are probably in violent agreement on most of this.

> Spectre mitigations don't change that, ...

Yes, exactly. To the first order I think Spectre didn't really change the performance of existing userspace-only code. What slowed down was system calls, kernel code and some things which were recompiled or otherwise adjusted to mitigate some aspects of Spectre. There might be a rare exception, e.g., IIRC `lfence` slowed down on AMD in order to make it more useful as a speculation barrier on AMD but this is hardly an instruction that saw much use before.

> I don't know what the state of the art is, although I've seen results showing both speedups and slowdowns

Yeah. This seems like a pretty cut and dry case where you'd get a speedup from wrong-path misses, since the independent next search will be correctly predicted from the start and access exactly the right nodes, so it serves as highly accurate prefetching: it only gets thrown out because of a mispredict at the end of the _prior_ search.

Something like the misses within a single binary search are more ambiguous: for random input the accuracy drops off like 0.5^n as you predict n levels deep, but that still adds up to ~double MLP compared to not speculating, so in a microbenchmark it tends to look good. In the real world with 1 lookup mixed in with a lot of other code, the many cache lines brought in on the bad path may be overall worse than inserting a speculation barrier yourself.

That's the cool part: we can choose whether we want speculation or not if we know up front if it's harmful.

No, just a consequence of how mispredicts work: all execution after a mispredict is thrown away: though some traces remain in the cache, which can be very important for performance (and also, of course, Spectre).

To answer a question implied in the article, per-lookup timing with rdtscp hurts the hash more than the btree for the same reason the hash is hurt by the data-depending chaining: rdtscp is an execution barrier which prevents successive lookups from overlapping. rdtsc (no p) isn't, and would probably produce quite different timings.

That the btree doesn't benefit from overlapping adjacent lookup/inserts is intereting.

I suppose it is because btree access (here) involves data-dependent branches, and so with random access you'll get about L mispredicts per lookup in an L-deep tree, so adjacent lookups are separated by at least one mispredict: so adjacent lookup can overlap execution, but the overlapping is useless since everything beyond the next mispredict is useless as it is on the bad path.

That's probably at least true for the small map regime. For the larger maps, the next iteration is actually very useful, even if on a mispredicted path, because the date accesses are at the right location so it serves to bring in all the nodes for the next iteration. This matters a lot outside of L2. At 5 instructions per comparison and 32-element nodes, however, there are just so many instructions in the window for 1 lookup it's hard to make it to the next iteration.

So b-trees benefit a lot from a tight linear seach (e.g. 2 instructions per check, macro-fused to 1 op), or a branch-free linear search, or far better than those for big nodes, a vectorized branch-free search.

> If we define 'processed' as fully committed, then messages ca be processed exactly once. If it can be processed once, it can be delivered exactly once if you accept the simplest definition of that word.

I don't see how. Let's take a simple example of a the receiving end of a messaging system, where the messaging system can do whatever it wants to enforce idempotency or whatever semantics it wants, and calls, in-process, some `handler()` method of the application.

The useful processing happens somewhere in `handler()`. No matter what point you identify as the point where processing happens inside handler() it won't have delivered/processed-once semantics: it will potentially be called multiple times. The fact that the messaging system will internally have a commit step after handler() completes which is idempotent is irrelevant: as a user of the system you care how many times handler() is called.

In a sense it's just kicking the can down the road: how you ensure the consumer reads the message only once? It may fail at some point after it has read the message but updated some state to reflect that.

So it's not just a pointless argument about the semantics of the term "delivery": the fact that no communication channel can have exactly once delivery means that these systems are much more difficult to implement. For example, you can't just chain together 2 "exactly once" delivery systems into some longer one with a stateless middle node: instead you need some concept of idempotency that spans both systems or the middle node itself needs to de-duplicate (statefully) the first link and forward messages on to the second link.

That's exactly what it does by default.

Only if you pass --and-rebase does it actually do the autosquash rebase for you.