Hacker News Reader

Comment by ajenner | Hacker News Reader

It doesn't, because there are lots of special-purpose x86 instructions that would be more trouble than they're worth to teach a compiler about. For example, instructions for accessing particular CPU features that the C and C++ languages have no concept of (cryptographic acceleration and instructions used for OS kernel code spring to mind). Some of these the compiler might know about via intrinsic functions, but won't generate for pure C/C++ code.

Regarding the large number of LEA instructions in x86 code - this is actually a very useful instruction for doing several mathematical operations very compactly. You can multiply the value in a register by 1, 2, 4 or 8, add the value in another register (which can be the same one, yielding multiplication by 3, 5 or 9), add a constant value and place the result in a third register.

View on HN

lea's addressing mode arithmetic also doesn't wipe out any flags so it can be extremely useful for throwing in between arithmetic operations whose resulting flags you care about and the compare operation itself so as to obtain a greater degree of instruction level parallelism.

There are also AFIAK a few "deprecated" instructions that are implemented for backward compatibility but do not perform well on modern cores or have much better modern alternatives. These would be things like old MMX instructions, cruft left over from the 16-bit DOS days, etc.

X86 is crufty. Of course all old architectures are crufty, and using microcode it's probably possible to keep the cruft from taking up much silicon.

There are also instructions not universally available. A typical compiler will not emit these unless told to do so or unless they are coded in intrinsics or inline ASM.

And the counterpoint is that some instructions that are commonly believed to be slow (eg. the string instructions like rep movs, lods, stos), are in fact fast on modern processors.

Now I'm curious - do you have performance numbers somewhere for this? The rep instructions can actually be shorter than a call to str*, so if rep is actually fast enough then it might make a nice optimization.

It depends if the strings are aligned or not, the size of the copy, and also on the generation of processor. There are some good answers here:

http://stackoverflow.com/a/9177369

https://stackoverflow.com/questions/12359228/reliable-inform...

https://stackoverflow.com/questions/8425022/performance-of-x...

Reasonably modern versions of GCC will emit various rep instructions in some cases.

Some code I just compiled with GCC 6.1.1 had several snippets like this emitted for zeroing with memset:

    xor eax,eax
    ...
    rep stos QWORD PTR es:[rdi],rax

and some rep movs for memcpy/memmove.

really? I wonder if the timing of rep and string instructions have improved at all?

They operate on cacheline-sized pieces ever since the P6.

Since P6, Intel's CPUs have used a RISC like core with a very heavy decoder that translates x86 CISC instructions to run on the internal ISA. With that in mind, do older or lesser used instructions actually perform poorly or are they just the wrong choice but actually preferred for other scenarios?

According to [1], on recent Intel CPUs, each instruction is translated by hardware decoder to up to four micro-ops: either trivial micro-ops like addition, subtraction, bitwise and/or/xor, or a special "microcode assist" micro-op which is essentially a function call into the CPU microcode table. According to the same source, CPU microcode table is believed to consist roughly of 20,000 micro-ops which handle edge cases like rare instructions, rare prefixes, FPU denormals, traps/exceptions, all that stuff. Also, CPU microcode table is believed to contain full-blown implementations of RSA and SHA-256 in order to support microcode updates.

So, yes, there's a performance gap between instructions with hardware fast path and ones which require a microcode assist.

[1] https://eprint.iacr.org/2016/086.pdf

The new slides for AMD Zen say explicitly that it has hardware sha256 support.

Careful. Do they mean an ISA extension to support fast SHA-256 implementations in your code, or do they have a SHA-256 implementation in their microcode for CPU-internal use?

I don't know and that goes beyond my point. The original poster said that it is rumored that Intel has a full implementation of sha256 in microcode. I am saying that AMD has confirmed that they at least have it in microcode.

> Since P6, Intel's CPUs have used a RISC like core with a very heavy decoder that translates x86 CISC

This get repeated often, but it is actually wrong. First of all RISC is a property of the ISA, not the microarchitecture: CISCs have been breaking complex instructions in micro instructions well before the RISC/CISC separation were even conceived.

In fact modern CISCs try to not to break instructions until they reach the execution units so that less resources need to be spent tracking them (uop fusion). Some even try to fuse multiple instructions (macro op fusion, many RISCs do it as well).

Old instructions may have a smaller encoding, which means it can be hard to tell whether you should use them if they are otherwise slow. The compactness of the x86 instruction encoding is one of the architecture's chief strengths (and weaknesses).

Yes, for instance the LOOP instruction: http://stackoverflow.com/questions/35742570/why-is-the-loop-...

Some legacy instructions are too complex and infrequently used so they are microcoded and run much slower.

