The Art of Picking Intel Registers (2003) | Hacker News Reader

The Art of Picking Intel Registers (2003)

swansontec.com

78 pointsTomte55 comments

> Using registers according to Intel's original plan allows the code to take full advantage of these optimizations. Unfortunately, this seems to be a lost art. Few coders are aware of Intel's overall design, and most compilers are too the simplistic or focused on execution speed to use the registers properly.

Note carefully that the context here is size optimisation only. When they talk about 'optimised' they just mean smaller code.

The advice is pre-historic and counter-productive for all other purposes. Compilers don't generate as is being advocated here, not because they're ignorant of this 'lost art', but because in modern implementations of the architecture there's no point! In fact I think some of the old instructions recommended here like 'loop' are almost always slower than simpler modern equivalents using any registers and multiple instructions.

I'd go so far as to say extreme size optimization, as indeed the author is doing... Demoscene tricks and shellcode are about the only places that matters now, i think. Stunts.

Makes it no less cool. I needed some of these tricks once, and have had many years of joy since in not needing them again.

Generating small code can be desirable - the uOP$ is a lot smaller than the I$

For example, compilers aren't very good at spotting overflows, so you can end up with a 150 instruction SIMD monster for the factorial function when pentium pro code could've been faster for the ints that matter.

All this x86 weirdness is partly why the schedulers compilers actually use are quite detached from the textbooks - GCC builds a FSM to model the decoder for example, as that's where a lot of the bottleneck will be for a CISC ISA like X86

uOPs are proprietary and undocumented: potentially changing between architectures even from the same company. So it's hard to generalize.

But it's my understanding that uOPs are constant sized. Having a variable length uOP seems counterproductive. If something is so complex that it won't fit in one uOP, then it's probably preferable to encode it as two separate uOPs.

We can get an idea of what is multiple uOPs by looking at the pipelines and latency charts. But even then: multiplication is likely one uOP despite taking multiple clock ticks of latency. So it's not exactly a precise science...

We know - and your compiler knows - exactly how many uOps are generated and which ports they execute on them - just not what they really do. Intel's performance counters can be fairly elucidating as to what your computer is doing - but - finding one you actually want can often mean scrolling through a list of thousands.

My point is that small code is useful - unrolling a twice nested loop can kill performance if you aren't careful.

The number of uops for each instruction is well documented.

IIRC uops can take more than one solt in the uop cache if they need to encode large constants, so they are technically variable length.

Could you explain how one would get a SIMD monster for a factorial function?

https://godbolt.org/z/61xGW7

Basically, the compiler isn't smart enough to realize that the loop in the factorial function couldn't possibly execute more than a few iterations before returning. Basically, it tries to do this:

int a = 1;

int b = 2;

int c = 3;

int d = 4;

for (int i = 5; i < x; i += 4) {

    a *= i;

    b *= i + 1;

    c *= i + 2;

    d *= i + 3;

}

// handwave a bunch of crap about edge cases

return a * b * c * d;

nwallin has provided an example.

I think I've lost the results now, but when benchmarked it's basically neck and neck between size and speed but similar speed for less code is almost always a good thing in this case.

> Note carefully that the context here is size optimisation only.

Indeed, and even if other benefits were once possible in the early x86 era, modern CPUs use register renaming[0] which presumably would make such benefits redundant.

[0]: https://en.wikipedia.org/wiki/Register_renaming

This knowledge is not obsolete. REP STOS/MOVS is the right way to move memory now, and its operands are SI, DI, and CX. It is still useful to know what the registers are supposed to mean.

From my understanding, looping avx512 or avx2 mov might be faster than rep stos in many cases.

The number of such cases is decreasing, though. Recent (ICL and "later" whatever that means) Intel cores have fast-short-rep-movsb which reduces the startup time of the REP. Considering the icache pressure of a hyperoptimized memcpy, it is probably the right way to go for new code.

If you're interested see Google's paper, AsmDB: Understanding and Mitigating Front-End Stalls, section 4.4 Memcmp and the perils of micro-optimization, in which they say that REP CMPS beats glibc memcmp in full-scale benchmarks. "On large-footprint workloads like websearch, it reduced cycles in memcmp more than twofold and showed an overall 0.5%-1% end-toend performance improvement." And that was on Haswell, before people started selling parts with "fast short cmpsb"

Good to hear.

Rep movs is the obvious way to represent memmove and memcpy. Avx moves should have never been faster than that sequence.

Don't Intel now recommend 'implementing memcpy using Enhanced REP MOVSB and STOSB might not reach the same level of throughput as using 256-bit or 128-bit AVX alternatives'?

For implementing an optimized memcpy, I believe that is still true (although the gap between rep movsb and a nontemporal copy using vector registers is not all that large). But for many cases the code size improvement (a couple of bytes versus hundreds for a typical vectorized implementation) or restrictions on register use (kernel) mean that it can be a good choice.

