8 ms·

How Rust 1.26 more than tripled the speed of my code

305 points by nonsince 8y ago

the_new_guy_29 8y ago
"decreased the execution time by a factor of 3" So article is about a flew in previous versions of Rust not supporting 128-bit numbers on x86_64. But title makes it sound like "switching to Rust was the breakthrough". Or am i paranoid about it..
- viraptor 8y ago
  The original title is the more precise "How a Rust upgrade more than tripled the speed of my code". Also I think mentioning the version made it clear that it's about a specific version, not about rust in general.
  - magduf 8y ago
    Maybe they should change it to: "How an upgrade to Rust 1.26 more than tripled the speed of my code"
- infogulch 8y ago
  They probably wouldn't have mentioned the specific version if they were talking about switching languages instead of switching compiler versions.
- rkagerer 8y ago
  I'd say its more about how LLVM outperformed their previously handwritten assembly (the latter was impeded by crud from the asm! macro).
  - Ygg2 8y ago
    That would have done nothing, if Rust didn't stabilize u128/i128.
- codetrotter 8y ago
  > But title makes it sound like "switching to Rust was the breakthrough". Or am i paranoid about it.. Since titles keep changing on HN (for good reasons), I can’t be sure you saw the same title that I did, but if you did I disagree. The current title is “How Rust 1.26 more than tripled the speed of my code”. Because that title specifies a specific version number, I expected the blog post to be about exactly the kind of thing it was; some new feature or improvement in that version of Rust which would make their software run faster compared to the previous version of Rust they were using.
