Possible inlining improvements

[tarcieri]

I ran RUSTFLAGS=-Ccodegen-units=1 cargo bench to see what changed versus just cargo bench. There were a few that stuck out in particular:

• wrapping ops/widening_mul
  • I512xI512: -25%
  • I1024xI1024: -4%
• widening ops/concatenating_mul
  • I128xI128: −18%
  • I512xI512: −31%
• wrapping ops/sub
  • I512-I512: −35%
  • I1024-I1024: −25%
• bounded random/random_mod
  • U1024: -11%
  • U1024 tiny high limb: -9%
• wrapping ops/widening_mul
  • U256xU256: -12%
• wrapping ops/mul_mod_special
  • U256: -10%
• extended greatest common divisor/xgcd
  • 1: -3%
  • 2: -3%
  • 3: -2%
  • 5: -23%
  • 6: -16%
  • 7: -18%
  • 8: -5%
  • 16: -22%
  • 32: -16%
  • 128: -8%
  • 256: -5%
• left shift/shl_vartime
  • small, U2048: -40%
  • large, U2048: -41%
• left shift/shl_vartime_wide
  • large, U2048: -22%
• right shift/shr
  • U2048: -8%
• right shift/shr_vartime_wide
  • large, U2048: -24%
• modular ops/invert_mod2k_vartime
  • U256: -18%

cc @andrewwhitehead @erik-3milabs

[andrewwhitehead]

I'm a bit unsure about the benefit here. Inlining is already used quite heavily, and inlining every call to these methods where they are used could greatly increase the code size of an implementing application compared to the artificial world of the benchmarks. Although I don't understand how codegen-units=1 works very well.

[tarcieri]

codegen-units=1 shows what happens when the whole crate is compiled as a single codegen unit, where otherwise it's split up over multiple compilation units to increase parallelism. So it's a way of empirically locating places where #[inline] could actually help.

The #[inline] attributes apply across codegen units, whereas within a codegen unit you're at the discretion of e.g. LLVM's inliner. It's mainly useful when you have a lot of function calls that wrap small functions where you might wind up with some wrapper function split across codegen units where you could otherwise have something approaching a zero cost abstraction. It effectively hints to the inliner it should take a second look.

Note that's a bit different from e.g. #[inline(always)] which overrides the inliner's decisions and should definitely be used judiciously.

These sorts of inlining improvements should be relatively deterministic, measurable, and empirically justifiable when they work.

[pinkforest]

I thought the biggest effect is on cross-crate linking where even LTO doesn't help and even inline(always) is not guaranteed to inline where optimizer makes the final decision depending on it's weights that inline(..) attributes affect.

It would be interesting to have tracking on code sizes under various scenarios across PRs and with various inlines a bit like codecov but for code sizes.

[tarcieri]

It impacts inlining between codegen units in the same crate too, which is what codegen-units=1 helps you spot because it turns the crate into a single codegen unit

[cong-or]

Hey, I'd like to pick this up. I'll start with the shift and wrapping arithmetic ops and put together a PR with before/after benchmarks. Let me know if anyone's already working on part of it.

[tarcieri]

@cong-or nope, now's a great time to take a look if you'd like

[cong-or]

@cong-or nope, now's a great time to take a look if you'd like

@tarcieri Nice, got started on this — here's the first pass covering shift and wrapping ops: #1229