Nearly all x86_64 instructions are microcoded on modern Intel and AMD CPUs. That does not mean they're slow.

Some instructions may end up slow when the microcode isn't updated to take advantage of the latest processor iteration (I recall this happened to rep movs at some point, which gave it its bad reputation, even though it was fixed). That probably happens often for legacy instructions.

No, the large majority of instructions are not microcoded. In addition to microcode having a performance penality by itself, a modern intel cpu machine can decode only one microcoded instruction per cycle, while it normally can decode up to 4 non-microcoded instructions per cycle. Note that microcoding and uop splitting are different things.

Do you have any reference for most of the stuff you are talking about in the comments here? I'd like to understand it better. Thanks.

Micro-ops are smaller units of work to execute a CPU instruction. Some instruction may take 1 uop like adding two registers together. Some may take multiple uops like adding a register and a memory location. For example split into one uop to read from memory into a temporary register and then another uop to add that temporary register with another.

There are instruction decoders that quickly breaks up an CPU instruction into a series of uops. It needs to be fast or the execution units may become idle. So there are limitations like breaking up into 4 uops max. On the Intel x86 processors, there were lots of quite complex instructions that might need to be broken down into more than 4 uops so a separate microcode modules can handle those. However there is only one of those so it can become a performance bottleneck if you use too many of those complex instructions.

If you really want a technical book on this, read "Modern Processor Design" by Shen. A bit pricey though (I got one second hand cheap.)

The bible are Agner Fog optimization manuals [1] which contain quite a detailed description of the microarchitecture of intel and AMD CPUs from the pentium era till today. They are based on the extensive reverse engineering done by the author.

David Kanter microarchitecture articles at RWT [2] are also quite good.

Intel manuals are quite detailed as well.

[1] http://www.agner.org/optimize/

[2] http://www.realworldtech.com/cpu/

