3 ms·

> 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

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

crest 4y ago
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.
Taniwha 4y ago
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
- gpderetta 4y ago
  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).
  - NohatCoder 4y ago
    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.
    - gpderetta 4y ago
      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.
anonymoushn 4y ago
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 https://highload.fun/tasks/5/leaderboard
masklinn 4y ago
> 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)
- mcbain 4y ago
  My vote is that pext and pdep are the highlight from BMI2.
  - planede 4y ago
    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.
    - klodolph 4y ago
      Yes, there’s the annoying tendency of extensions to be slow on the first generation of processors that support them, and then faster afterwards.
      - planede 4y ago
        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 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.

crest 4y ago

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.

Taniwha 4y ago

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

gpderetta 4y ago
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).
- NohatCoder 4y ago
  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.
  - gpderetta 4y ago
    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.

anonymoushn 4y ago

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 https://highload.fun/tasks/5/leaderboard

masklinn 4y ago

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

mcbain 4y ago
My vote is that pext and pdep are the highlight from BMI2.
- planede 4y ago
  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.
  - klodolph 4y ago
    Yes, there’s the annoying tendency of extensions to be slow on the first generation of processors that support them, and then faster afterwards.
    - planede 4y ago
      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 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.