Hacker News Reader

Comment by _8j50 | Hacker News Reader

Something I heard a while back is that very roughly 90%+ of compiler generated code is made up of 19 instructions and the rest are rare enough that you on x86/64 you shouldn't memorize them, just keep the manual handy. I wonder if that included various variations of instructions. But I am very curious about OPs question now.

Moreover, can you influence GCC over what instructions it emits? On Gentoo for example, you can setup your make file so that the while system is compiled with your specific processor in mind.

View on HN

> Moreover, can you influence GCC over what instructions it emits? On Gentoo for example, you can setup your make file so that the while system is compiled with your specific processor in mind.

For what it's worth, this is largely unnecessary nowadays. Tuning for a specific processor used to allow the compiler to use instruction scheduling and enabled use of SSE instructions. However:

1) Modern x86 CPUs all use out-of-order execution, making instruction scheduling unnecessary. (Some older Atom CPUs are in-order, but their performance is pretty awful even with instruction scheduling.)

2) If you're building for x86_64, you can assume a certain baseline of instruction set support -- in particular, CMOV, SSE, and SSE2 instructions are always available on any 64-bit CPU. While these don't cover all instructions, it does cover the bulk of what the compiler is likely to want to generate in typical application code.

> For what it's worth, this is largely unnecessary nowadays.

Not true, compilers remain extremely conservative in their default codegen, we’re talking pre-nehalem (SSE2 at the top end).

I just checked on godbolt, by default u32::count_ones compiled with rustc 1.62 with -O generates 15 lines of assembly hand-counting the bits in the word.

Adding `-C target-cpu=x86-64-v2` reduces that to a single popcnt.

Even if you don’t care for SSE3+, there’s a handful of really useful instructions which are not part of the baseline x86 profile, especially for bit-twiddling and endianness manipulation: popcnt, lzcnt (v3), movbe (v3), BMI1 and BMI2 (v3)

My vote is that pext and pdep are the highlight from BMI2.

Just be aware that even though these instructions are supported on pre-zen3 AMD, they are pretty much emulated and not very fast.

Otherwise I agree that these are awesome, I know a fast Hilbert-curve implementation using those.

Yes, there’s the annoying tendency of extensions to be slow on the first generation of processors that support them, and then faster afterwards.

While that's true, the PDEP/PEXT numbers are a bit on the extreme side on AMD early generations. On Zen1 and Zen2 these instructions have latency and rthroughput of 18 and 19 clock cycles respectively. On Zen3 it's a perfectly sensible 3 cycle latency and 1 cycle rthroughput [1].

I'm not aware of an other extensions with such a slow implementation in first generations.

[1] https://www.agner.org/optimize/instruction_tables.pdf

It's unfortunate that PDEP and PEXT is part of BMI2. AMD probably wanted to push BMI2 for the other instructions and they had to include emulated PDEP and PEXT before they had a proper implementation for those.

This stuff seems actually quite difficult to me. For example on one silly programming contest problem[0] there's a cluster of users from about 6th place to about 21st place who are basically reading memory sequentially as fast as they can using some simple loop that does 2 or more 32-byte loads into vector registers and then does some trivial calculations that can be done concurrently with the next loads (this is maybe 20 instructions if you choose to do a lot of loads per iteration, way fewer than that if you do just 1 or 2). There is also a small group of users who are going significantly faster! The top solution seems to be reading RAM 20% faster than a loop whose instructions look fine to me.

[0]: https://highload.fun/tasks/5/leaderboard

Even with out of order scheduling there's still use from instruction scheduling - move those loads as far forward in the instruction stream as you can - a CPU can't execute instructions out of order if it hasn't decoded them yet

These days CPUs have instruction windows that are hundreds of instructions deep. That typically allows for way more load hoisting than a compiler can realistically do (and that's pretty much the reason why all in-order or VLIW designs have fallen out of favor for general purpose computation).

They can't do a load before actually reaching the load instruction, and they can't fill the instruction buffer all that fast, maybe 5 instructions per clock, depending on loads of factors. They don't know what instructions are on the critical path, so it is perfectly possible to pick wrong ones in this regard. Having a big instruction buffer does not necessarily mean that the CPU can always pick a perfect selection of instruction from it, that is already a very hard issue that only becomes harder when you give it over a hundred to pick from.

In short, the out of order instruction buffer can do some amazing stuff for code that would otherwise run much slower, that doesn't mean you can't gain or lose performance by reordering instructions. For non-trivial code the best composition is almost certainly different between CPUs.

OoO windows do not need to do a perfect job. They just need to do a better job than the compiler at exposing memory parallelism, and that's usually the case.

Instruction placement and scheduling is still important on OoO cores e.g. splitting a function intentionally over multiple pages to keep the commonly used parts of functions used together in less pages which helps with instruction cache utilisation and iTLB pressure.

Lots of high performance microarchitectures use assumptions about control flow for optimisation e.g. use the direction (backward, forward) of conditional jumps and branches as weak prediction, convert conditional branches over a single instruction into predicated execution, fuse common instruction pairs into a single micro-operation. At least limited cooperation between compiler and CPU core is required to make good use of those features.

> Something I heard a while back is that very roughly 90%+ of compiler generated code is made up of 19 instructions and the rest are rare enough that you on x86/64 you shouldn't memorize them, just keep the manual handy. I wonder if that included various variations of instructions.

It would definitely have to include the various variations. I ran it on my system, and of the top 38 instructions, 13 of them are variations on `mov`. The 22nd most common instruction is `and`, 26th is `shl`, 34th is `shr`, 36th is `or`, 39th is `imul`. You need to know those.

You can with -march flags, but there was a long time where the added instructions weren't useful for "typical" programs, only high end ones using SIMD. So many of them still won't be generated, since autovectorization isn't all that reliable.

/usr/bin has certainly no -march=native extensions, not even SIMD. It's extremely conservative, unless you are using Gentoo (nobody does anymore).

/usr/local/bin with tuned CFLAGS sounds better for such a statistical analysis.

> Moreover, can you influence GCC over what instructions it emits? On Gentoo for example, you can setup your make file so that the while system is compiled with your specific processor in mind.

Yes, of course. On a Gentoo ~amd64 system where everything is compiled with "-O3 -march=native", I get 1311 different ASM instructions: https://gist.github.com/stefantalpalaru/932b6d0ef439756e825d...

Wow, that is fascinating. I need to play with this myself, I never heard of some of those like prefetcht0.

Reply on news.ycombinator.com