The Art of Picking Intel Registers (2003)(swansontec.com)

78 pointsby Tomte5 tahun yang lalu55 comments

The Art of Picking Intel Registers (2003)

http://www.swansontec.com/sregisters.html

56 comments

chrisseaton5 tahun yang lalu

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

ajross5 tahun yang lalu

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.

CalChris5 tahun yang lalu

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.

vlovich1235 tahun yang lalu

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?)

jcranmer5 tahun yang lalu

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

fctorial5 tahun yang lalu

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

CalChris5 tahun yang lalu

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

toast05 tahun yang lalu

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.

chrisseaton5 tahun yang lalu

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.

jeffbee5 tahun yang lalu

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.

agalunar5 tahun yang lalu

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.

jeffbee5 tahun yang lalu

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

agalunar5 tahun yang lalu

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

mhh__5 tahun yang lalu

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.

384912398213985 tahun yang lalu

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

  % sysctl hw.cachelinesize
  hw.cachelinesize: 128

zeusk5 tahun yang lalu

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

384912398213985 tahun yang lalu

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.

zeusk5 tahun yang lalu

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.

384912398213985 tahun yang lalu

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.

zeusk5 tahun yang lalu

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

jeffbee5 tahun yang lalu

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.

moonchild5 tahun yang lalu

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.

jeffbee5 tahun yang lalu

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

moonchild5 tahun yang lalu

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

jeffbee5 tahun yang lalu

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.

moonchild5 tahun yang lalu

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.

chrisseaton5 tahun yang lalu

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'?

saagarjha5 tahun yang lalu

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.

dragontamer5 tahun yang lalu

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

jeffbee5 tahun yang lalu

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"

dragontamer5 tahun yang lalu

Good to hear.

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

[deleted]5 tahun yang lalu

zowanet5 tahun yang lalu

> 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

mhh__5 tahun yang lalu

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

dragontamer5 tahun yang lalu

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

mhh__5 tahun yang lalu

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.

gpderetta5 tahun yang lalu

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.

tom_mellior5 tahun yang lalu

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

nwallin5 tahun yang lalu

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;

mhh__5 tahun yang lalu

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.

saagarjha5 tahun yang lalu

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

h2odragon5 tahun yang lalu

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.

gbrown_5 tahun yang lalu

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

saagarjha5 tahun yang lalu

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

a13692099935 tahun yang lalu

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

rmhsilva5 tahun yang lalu

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

See also:

- Standard x86 calling conventions -- http://unixwiz.net/techtips/win32-callconv-asm.html

- A x86 instruction reference -- http://ref.x86asm.net/

EDIT: formatting

a13692099935 tahun yang lalu

Also, https://www.sandpile.org/ - a differently organized instruction reference, plus assorted information on register and memory layouts and the like.

dang5 tahun yang lalu

dragontamer5 tahun yang lalu

Register renaming on modern x86 (skylake or zen) doesn't even use an execution unit. It may not even use a spot in the uOP cache IIRC. That means 'mov eax, ebx' uses minimal resources.

It still matters for taking up L1 space, but today's processors probably don't care about this list art anymore outside of code size.

Years ago, when mov actually created a write hazard and caused bubbles in your pipeline, this stuff was important. But not nearly as important anymore.

This post is still useful as a historical note, and as a reminder for how low level details can dramatically change over the decades, even within the same x86 instruction set.

fctorial5 tahun yang lalu

The author claims that using these patterns will result in faster code. Has anyone done the actual benchmarks and tested this claim?

chrisseaton5 tahun yang lalu

> The author claims that using these patterns will result in faster code.

No that's the opposite of what the author claims. They claim size, compressibility, and readability.

> The goal is to put as much high-quality music, graphics, and animation as possible into only 4096 bytes.

blueflow5 tahun yang lalu

The opcode encoding goes AX CX DX BX, not AX BX CX DX. This is a bit like the XKCD comic about bad kerning - you need to point it out and then people cant be unbothered by it.

kiwidrew5 tahun yang lalu

That's because Intel made the 8086 kind-of-sort-of backwards compatible with the 8080; it had six 8-bit registers (A Flags B C D E) plus a 16-bit register pair (H L), in that order.

AL corresponds to the 8080's A register and AH to the flags (which is also why the LAHF and SAHF instructions exist). CX corresponds to B+C and DX corresponds to D+E. Finally, BX is the 8086 equivalent of the 8080's pointer register HL.

(The 8086 didn't use the same opcodes as the 8080 but it was designed this way so that a simple translator could 'convert' existing 8080 code.)

blueflow5 tahun yang lalu

Why would the 8086 encoding be inspired from the 8080 when these two are generally not meant to be compatible in terms of their encoding? There is no gain from any of that.

This is like a urban legend that i have never found the source for. I stopped believing it after learning that the 8080 encoding order is BCDEHLMA, with the accumulator being last at position 7.

userbinator5 tahun yang lalu

BX is special because in 16-bit mode it's the only one of the ABCD registers that can be used in addressing modes.

...and detecting 11 or 00 is easier than 01 or 10 in hardware, because it saves an inversion and thus a few transistors.

blueflow5 tahun yang lalu

This doesnt make sense - the 16-bit modr/m byte (required for indirect register access) doesn't use the 'regular' opcode numberings, and the 32-bit modr/m byte can use any GPR, so BX is not special anymore (as mentioned in the article).