hoare 8y ago
What other factors played a role in your decision to use rust over other languages when 128bit arithmetic played such an important role you wrote inline assembly for it?
- lmm 8y ago
  What other languages are sensible options for when you need to work with inline assembly?
  - nonsince 8y ago
    C has had strong support for inline assembly for a long time, and in fact for a short period we called out to C in order to use inline assembly on stable (the function call overhead was worthwhile compared to how much faster the assembly implementation of the function was).
  - e12e 8y ago
    From just reading the discussion so far, I'd like to see how a naive implementation in Julia would do (Julia does type inference, and some quick duck-duck-ing indicates that unsigned 128 bit int is the biggest regular number type - before having to go to bigint). [ed: ok, from a skim, I see this is actually about 256bit multiplication - which makes me curious how just using bigints and * (mul operator) would work in Julia. Also, I don't get this: > u256_mul multiplies two 256-bit numbers to get a 256-bit result (in Rust, we just create a 512-bit result and then throw away the top half but in assembly we have a seperate implementation) How do they know the result will fit in 256 bits? Sounds like they know more about the arguments than both having to be 256 bits long? Or do they want multiply and shift?]
    - Retra 8y ago
      That doesn't say it will fit in 256 bits, it says it is truncated to 256 bits.
    - wallnuss 8y ago
      Julia has `widemul` which takes two `Int64` and produces an `Int128`. It is also not to hard to actually add your own primitive type for `Int256` (with the caveat that it needs support from LLVM, which I haven't checked)
tzahola 8y ago
* compared to Rust 1.25
- alimbada 8y ago
  An unnecessary distinction as it can quite be easily inferred from the current title. Despite this there seem to be a lot of people nitpicking on semantics of the title in this thread. It's unnecessary noise and detracts (and distracts) from the real conversation.
  - paulmd 8y ago
    It's not just this thread. HN is absolutely obsessed with nitpicking titles and yes, it's distracting and detracts from actual discussion of the topics. The moderation team here tacitly encourages it by catering to it. I've seen some threads go through 2 or 3 title changes as people find something new to complain about. Really it's almost a form of editorializing in itself - the title of the article is what it is, people here just think they know better than the author.
FPGAhacker 8y ago
>”When Rust does a * b when a and b are both u64 the CPU actually multiplies them to create a 128-bit result and then Rust just throws away the upper 64 bits.” Is that right? Wouldn’t that answer look like nonsense? I would have guessed it tossed the lower 64bits so it looked like rounding by truncation at least.
- deleted 8y ago
  [deleted]
- monocasa 8y ago
  It's right. This is all integer arithmetic, so you wouldn't want to just drop the lower 64bits.
- chrisseaton 8y ago
  Well semantics for a number that's too big to fit into the result can be debated, so there's no one right answer and all are nonsense in some way or another. You talk about rounding but if the number's too big then then you're only ever going to round to the max number you could use, so we might as well call that saturation. Discarding the upper bits means you are implementing modular arithmetic. Both saturation and modular arithmetic are well defined, and can both be reasonable choices. I think most languages implement modular arithmetic, so that's what most programmers expect, and it seems a reasonable choice to me compared to saturation.
- DSingularity 8y ago
  It doesn’t make sense to throw away either. Remember the 64 bit numbers can be small too. So throwing away the lower will result in 2*2=0.
- OskarS 8y ago
  That's how floats work, not ints. Unsigned integers more or less always wrap on overflow, which is what you want, generally speaking. Essentially, the operation is carried out modulo the size of the type. For signed integers, overflow is undefined in C/C++, but generally results in wrapping as well.
jsd1982 8y ago
Are you sure those are missed optimization opportunities where llvm copied values to registers as temporary storage instead of a direct copy to the destination register? I saw use of the temporary registers below the lines in question. Perhaps it was just a cheap copy of the value to a register which will be used later because the original destination register was clobbered. Also I would hazard a guess that pushing flag state into a register is a lot faster than the stack. Finally, it'd be interesting to see the original hand-rolled inline assembly used with "r" instead of "m" to see how llvm stacks up against the intended version without the redundant memory load/stores.
- nonsince 8y ago
  Great catch, you're absolutely right. LLVM is smarter than me once again.
tomsmeding 8y ago
> especially since the original code used highly-optimised assembly incantations from our resident cycle wizard. He/she might be cool, but I think someone familiar with assembly optimisation would think to look at the generated assembly as well, after noticing the speedup is not what you expect. Don't go hand-writing assembly routines thinking your code is fast without actually checking whether your code is fast. :)
- nonsince 8y ago
  They're certainly familiar with assembly itself, but the `asm!` macro and the related constructs in Clang/GCC is its own beast and has a lot of footguns (like GCC allocating registers as overlapping by default). I don't begrudge them writing suboptimal assembly, since it already beat our Rust implementation by a significant margin.
- stochastic_monk 8y ago
  And correct.
pbsd 8y ago
The code in the blog post does not match what is actually benchmarked. The reason `u256_full_mul` is so much faster than the inline assembly version is that it omits the upper part of the result, due to how the benchmark is done (cf. https://github.com/paritytech/bigint/blob/44a3133030306d9fcc9865b2e8e8368f6992cc98/benches/bigint.rs#L114-L115 https://github.com/paritytech/bigint/blob/44a3133030306d9fcc...). There should be 16 full 64x64->128 multiplications (unless you're doing Karatsuba, which is not the case here) in a full 256-bit multiplication, but I only count 6 in the benchmark's inner loop (plus 4 64x64->64 multiplications). No wonder it's faster. The disassembly for the Rust output of `u256_full_mul` at the end is also terrible, and it looks like the output of a debug build. There's no reason an optimizing compiler should be outputting `pushfd` and `popfd` in performant code. The benchmarked loop does not have those instructions.
- nonsince 8y ago
  It's possible that `pushfq`+`popfq` get turned into a `mov` from the flag register into a the output register due to microcode-level optimisations.
  - pbsd 8y ago
    That is not the case. On a Skylake chip, a pushfd + popfd roundtrip costs 24 cycles.
    - feikname 8y ago
      Just out of curiosity, how do you know this? Is it some kind of measurement you made yourself, written on Intel docs somewhere or something else? I've been wondering about how much instructions cost lately and would like to be able to know this without the need of asking others.
      - pbsd 8y ago
        Agner's instruction listings [1] and InstLatX64 [2] are good sources for a variety of chips. The 24 cycle figure above can be seen at https://github.com/InstLatx64/InstLatx64/blob/ee13abcfb1e2bb8207737a362daa73d7c9ed66a8/GenuineIntel00506E3_Skylake2_InstLatX64.txt#L625-L628 https://github.com/InstLatx64/InstLatx64/blob/ee13abcfb1e2bb... [1] http://www.agner.org/optimize/#manuals http://www.agner.org/optimize/#manuals [2] https://github.com/InstLatx64 https://github.com/InstLatx64
deleted 8y ago
[deleted]
comex 8y ago
The behavior with "m" is quite strange. In theory, it should produce a memory operand pointing directly to where the function argument was passed on the stack, rather than copying it to registers and then back onto the stack. I can reproduce this with Rust nightly: https://play.rust-lang.org/?version=nightly&mode=release https://play.rust-lang.org/?version=nightly&mode=release However, Clang appears to do the right thing with equivalent C code: https://godbolt.org/g/B1sjfS https://godbolt.org/g/B1sjfS This is strange because Rust and Clang both use LLVM for their backend. Looking at the LLVM IR produced, Rust's IR straightforwardly corresponds to the source code: a load instruction (to evaluate `self_t[0]`) whose result is passed to an asm instruction: %0 = getelementptr inbounds %U256, %U256* %self, i64 0, i32 0, i64 0 %1 = load i64, i64* %0, align 8 tail call void asm sideeffect "mulq $0", "m,~{dirflag},~{fpsr},~{flags}"(i64 %1) #1, !srcloc !0 But Clang's omits the load, and transforms the "m" constraint to "* m" (without the space, bah HN formatting): %2 = getelementptr inbounds %struct.U256, %struct.U256* %0, i64 0, i32 0, i64 0, !dbg !24 call void asm sideeffect "mulq $0", "*m,~{dirflag},~{fpsr},~{flags}"(i64* nonnull %2) #2, !dbg !26, !srcloc !27 Hmm… seems to be related to this Rust bug: https://github.com/rust-lang/rust/issues/16383 https://github.com/rust-lang/rust/issues/16383
Const-me 8y ago
Their assembly implementation can be improved, at least when targeting modern hardware. Here’s an article explaining how to use new instructions to implement large integers multiplication: http://www.intel.com/content/dam/www/public/us/en/documents/white-papers/ia-large-integer-arithmetic-paper.pdf http://www.intel.com/content/dam/www/public/us/en/documents/...
- nonsince 8y ago
  If you use Rust's equivalent of `-march=native` you get faster code that can target modern hardware. We would have to get another factor-of-two speedup for the maintainance burden of using inline assembly to be worthwhile. https://gist.github.com/Vurich/5cb83c773e90fc7a463ccb58e1dad4e3 https://gist.github.com/Vurich/5cb83c773e90fc7a463ccb58e1dad...
kibwen 8y ago
Happy to see alternative language features reducing the need for inline assembly, not just with the 128-bit integer support in 1.26 but also with the stable SIMD support coming in 1.27 (so crates like https://users.rust-lang.org/t/jetscii-now-works-with-future-stable-rust-1-27-0/17426 https://users.rust-lang.org/t/jetscii-now-works-with-future-... can at last work on stable). Sadly the current implementation of inline assembly is so inextricably tied to LLVM that there's resistance to stabilizing it in its current form, though in this case I think the perfect is being allowed to be the enemy of the good^W good-enough^W janky-but-acceptable.
the8472 8y ago
There's a proposal to introduce a double wide mul which should make this much more ergonomical to solve. https://github.com/rust-lang/rfcs/pull/2417 https://github.com/rust-lang/rfcs/pull/2417
andrepd 8y ago
Could this be compared with C/gcc and C++/g++? Because this is what Rust is aiming to displace.
- steveklabnik 8y ago
  Sure; this is exposing LLVM's support, so it should be the same as clang.

305 points by nonsince 8y ago

"decreased the execution time by a factor of 3" So article is about a flew in previous versions of Rust not supporting 128-bit numbers on x86_64. But title makes it sound like "switching to Rust was the breakthrough". Or am i paranoid about it..

viraptor 8y ago
The original title is the more precise "How a Rust upgrade more than tripled the speed of my code". Also I think mentioning the version made it clear that it's about a specific version, not about rust in general.
- magduf 8y ago
  Maybe they should change it to: "How an upgrade to Rust 1.26 more than tripled the speed of my code"
infogulch 8y ago
They probably wouldn't have mentioned the specific version if they were talking about switching languages instead of switching compiler versions.
rkagerer 8y ago
I'd say its more about how LLVM outperformed their previously handwritten assembly (the latter was impeded by crud from the asm! macro).
- Ygg2 8y ago
  That would have done nothing, if Rust didn't stabilize u128/i128.
codetrotter 8y ago
> But title makes it sound like "switching to Rust was the breakthrough". Or am i paranoid about it.. Since titles keep changing on HN (for good reasons), I can’t be sure you saw the same title that I did, but if you did I disagree. The current title is “How Rust 1.26 more than tripled the speed of my code”. Because that title specifies a specific version number, I expected the blog post to be about exactly the kind of thing it was; some new feature or improvement in that version of Rust which would make their software run faster compared to the previous version of Rust they were using.

hoare 8y ago

What other factors played a role in your decision to use rust over other languages when 128bit arithmetic played such an important role you wrote inline assembly for it?

lmm 8y ago
What other languages are sensible options for when you need to work with inline assembly?
- nonsince 8y ago
  C has had strong support for inline assembly for a long time, and in fact for a short period we called out to C in order to use inline assembly on stable (the function call overhead was worthwhile compared to how much faster the assembly implementation of the function was).
- e12e 8y ago
  From just reading the discussion so far, I'd like to see how a naive implementation in Julia would do (Julia does type inference, and some quick duck-duck-ing indicates that unsigned 128 bit int is the biggest regular number type - before having to go to bigint). [ed: ok, from a skim, I see this is actually about 256bit multiplication - which makes me curious how just using bigints and * (mul operator) would work in Julia. Also, I don't get this: > u256_mul multiplies two 256-bit numbers to get a 256-bit result (in Rust, we just create a 512-bit result and then throw away the top half but in assembly we have a seperate implementation) How do they know the result will fit in 256 bits? Sounds like they know more about the arguments than both having to be 256 bits long? Or do they want multiply and shift?]
  - Retra 8y ago
    That doesn't say it will fit in 256 bits, it says it is truncated to 256 bits.
  - wallnuss 8y ago
    Julia has `widemul` which takes two `Int64` and produces an `Int128`. It is also not to hard to actually add your own primitive type for `Int256` (with the caveat that it needs support from LLVM, which I haven't checked)

tzahola 8y ago

* compared to Rust 1.25

alimbada 8y ago
An unnecessary distinction as it can quite be easily inferred from the current title. Despite this there seem to be a lot of people nitpicking on semantics of the title in this thread. It's unnecessary noise and detracts (and distracts) from the real conversation.
- paulmd 8y ago
  It's not just this thread. HN is absolutely obsessed with nitpicking titles and yes, it's distracting and detracts from actual discussion of the topics. The moderation team here tacitly encourages it by catering to it. I've seen some threads go through 2 or 3 title changes as people find something new to complain about. Really it's almost a form of editorializing in itself - the title of the article is what it is, people here just think they know better than the author.

FPGAhacker 8y ago

>”When Rust does a * b when a and b are both u64 the CPU actually multiplies them to create a 128-bit result and then Rust just throws away the upper 64 bits.” Is that right? Wouldn’t that answer look like nonsense? I would have guessed it tossed the lower 64bits so it looked like rounding by truncation at least.

deleted 8y ago
[deleted]
monocasa 8y ago
It's right. This is all integer arithmetic, so you wouldn't want to just drop the lower 64bits.
chrisseaton 8y ago
Well semantics for a number that's too big to fit into the result can be debated, so there's no one right answer and all are nonsense in some way or another. You talk about rounding but if the number's too big then then you're only ever going to round to the max number you could use, so we might as well call that saturation. Discarding the upper bits means you are implementing modular arithmetic. Both saturation and modular arithmetic are well defined, and can both be reasonable choices. I think most languages implement modular arithmetic, so that's what most programmers expect, and it seems a reasonable choice to me compared to saturation.
DSingularity 8y ago
It doesn’t make sense to throw away either. Remember the 64 bit numbers can be small too. So throwing away the lower will result in 2*2=0.
OskarS 8y ago
That's how floats work, not ints. Unsigned integers more or less always wrap on overflow, which is what you want, generally speaking. Essentially, the operation is carried out modulo the size of the type. For signed integers, overflow is undefined in C/C++, but generally results in wrapping as well.

jsd1982 8y ago

Are you sure those are missed optimization opportunities where llvm copied values to registers as temporary storage instead of a direct copy to the destination register? I saw use of the temporary registers below the lines in question. Perhaps it was just a cheap copy of the value to a register which will be used later because the original destination register was clobbered. Also I would hazard a guess that pushing flag state into a register is a lot faster than the stack. Finally, it'd be interesting to see the original hand-rolled inline assembly used with "r" instead of "m" to see how llvm stacks up against the intended version without the redundant memory load/stores.

nonsince 8y ago
Great catch, you're absolutely right. LLVM is smarter than me once again.

tomsmeding 8y ago

> especially since the original code used highly-optimised assembly incantations from our resident cycle wizard. He/she might be cool, but I think someone familiar with assembly optimisation would think to look at the generated assembly as well, after noticing the speedup is not what you expect. Don't go hand-writing assembly routines thinking your code is fast without actually checking whether your code is fast. :)

nonsince 8y ago
They're certainly familiar with assembly itself, but the `asm!` macro and the related constructs in Clang/GCC is its own beast and has a lot of footguns (like GCC allocating registers as overlapping by default). I don't begrudge them writing suboptimal assembly, since it already beat our Rust implementation by a significant margin.
stochastic_monk 8y ago
And correct.

pbsd 8y ago

The code in the blog post does not match what is actually benchmarked. The reason `u256_full_mul` is so much faster than the inline assembly version is that it omits the upper part of the result, due to how the benchmark is done (cf. https://github.com/paritytech/bigint/blob/44a3133030306d9fcc9865b2e8e8368f6992cc98/benches/bigint.rs#L114-L115 https://github.com/paritytech/bigint/blob/44a3133030306d9fcc...). There should be 16 full 64x64->128 multiplications (unless you're doing Karatsuba, which is not the case here) in a full 256-bit multiplication, but I only count 6 in the benchmark's inner loop (plus 4 64x64->64 multiplications). No wonder it's faster. The disassembly for the Rust output of `u256_full_mul` at the end is also terrible, and it looks like the output of a debug build. There's no reason an optimizing compiler should be outputting `pushfd` and `popfd` in performant code. The benchmarked loop does not have those instructions.

nonsince 8y ago
It's possible that `pushfq`+`popfq` get turned into a `mov` from the flag register into a the output register due to microcode-level optimisations.
- pbsd 8y ago
  That is not the case. On a Skylake chip, a pushfd + popfd roundtrip costs 24 cycles.
  - feikname 8y ago
    Just out of curiosity, how do you know this? Is it some kind of measurement you made yourself, written on Intel docs somewhere or something else? I've been wondering about how much instructions cost lately and would like to be able to know this without the need of asking others.
    - pbsd 8y ago
      Agner's instruction listings [1] and InstLatX64 [2] are good sources for a variety of chips. The 24 cycle figure above can be seen at https://github.com/InstLatx64/InstLatx64/blob/ee13abcfb1e2bb8207737a362daa73d7c9ed66a8/GenuineIntel00506E3_Skylake2_InstLatX64.txt#L625-L628 https://github.com/InstLatx64/InstLatx64/blob/ee13abcfb1e2bb... [1] http://www.agner.org/optimize/#manuals http://www.agner.org/optimize/#manuals [2] https://github.com/InstLatx64 https://github.com/InstLatx64

deleted 8y ago

[deleted]

comex 8y ago

The behavior with "m" is quite strange. In theory, it should produce a memory operand pointing directly to where the function argument was passed on the stack, rather than copying it to registers and then back onto the stack. I can reproduce this with Rust nightly: https://play.rust-lang.org/?version=nightly&mode=release https://play.rust-lang.org/?version=nightly&mode=release However, Clang appears to do the right thing with equivalent C code: https://godbolt.org/g/B1sjfS https://godbolt.org/g/B1sjfS This is strange because Rust and Clang both use LLVM for their backend. Looking at the LLVM IR produced, Rust's IR straightforwardly corresponds to the source code: a load instruction (to evaluate `self_t[0]`) whose result is passed to an asm instruction: %0 = getelementptr inbounds %U256, %U256* %self, i64 0, i32 0, i64 0 %1 = load i64, i64* %0, align 8 tail call void asm sideeffect "mulq $0", "m,~{dirflag},~{fpsr},~{flags}"(i64 %1) #1, !srcloc !0 But Clang's omits the load, and transforms the "m" constraint to "* m" (without the space, bah HN formatting): %2 = getelementptr inbounds %struct.U256, %struct.U256* %0, i64 0, i32 0, i64 0, !dbg !24 call void asm sideeffect "mulq $0", "*m,~{dirflag},~{fpsr},~{flags}"(i64* nonnull %2) #2, !dbg !26, !srcloc !27 Hmm… seems to be related to this Rust bug: https://github.com/rust-lang/rust/issues/16383 https://github.com/rust-lang/rust/issues/16383

Const-me 8y ago

Their assembly implementation can be improved, at least when targeting modern hardware. Here’s an article explaining how to use new instructions to implement large integers multiplication: http://www.intel.com/content/dam/www/public/us/en/documents/white-papers/ia-large-integer-arithmetic-paper.pdf http://www.intel.com/content/dam/www/public/us/en/documents/...

nonsince 8y ago
If you use Rust's equivalent of `-march=native` you get faster code that can target modern hardware. We would have to get another factor-of-two speedup for the maintainance burden of using inline assembly to be worthwhile. https://gist.github.com/Vurich/5cb83c773e90fc7a463ccb58e1dad4e3 https://gist.github.com/Vurich/5cb83c773e90fc7a463ccb58e1dad...

kibwen 8y ago

Happy to see alternative language features reducing the need for inline assembly, not just with the 128-bit integer support in 1.26 but also with the stable SIMD support coming in 1.27 (so crates like https://users.rust-lang.org/t/jetscii-now-works-with-future-stable-rust-1-27-0/17426 https://users.rust-lang.org/t/jetscii-now-works-with-future-... can at last work on stable). Sadly the current implementation of inline assembly is so inextricably tied to LLVM that there's resistance to stabilizing it in its current form, though in this case I think the perfect is being allowed to be the enemy of the good^W good-enough^W janky-but-acceptable.

the8472 8y ago

There's a proposal to introduce a double wide mul which should make this much more ergonomical to solve. https://github.com/rust-lang/rfcs/pull/2417 https://github.com/rust-lang/rfcs/pull/2417

andrepd 8y ago

Could this be compared with C/gcc and C++/g++? Because this is what Rust is aiming to displace.

steveklabnik 8y ago
Sure; this is exposing LLVM's support, so it should be the same as clang.