[exmadscientist]

A huge part of the problem here is that you're playing with the 8-bit registers. They work, but they're like travelling the back roads: the CPU designers put all their effort into the big highway next door, and not so much into keeping the back roads clear. They're infamous for random weird stalls and such. I wouldn't be surprised at all if there's dependency chain tracking weirdness using them.

If you can change the type on `next_j` over to `unsigned` (or `size_t` or ...) then a lot of weird stuff goes away. The dependency chains in address calculation at the beginning of the loop are gone too, which seems a win. (Or I'm sure there's some other, more complicated, way to get the compiler to get rid of them.) But if the space hit from using `unsigned` is allowable, I'd expect it to be both faster and less brittle.

The processor doesn't really know what you're up to, it only sees registers. When `j` is stored in `ecx`/`rcx` and `ecx` isn't changing, it knows it's free to push ahead pretty far on speculation. If the update to `ecx` is rare, putting it behind a well-predicted-not-taken branch will make it go away, as far as the speculation engine is concerned, and let the processor go far and fast. (The rollback on mispredict can be pretty painful, but, well, that's out-of-order execution for you.) That's what we're really trying to accomplish here: stuff that single register write behind a rare branch, somehow.

Here's what that can look like: https://clang.godbolt.org/z/1ss6hsEKb

Note that I disabled unrolling because some approaches got unrolled more than others. (I saw no unrolling, 2x, and more!) Comparing them without unrolling is fairest, I think, though it's also interesting to see how far they can unroll without assistance.

I also found that clang didn't need any additional fencing (or care if it was present), but gcc did, so there's an `asm volatile` style fence, which I think is a lot more clear than the other tricks. (Your mileage may vary; people who've done a lot of low-level work won't blink at these, while others will just stare agape. Perhaps also not blinking, but for opposite reasons!)

(Mind you, I didn't actually run any of this, so, well, you get what you pay for.)

[purplesyringa]

> A huge part of the problem here is that you're playing with the 8-bit registers. [...]

That's an interesting thought, though in this particular case I think it's a little misguided. 8-bit arithmetic (or, god forbid, 16-bit arithmetic) can quickly cause unexpected stalls, but there is no arithmetic here: the only inherent difference between 8-bit and 32-bit code is the use of `movzx` versus `mov` in a memory load, which to the best of my knowledge are equivalent in performance (modulo store-to-load forwarding and such).

It does look like LLVM generates ugly code for address calculation, though. I don't think it's necessarily going to cause a large effect, since `movzx r8d, cl; lea rdx, [rdi + r8]` doesn't depend on the previous iteration, and the critical latency chain here is just `inc rax`, but it might affect throughput a little. It's quite unfortunate that the induction heuristics didn't do their best here.

> so there's an `asm volatile` style fence

I've seen a couple people suggest the compiler fence, and all of them did the same thing -- they put `asm volatile` after the assignment to `j`, not before. Could you explain your thought process here? I thought putting it before the second load would make more sense, because I can imagine

    if (j != next_j[i][j]) {
        j = next_j[i][j];
        asm volatile("" : "+r"(j)); 
    }

being (de)optimized to

    unsigned char value = next_j[i][j];
    _Bool flag = j != value;
    j = value;
    if (flag) {
        asm volatile("" : "+r"(j)); 
    }

which in turn could be compiled to `mov reg, [mem]; cmp reg, reg; mov reg, reg; je`, whereas

    if (j != next_j[i][j]) {
        asm volatile("" : "+r"(j)); 
        j = next_j[i][j];
    }

doesn't permit such an optimization because it forces a conditional load, which you can't avoid putting behind a branch.

I have no doubt that putting the fence after the assignment works in this scenario (clearly it does, since LLVM and GCC recognize it), but I don't intuitively see why.

[exmadscientist]

> in this particular case I think it's a little misguided ... only inherent difference between 8-bit and 32-bit code is the use of `movzx` versus `mov` ... generates ugly code for address calculation ... the induction heuristics didn't do their best here

OK, it seems I've been a bit confused myself. I think my final conclusion is actually just that clang is generating kind of crap code here, and this change gets good codegen out of clang. Since I was mostly looking at clang and was leaving gcc as an afterthought, I didn't pick up on this. (Obviously I'm a little rusty on my x86, I shouldn't have fallen for that!) As gcc shows, it doesn't matter much either way. But when clang is happy, its code is quite nice, so there's that.

That little address dependency chain is nastier than it looks, though, the way clang is writing it. Best done away with. There's really no reason for clang to be emitting that crud. gcc handles the addressing in a much cleaner manner whether it's byte- or dword-wide. But gcc also does need that fence when clang does not. I'm sure that's not a coincidence.

> Could you explain your thought process [on placing the compiler fence]?

I ended up dumping this in kind of carelessly and noting that it worked before moving on (it was a last-minute add and I was kind of done by this point). But GCC does care where it goes, since it doesn't work if placed before. Let's try this explanation: the fence basically means "resolve all funny business with this variable before proceeding". Before the write, there's no funny business to resolve: nothing has happened to that variable. No writes, no outstanding reads (we're well into the loop at this point, in theory). So it's a fancy nop. But if it's after the write, we've now got a consequence: `next_j[i][j]` is different now. The fence forces us to resolve that now and not let it linger until the next loop iteration. Where it can be handled perfectly well, but not particularly quickly (which we do care about), and by the way that choice puts the update in the fast path. Forcing it to be dealt with before we re-enter the fast path is how we force the stupid compiler to keep it out of the fast path.

> ugly code for address calculation... might affect throughput a little

What I'd actually worry most about is poisoning the prefetchers, and speculation more generally. They're very very good at handling things like "increasing stride off this base". They struggle more with things like "double indirect register access to determine next address", though there is so much compiler crud out there that they have some surprising capabilities. Basically: simple stupid loop stride is going to do well with them. Complicated four-instruction chains to generate an address that could have been `[base + 8*stride]` or whatever is just... not helping. gcc does perfectly well here. It has multiple offsets floating around, but all of those instructions to update them can update superscalar, in a single cycle. The clang chain is a four-cycle delay. And to top it all off the branch can probably fuse in the simple addressing case!

[purplesyringa]

> the fence basically means "resolve all funny business with this variable before proceeding"

Thanks, that's a good explanation! I understand it better now.

> What I'd actually worry most about is poisoning the prefetchers, and speculation more generally.

I didn't know prefetchers rely on address generation instructions, I thought they only tracked accessed memory. Good to know! Do you know any relevant external resources about this, by any chance?

[exmadscientist]

I don't have anything covering recent generations. Try the usual suspects, I guess (Agner Fog et al). Sorry that's not more useful, but I haven't seriously worked on x86 in over a decade, so I'm a bit out of date.

Certainly, back then the prefetchers were a lot happier when they could easily identify patterns. They are more sophisticated now, but the old tricks still work. Avoiding register-based indirection is a major help to pretty much everything. When the base register gets updated, as well as the index register, that's hard to optimize. It shows up in both memory prefetch as well as speculation past an instruction.

The other idea to keep in your head is to start thinking in SSA form. Compilers live and breath SSA, so if your fast-path code looks like SSA with a couple of phi nodes, well, it's probably going to generate like you think it will. That's why I preferred the explicit `update_j` style: it's SSA form!