8 ms·
The Alder Lake SHLX Anomaly
- aftbit 2y agoWoah that's weird. Left shifting either takes 3 cycles or 1 cycle, depending on how you initialize the cycle count register? This patch from the article makes it take 1 cycle instead of 3: - MOV RCX, 1 + MOV ECX, 1 >It seems like SHLX performs differently depending on how the shift count register is initialized. If you use a 64-bit instruction with an immediate, performance is slow. This is also true for instructions like INC (which is similar to ADD with a 1 immediate). Practically speaking, is this sort of µop-dependent optimization implemented by compilers? How do they do so?
- tavianator 2y ago> Practically speaking, is this sort of µop-dependent optimization implemented by compilers? I suspect this specific thing is not; I don't think many people were aware of this anomaly until this week. I doubt the compilers are modeling it. But in general, compilers will have a machine model that predicts the cost of different instructions. The backend will try to generate instruction sequences with low cost, so if you include this anomaly in the model it will probably work around it automatically. This old example might interest you: a false dependency on the destination register for `popcnt` on some uarches led to compiler patches: https://stackoverflow.com/q/25078285/502399 https://stackoverflow.com/q/25078285/502399
- RossBencina 2y agouser mshockwave posted this the other day in a comment, might be of interest/tangential relevance: Scheduling Model in LLVM - Part I https://myhsu.xyz/llvm-sched-model-1 https://myhsu.xyz/llvm-sched-model-1
- loeg 2y agohttps://news.ycombinator.com/item?id=42555110 https://news.ycombinator.com/item?id=42555110
- tavianator 2y agoOne fun thing about this is that spilling+restoring the register will fix it, so if any kind of context switch happens (thread switch, page fault, interrupt, etc.), the register will get pushed to the stack and popped back from it, and the code suddenly gets 3x faster. Makes it a bit tricky to reproduce reliably, and led me down a few dead ends as I was writing this up.
- eigenform 2y agoI wonder if this is a thing where the machine is trying to predict the actual value of the 'count' operand ...
- tavianator 2y agoIf it were a prediction/speculation thing, I would expect it to settle down long before 10,000 `SHLX`s are retired.
- deleted 2y ago[deleted]
- dataflow 2y agoWow. Any chance you could share either an explanation or your benchmark code to show how you measured this reliably? I've never had to constrain benchmarks to within a time slice so I'm kind of fascinated how you got stable measurements out of that. Did you force a context switch prior to starting and then loop for a fixed number of times that wouldn't trigger another context switch? Or did you disable preemption on your thread, or something else?
- valleyer 2y agoYeah, even an interrupt (that doesn't result in a thread switch) would cause a spill to the stack, right? That seems hard to control.
- 2y ago
- userbinator 2y agoHow about trying "xor ecx, ecx; inc ecx"? Or the even shorter "mov cl, 1"? It is very strange to me that the instruction used to set the shift count register can make the SHLX instruction 3× slower. I suspect this is a width restriction in the bypass/forwarding network. The 32-bit vs. 64-bit operand size distinction is especially surprising to me as SHLX only looks at the bottom 6 bits of the shift count. Unfortunately the dependency analysis circuitry seems not Intel-ligent enough to make that distinction.
- tavianator 2y ago> How about trying "xor ecx, ecx; inc ecx"? Fast. But inc rcx is slow. > Or the even shorter "mov cl, 1"? Fast. > I suspect this is a width restriction in the bypass/forwarding network... I think we just found the explanation on Twitter: https://x.com/corsix/status/1874965887108976858 https://x.com/corsix/status/1874965887108976858 Alder Lake adds support for mov/add/sub with small immediates to the register renamer. So `add rcx, 1` gets handled by the renamer, potentially with zero latency. Unfortunately shifts are slow when the shift count is renamed in this way. This leads to fun things like `mov rcx, 1024` being fast while `mov rcx, 1023` is slow. I'll update the blog post in a bit.
- tptacek 2y agoI got nothing here other than: this is very cool.
- eigenform 2y agoOooh, I forgot about this. Only thing I can think of is something like: 1. Assume that some values can be treated internally as "physical register plus a small immediate" 2. Assume that, in some cases, a physical register is known to be zero and the value can be represented as "zero plus a small immediate" (without reference to a physical register?) 3. Since 'count' is always expected to be <64, you technically don't need to use a physical register for it (since the immediate bits can always just be carried around with the name). 4. The 3-cycle case occurs when the physical register read cannot be optimized away?? (Or maybe it's just that the whole shift operation can occur at rename in the fast case??)
- bhouston 2y agoShifts were not always fast. These old hacker news comments contain the details: https://news.ycombinator.com/item?id=2962770 https://news.ycombinator.com/item?id=2962770
- petermcneeley 2y agoIndeed. Dynamic shifting was microcoded (not uop!) on the power pc for gen3. However shifting with immediate values was not. This leads to all sorts of strange performance workarounds. Mike Acton refers to it here: https://macton.smugmug.com/Other/2008-07-15-by-Eye-Fi/n-xmKDH/i-BbZPR2r/A https://macton.smugmug.com/Other/2008-07-15-by-Eye-Fi/n-xmKD...
- BeeOnRope 2y agoWorth 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.
- tavianator 2y agoIt's possible to get gcc to generate sequences that would trigger this: https://godbolt.org/z/rYKqPxn7b https://godbolt.org/z/rYKqPxn7b
- loeg 2y agoThe godbolt paste I'm looking at shows GCC generating a SAL with 8 bit shift (CL), not a SHLX with 64-bit shift (RCX).
- tjalfi 2y agoGCC will generate the shlx instruction if you add the -mbmi2 flag to your build options. For example, you can see this in action here: https://godbolt.org/z/asb1fxos5 https://godbolt.org/z/asb1fxos5.
- BeeOnRope 2y agoIt'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.
- deleted 2y ago[deleted]
- tavianator 2y ago
- BeeOnRope 2y agoTo 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).
- tavianator 2y agoI did try aligning the loop, it didn't matter
- BeeOnRope 2y agoDoes this also occur with other 3-argument instructions like ANDN?
- tavianator 2y agoANDN is fast. The issue looks specific to shift counts. SHL is also slow.
- Bulat_Ziganshin 2y agowhat about 8-bit ANDN? SHL essentially uses CL, so it may be because 8-bit subregister of "constant register" isn't present on the bypass network
- crest 2y agoSo the issue is that the frontend which "eliminates" those operations doesn't make the resulting values available to the backend if fits Intel's ad-hoc definition of a short immediate (which shift values do) and since there is no SHLX with immediate uop the small value has to be be expanded to a full 32 or 64 bits and requested from the frontend with adds two cycles of latency? Has anyone run tests with ≥3 interleaved SHLX dependency chains in a loop? Does it "just" have 3 cycle latency or also less than 1 operation/cycle sustained throughput? Because if the pipeline stalls that would be even more annoying for existing optimised code. Is the regression limited to only Alder Lake P-cores or also present it later (refreshed) cores?
- deleted 2y ago[deleted]
- orlp 2y agoSeems like LLVM knows about this quirk (note how it suddenly uses eax instead of rax for the multiply): https://rust.godbolt.org/z/8jh7YPhz4 https://rust.godbolt.org/z/8jh7YPhz4.
- stassats 2y agoUsing EAX is one byte shorter, so it might be doing that inadvertently.
- rincebrain 2y agoSince this seems like an optimization going awry somewhere, I wonder if there's a chicken bit that disables it, and if so, how broad the impact of disabling it is...
- eqvinox 2y agoHmm… does this have any impact on time-constant cryptographic algorithm implementations? In particular the wider "addition in register renamer" story?
- dzaima 2y agoPerhaps not - as it happens at the rename stage and thus only with immediate values, it's all fixed behavior for a given instruction stream; with branching you can of course get dynamically different renamed immediates, but, as that's branchy code, it's not time-constant anyway.
- LegionMammal978 2y agoI don't think it should, if the performance change only depends on immediates hardcoded into the binary, and not the variable data being processed. Maybe if the algorithm branched on the variable data and had two separate ways of loading something, but branching on variable data is the #1 thing you're supposed to avoid in the first place.
- atq2119 2y agoTo expand on this a bit, the hypothesis stated elsewhere is that the register renamer stores "physical register + 11-bit signed immediate". It should be possible to construct scenarios where a logical register is mapped to "physical register + immediate" where the immediate depends on the path taken through the program so far. The easiest example would be an if-statement that optionally adds 1023 to a register, and then an add of 1 after the if-statement. The add of 1 overflows the immediate stored in the register renamer if and only if the if-condition was true. As you said, that requires taking different control flow paths through the program, which is something to be avoided by constant-time algorithms anyway. One potential twist: This shows that it may be important that the interface between the constant-time algorithm and the rest of the program goes entirely through memory and not through registers. If the interface does go through registers, it's possible that variable register-renamer-immediates leak from the outside world into the constant-time algorithm. (This admittedly feels like a bit of a stretch, but who knows.)
- juancn 2y agoCode alignment? I mean, the different instructions change the alignment of the rest of the code. - 64 bit register 0: 48 c7 c1 01 00 00 00 mov rcx,0x1 - 32 bit register 0: b9 01 00 00 00 mov ecx,0x1 It should be easy to test by adding a couple of NOPs to the fast version: 0: b9 01 00 00 00 mov ecx,0x1 5: 90 nop 6: 90 nop and see if it regresses again. I don't have an Alder Lake to test on.
- BeeOnRope 2y agohttps://news.ycombinator.com/item?id=42582623 https://news.ycombinator.com/item?id=42582623
- tavianator 2y agoIn general I'd be very surprised if code alignment had much effect on a 10,000 instruction block, especially since the instruction is 5 bytes long so it will quickly unalign itself
- tavianator 2y agoWrote up the presumed explanation here: https://tavianator.com/2025/shlxplained.html https://tavianator.com/2025/shlxplained.html