Good examples of (essentially-deprecated) instructions include the rep prefixed instructions for string operations (modern library code for string operations typically involve a mixture of SSE, full-word loads and unrolled loops for speed); the "loop" instruction (compilers usually generate explicit loops for flexibility); pretty much all the BCD arithmetic instructions (since programming languages don't typically use BCD anymore), and many other such examples. The x86 architecture is chock-full of rarely-used legacy instructions that are mostly carried around for compatibility these days.

> the rep prefixed instructions for string operations

... are actually preferred over a hand-written vectorized loop on Ivy Bridge and up (see [1] section 3.7.7, "Enhanced REP MOVSB and STOSB operation (ERMSB)"). It's indicated by a CPUID feature flag bit (edit: grep for "erms" in /proc/cpuinfo to see this).

The reason is that microcode knows more about the dcache microachitecture, load/store units, special features (weak ordering with fence at end? [2]), etc., than you do, and can be specially optimized for the particular design. There's a slight cost to transitioning to microcode and back (to ordinary hardware-decoded instructions), of course, so for small operations it might not be a win.

The section cited above shows ERMSB as ~break-even vs. 128 bit AVX on Ivy Bridge from 128 bytes up to 2KB, and about 2% faster above that.

[1] Intel 64 and IA-32 Architectures Optimization Reference Manual (order #248966-026), April 2012. http://www.intel.com/content/dam/doc/manual/64-ia-32-archite...

[2] http://stackoverflow.com/questions/33480999/how-can-the-rep-...

And by not having a group of hand-optimized special cases, the REP MOVSB and REP STOSB can be inlined saving instruction cache.

Do you have benchmarks, supporting "~break-even vs. 128 bit AVX on Ivy Bridge from 128 bytes up to 2KB" as I have not found it to be the case at least on Haskell (my benchmarking code is @ https://bitbucket.org/olegoandreev/scratch/src/dd7ab9008c59c...).

I was just quoting the cited PDF ("the section cited above shows..."), which the author(s) did on Ivy Bridge.

I haven't benchmarked it myself. It would be interesting to see how the most common cores today do on this...

The BCD instructions, despite originally conceived for BCD, actually have some other niche uses such as AAM/AAD for a small multiply/divide:

https://news.ycombinator.com/item?id=8477254

In that article I also further refute the common belief that they are significantly slower in this comment, by reasoning and then an actual benchmark: https://news.ycombinator.com/item?id=8477585

And this is where I think a gap between compilers and humans exist --- would a compiler recognise, for example, that if your code, for whatever reason, happened to have this pattern of operations in it...

http://x86.renejeschke.de/html/file_module_x86_id_3.html

...it should emit a single AAS instruction? Or perhaps a simpler example, would it know to emit an AAM for an 8-bit division or modulus with a constant divisor? Maybe it could --- see the other discussion here about LEA --- but the developers just didn't bother to. I wish they would though, because despite how slow these instructions may be (which might not be the case), they are still valuable for size optimisation (-Os), and after all, it is a gap.

lea is also used frequently to actually load addresses. When passing the address of a stack buffer, for example, the compiler will usually generate code like "lea eax, [ebp-0x80]; push eax". Or, when loading the address of a struct member, you might have "lea ecx, [eax+8]".

Yup, the original intention behind lea is the & operator. Compute the address but instead of accessing the memory immediately (like mov does) just keep it for later use. Just what & does.

Loading an address is just adding a fixed number to the value in a register. Your two examples are mathematically equivalent to "eax = ebp - 0x80" and "ecx = eax + 8."

Yes, but those would be two assembly instructions each. The basic idea of using lea over 'movl $ebp, $eax; addl 0x80,$eax'ist that we can shave off a cycle because lea can be executed in a single cycle.

However I wonder how much any of this still matters in a time where CPUs have developed to include all sorts of complex optimizations.

Modify the backend, or do a binary translation from one to the other and test. If `lea` is the predominate instruction, there might be microcode optimizations that favor `lea` over `movl`. My hunch is that is will be mostly the same barring overflowing the instruction cache. The microps should compile to the same instruction stream.

No, LEA issues as a single micro-op on modern Intel CPUs, but no x86 CPU will merge a sequence of shift and add into a single micro op.

How would one find this out? Sounds like it would be fun to figure out how to develop all possible reasonably compact instruction combinations to achieve the same basic block and then compare timings.

http://www.agner.org/optimize/

Document 4.

lea also doesn't modify the flags register. At one point this meant there was a wider choice of execution units it could be scheduled on than arithmetic instructions that required a full ALU.

About LEA: adding to the above correct information, it is also useful because it can be scheduled in parallel with other ALU instructions (through a different "port" in x86 parlance), or at least that's how it used to be (I haven't looked at most recent x86 architectures). Thus compilers can use LEA to perform some arithmetic operations and generate code that will effectively run faster.

On recent Intel CPUs, LEA is generally executed with the same resources as other arithmetic.

LEAs touching 16-bit registers issue multiple micro-ops and are slow (the machine no longer has native 16-bit register support and has to mask the results in a separate op).

LEAs with 1 or 2 address components are issued to port 1 or 5 and have a latency of 1, and LEAs with 3 components or a RIP-relative address are issued to port 1 exclusively, and have a latency of 3.

In contrast, register-register/immediate adds and subs go to any of ports 0,1,5 or 6 and have a latency of 1, and register, immediate shifts go to ports 0 or 6 and have a latency of 1.

Converting operations to LEAs really doesn't buy as much today as it used to, but a smart programmer or a compiler can occasionally grab a cycle here or there.

Could you provide some links or examples? I'd love to learn more about this.

For kernel/OS functions, there are lots of things that can only be done while in 'kernel-mode' with kernel privileges. These are things such as turning interrupts on and off, changing which page table is being used, changing the GDT/IDT, and other various things. C has no concept of these things, and they are very special purpose. The AES instructions are similar - C has no built-in AES functionality, and the compiler just can't figure-out in which situations it could use them. All of these instructions can be accesses through inline assembly, so you can still use them in C, the compiler just won't understand what you're doing besides "It takes in these inputs, does something, and then puts out these outputs".

As for `lea`, there's nothing particularly special about it. x86 allows you to do some 'funny' addressing within instructions that take memory addresses - where you can do several calculations on the address within the instruction itself, without having to use a temporary to hold the address. `lea` just lets you 'load' the result of that calculation back into a register, presumably to let you avoid making the CPU do the calculation a bunch of times in a row. But there's nothing about `lea` that requires you to actually use addresses, rather then just plain numbers you want to shift and add. It is used a lot because `lea` is a single instruction and will generally run faster then doing a shift and some additions over multiple instructions.

Just read the output of your compiler for simple functions. objdump -d, or, cc -S

objdump -S does the trick too, it even has the C code intermixed if the -g CFLAG was used.

https://gcc.godbolt.org/ may help too

is there any point in multiplying by 1 ?

It might be used to avoid a conditional.

Thank you for your answer but frankly I don't understand it. Could you please elaborate?

Generally multiplying with 1 can be used to just do (the equivalent in assembly of):

    a  = a * b;

instead of

    if (b != 1)
       a  = a * b;

Which is normally a win, as branching are expensive vs multiplication.

It doesn't because when would a compiler issue syscall? Maybe if you count instructions emitted by inline assembly

Compilers do have intrinsics. No inline assembly needed for something that trivial.

Reply on news.ycombinator.com