ERMS is extremely slow for small sizes. In my testing, rep stos wins over sse for sizes above ~1k, and over avx for sizes greater than l1. It also requires correct alignment, and isn't fast on most AMD cpus.

For smaller sizes, rep stos can be as much as 20x slower than the alternative.

You can’t make a statement like that without mentioning which part you’re testing with.

Not sure what you mean by 'part'. I reproduced this across the following CPUs, which I think are fairly representative:

- intel xeon e3-1246

- intel core i3-5005u

- amd ryzen 3960X

- amd epyc 7402p

Comparing my own[0] memset implementation, glibc's, and bionic's.

0. https://github.com/moon-chilled/fancy-memset

It seems that you do know what I mean by part. Only the latest Zen3 parts have ERMS and FSRM.

I think that benchmarking memset by itself is folly, because you may end up with a very large function that is fast on its own, but which trashes your icache when run in a real application. That is the conclusion of the paper I linked elsewhere in this thread: that rep cmpsb, even on old CPUs where it is slow, beats glibc memcmp in real full-scale applications because glibc memcmp is 6KB long and has a tendency to evict dozens of lines of icache. memset, memcpy, and memmove have the same hazard.

That is a good point, and I do intend to do full-scale application benchmarks; I just haven't gotten around to it yet.

That being said, all the implementations of memset I tested except for glibc's are in the neighborhood of 100-300 bytes (also including the freebsd version, which doesn't use any simd), which is a fair sight smaller than 6k.

All things being equal, smaller code is better[1]. Of course, if things are not equal, and loop is slower than building it yourself, then build it yourself except where you're size constrained.

Also, you really have to benchmark these things to know for sure, and it can change between processor generations and the author couldn't have tested Zen 3 in 2003; and we'll have a hard time testing Pentium M in 2021.

[1] Memory bandwidth is limited, cache sizes are limited, even though both are huge. Otoh, the quantum of useful savings is a cache line, 64 bytes on modern amd64 if I'm reading correctly. If you save some bytes, but not a cache line, it probably doesn't help anything. If you only save one cacheline, the difference will likely be hard to measure, but could be measurable depending on circumstances.

When Intel themselves don't recommend using the instruction in their optimisation manual... I think you can take that as a good indicator that it isn't going to be fast even before you start benchmarking.

Cachelines are 64 bytes on most architectures these days.

Zen 3(?) has some other requirements along these lines but I don't remember what exactly.

Interestingly, the M1 (and probably other Apple Silicon CPUs) is an exception:

  % sysctl hw.cachelinesize
  hw.cachelinesize: 128

That's an ARM thing afaik, the snapdragons I work with also use 128 byte cacheline.

A quick search suggests ARM's own designs tend to use 64-byte cache lines, but perhaps this is something the SoC vendors can customize? AFAIK, Qualcomm's recent parts use ARM-designed cores.

Actually you're right, recent designs use 64 byte because of things like this

https://www.mono-project.com/news/2016/09/12/arm64-icache/

Perhaps, either Apple is fooling the userspace software or is using 128b cachelines for their little cores too.

It looks like sysctl shows the cache info for the little cores, at least by default:

  hw.cachelinesize: 128
  hw.l1icachesize: 131072
  hw.l1dcachesize: 65536

The reported L1I and L1D matches up with the little cores.

Also very interesting: if you run sysctl under Rosetta, it reports 64 bytes:

  % arch -x86_64 /bin/bash -c "sysctl hw.cachelinesize"
  hw.cachelinesize: 64

This information is exposed specifically so that app developers can optimize for the cache line size in use. I very much doubt Apple would report a false number.

As for Samsung: my guess is that Apple has been using 128-byte cache lines for a long time, and Samsung simply copied that because Apple did it, without understanding the implications. That would be totally in line with what I expect from them.

> This information is exposed specifically so that app developers can optimize for the cache line size in use. I very much doubt Apple would report a false number.

