> 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.
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:
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.
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.
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"
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.
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.
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.
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."
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?)
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.
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.
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.)
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.
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).
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.
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].
> (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.
Also, https://www.sandpile.org/ - a differently organized instruction reference, plus assorted information on register and memory layouts and the like.
56 comments
[ 4.6 ms ] story [ 120 ms ] threadNote 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.
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.
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
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...
My point is that small code is useful - unrolling a twice nested loop can kill performance if you aren't careful.
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.
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) {
}// handwave a bunch of crap about edge cases
return a * b * c * d;
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.
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
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"
Rep movs is the obvious way to represent memmove and memcpy. Avx moves should have never been faster than that sequence.
For smaller sizes, rep stos can be as much as 20x slower than the alternative.
- 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
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 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.
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.
Zen 3(?) has some other requirements along these lines but I don't remember what exactly.
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.
Also very interesting: if you run sysctl under Rosetta, it reports 64 bytes:
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.
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).
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.
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.
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?)
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
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.)
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.
...and detecting 11 or 00 is easier than 01 or 10 in hardware, because it saves an inversion and thus a few transistors.
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.
2018 https://news.ycombinator.com/item?id=16896536
2013 https://news.ycombinator.com/item?id=5424649
[1] https://marc.info/?l=openbsd-tech&m=150869222214001&w=2
[2] https://www.openbsd.org/papers/asiabsdcon2019-rop-paper.pdf
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:
And even when the xchg's are actually needed (eg for mod/rm /0 and /1 opcode groups), they should be encoded properly: 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.See also:
- Standard x86 calling conventions -- http://unixwiz.net/techtips/win32-callconv-asm.html
- A x86 instruction reference -- http://ref.x86asm.net/
EDIT: formatting
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.