No, this number is used for compatibility reasons. OS is free to pull shenanigan behind apps to take care of CPU cache line size changing underneath them (like using a larger size so it'll align on everything; 128b aligned is 64b aligned too).

Hyperoptimizing for code size can be counterproductive. If you pack several branches or branch targets into the same cache line, the CPU might lose its ability to predict them. Making your code bigger (inserting NOP to align branch targets, for example) will often be worth the tradeoff in pure size.

I don't think this is true, though – it'd strike me as utterly bizarre if an architect decided to use the same index bits for the branch target buffer as the cache. For the cache, the low bits of the address are the offset, the next bits are the index, and the remaining bits are the tag. Branch target buffers have no offset, but instead (as I understand it) use those low bits for an index (perhaps more or fewer; it needn't be the same number as the cache) and the remaining bits as a tag.

I'm sure there are additional, more advanced techniques, but I also have a hard time believing they wouldn't use the lower bits of the address.

Well, maybe not an L1i cache line, but there are a LOT of caches in one of these CPUs and the optimization manual describes a plethora of conditions under which the caches will stop working. One of these conditions is if you've managed to pack four branches into 16 bytes of code. Another is if 32 bytes of code decodes to uops that don't fit in the DSB. Intel also warns "If there are many taken branches from one 32-byte chunk into another, it impacts the micro-ops being delivered per cycle."

Oh, that's interesting. Looks like I have some reading to do! Thanks for replying.

Yeah, this seems mainly aimed at demo programmers, where the absolute smallest code size is the concern rather than the best performance.

Well... it's complicated.

First, "size only" optimization isn't really a thing. The instruction cache is a finite resource, so using less of it allows more code to fit, which increases performance (this is less true in the post-SNB world where the first level of instruction caching is the uOp cache and not an image of memory).

Also, there do remain special purpose registers which are involved in compiler-generated code. Multiplication still clobbers RAX and RDX for example, so if you have hand-generated assembly that wants to touch those it will force nearby compiler-generated multiplies to issue extra instructions to arrange things. Likewise RSI/RDI are still the preferred loop counters for memcpy on most toolchains, so if you're mucking with them needlessly (e.g. where Rnn registers would do) you're making more work for the compiler.

It's true that lots of hardware work over time has acted to normalize the instruction set, so none of these optimizations are particularly large. But the details are still real and worth knowing.

Amplifying your point, μops are grouped into Ways and Ways are 6 μops on Intel and 8 μops on AMD. Ways have constraints; violating a constraint will necessitate a spill.

  stage bypass
  macro + micro fusion
  μops
  μop Way
  functional unit
  Loop Stream Detector
  16B decoder fetch line
  64B instruction cache line
  instruction cache
  page
  DRAM

Picking the right register might occasionally help with a decoder fetch line here and there, and progressively less often with the following instruction packing scenarios. But the first 6 are more important for performance although Intel spends a lot of transistors and dollars to make that less of an issue. They also have nothing (IIRC) with register names.

I’ve never seen this detailed high level breakdown before so super helpful, thanks!

What’s the difference between page and DRAM? In fact, I probably can only guess at most of these so if you could provide definitions that would be good (or are there Wikipedia pages on all these?)

Extra pages use more TLB resources is I think the message GP is trying to convey here.

Is this documented somewhere? Where do I look if I want more information about uops?

There is a new book out, Performance Analysis and Tuning on Modern CPUs, Denis Bakhvalov [1]. Let's be honest; he works for Intel and that should have been Intel CPUs. He's a good writer.

Of course, there's Agner Fog's Microarchitecture and the Intel® 64 and IA-32 Architectures Optimization Reference Manual.

There are about 11 people who really understand this stuff and they all know each other, and we all read them. Travis Downs and Geoff Langdale (Hyperscan) come to mind.

[1] easyperf.net

Another interesting point is ROP gadgets, which OpenBSD tries to reduce by preferring to avoid EBX/RBX registers [1]. This and more on the subject can be found in this paper [2].

[1] https://marc.info/?l=openbsd-tech&m=150869222214001&w=2

[2] https://www.openbsd.org/papers/asiabsdcon2019-rop-paper.pdf

(Of course, it is dubious as to whether this actually helps much.)

> (Of course, it is dubious as to whether this actually helps much.)

Unsurprising, since the paper seems to be written by someone with no actual knowledge of x86 in the first place. Eg, in Alternate Code Generation, they recommend rewriting:

  48 89 C3  mov rbx, rax
  # as
  48 87 D8  xchg rax, rbx
  48 89 D8  mov rax, rbx
  48 87 D8  xchg rax, rbx
  # when they should simply be writing
  48 8B D8  mov rbx, rax  $ note that this is *literally the same instruction* at the assembly level

And even when the xchg's are actually needed (eg for mod/rm /0 and /1 opcode groups), they should be encoded properly:

  48 C1 C3 04  rol rbx, 4
  # to
  48 93        xchg rax, rbx  # we have dedicated instructions for this for a reason
  48 C1 C0 04  rol rax, byte 42
  48 93        xchg rax, rbx  # I think we *do* need the 48 on these, unfortunately; blame AMD

The former (that is, the policy of assembling register-to-register mod/rm instructions between a ax/cx and a bx/dx with the former in the effective address (not "destination") slot) eliminates upwards of three quarters of mod/rm-ret gadgets (including in hand-coded inline assembly!) at zero cost, and should have been the first option, before even thinking about register allocation.

Ahh this was a great great article back in the day. Lots of fun on smashthestack.