4 ms·

It's not always superior! For example, I've been working on a big integer library. Addition is a bit annoying, because you need to add 3 numbers (the prior car

It's not always superior! For example, I've been working on a big integer library. Addition is a bit annoying, because you need to add 3 numbers (the prior carry bit, and the two digits you're adding) and get out a new carry bit and a resulting digit. This is a bit cumbersome: let (res, carry1) = target_digit.overflowing_add(carry as u64); let (res, carry2) = res.overflowing_add(other_digit); *target_digit = res; carry = carry1 || carry2; The resulting assembly is a fairly literal translation. We perform the addition using an add instruction, and extract the carry flag into a register using setb. addq (%rdi,%rsi,8), %rcx setb %r10b addq (%rdx,%rsi,8), %rcx setb %al movq %rcx, (%rdi,%rsi,8) orb %r10b, %al movzbl %al, %eax But there's a dedicated instruction for this, adc. adc adds two operands and the carry flag, while itself setting a carry flag. Manually unrolling the loop a bit, I wrote this assembly: shlb $8, {carry} adcq 0x00({y0}), {x0} adcq 0x08({y0}), {x1} adcq 0x10({y0}), {x2} adcq 0x18({y0}), {x3} adcq 0x20({y0}), {x4} adcq 0x28({y0}), {x5} setb {carry} And got a 3x speedup.

secondcoming 6y ago
What is Rust's policy for signed/unsigned int overflow? I assume that it's not modulo or else the complier should have generated ADC for you. I assume you've been using Compiler Explorer a lot?
- masklinn 6y ago
  > What is Rust's policy for signed/unsigned int overflow? Defined, by default checked in debug mode and unchecked in release, unsigned wraps and signed wraps as two's complement. This can be overridden by explicitly setting overflow-checks in the relevant profile. It also, separately, has explicitly wrapping, saturating and checking versions of basic arithmetic operations.
- palmtree3000 6y ago
  overflowing_add, like I was using above, is explicitly wrapping. I've found it very difficult to provoke rustc into emitting an ADC: the only case where it does so AFAICT is when adding u128s, which are implemented using u64s. Not sure why, except that the shortest function I could think of to emulate ADC is kind of baroque, and it's possible the compiler can't figure it out. I've mostly been using cpuprofiler[1] and Vtune to simultaneously profile my code and show the assembly. In theory they both provide timing information per-instruction, but I don't really trust it. For the 6 adc instructions above, it shows the number of clock ticks as ranging from 22 million to 3 billion, which doesn't make sense to me. But at least it shows me the assembly! [1] https://docs.rs/cpuprofiler/0.0.4/cpuprofiler/index.html https://docs.rs/cpuprofiler/0.0.4/cpuprofiler/index.html
  - secondcoming 6y ago
    This will change your life! https://godbolt.org/z/fntvYa https://godbolt.org/z/fntvYa
jeffdavis 6y ago
The article here: https://news.ycombinator.com/item?id=23351007 https://news.ycombinator.com/item?id=23351007 specifically recommends against the carry variants of addition, because the instructions are still dependent on each other and don't pipeline well. In other words, it's using the same algorithm, just buried in a single instruction, and that doesn't necessarily make it faster. Have you considered using a strategy similar to what the article suggests? I think the HN comments also had some additional suggestions.
- devit 6y ago
  The dependency is unavoidable due to the way addition works. The approach in the article only works if you are adding a lot of numbers together, and then indeed doing carry propagation once at the end is obviously faster. But of course there is no way that doing the carry propagation yourself on one addition can possibly be faster on a decent CPU that implements add-with-carry efficienly.
  - jeffdavis 6y ago
    Maybe it's worth considering an interface to a big int library that can defer carry work across many operations, and then normalizing at the end? That certainly sounds useful for, e.g., totaling an array of big integers.
- adwn 6y ago
  > that doesn't necessarily make it faster Did you miss the "And got a 3x speedup" part of the post you were replying to? Actual benchmarks of real code always trump theoretical deliberations.
  - jeffdavis 6y ago
    Yikes. I was just trying to link to a relevant technique that the author might find helpful. A big integer library may have many use cases; a benchmark only shows one data point. It's possible that by deferring carry work across more operations he'd see an even bigger improvement.
- 6y ago
sethhochberg 6y ago
Thanks for this - its been many years since I've done anything touching assembly, and never outside of an academic context, so when I read conversations like this I'm always curious for concrete examples of how people are actually _using_ this stuff beyond something vague like interacting with VT-x or working on an experimental OS.

secondcoming 6y ago

What is Rust's policy for signed/unsigned int overflow? I assume that it's not modulo or else the complier should have generated ADC for you. I assume you've been using Compiler Explorer a lot?

masklinn 6y ago
> What is Rust's policy for signed/unsigned int overflow? Defined, by default checked in debug mode and unchecked in release, unsigned wraps and signed wraps as two's complement. This can be overridden by explicitly setting overflow-checks in the relevant profile. It also, separately, has explicitly wrapping, saturating and checking versions of basic arithmetic operations.
palmtree3000 6y ago
overflowing_add, like I was using above, is explicitly wrapping. I've found it very difficult to provoke rustc into emitting an ADC: the only case where it does so AFAICT is when adding u128s, which are implemented using u64s. Not sure why, except that the shortest function I could think of to emulate ADC is kind of baroque, and it's possible the compiler can't figure it out. I've mostly been using cpuprofiler[1] and Vtune to simultaneously profile my code and show the assembly. In theory they both provide timing information per-instruction, but I don't really trust it. For the 6 adc instructions above, it shows the number of clock ticks as ranging from 22 million to 3 billion, which doesn't make sense to me. But at least it shows me the assembly! [1] https://docs.rs/cpuprofiler/0.0.4/cpuprofiler/index.html https://docs.rs/cpuprofiler/0.0.4/cpuprofiler/index.html
- secondcoming 6y ago
  This will change your life! https://godbolt.org/z/fntvYa https://godbolt.org/z/fntvYa

jeffdavis 6y ago

The article here: https://news.ycombinator.com/item?id=23351007 https://news.ycombinator.com/item?id=23351007 specifically recommends against the carry variants of addition, because the instructions are still dependent on each other and don't pipeline well. In other words, it's using the same algorithm, just buried in a single instruction, and that doesn't necessarily make it faster. Have you considered using a strategy similar to what the article suggests? I think the HN comments also had some additional suggestions.

devit 6y ago
The dependency is unavoidable due to the way addition works. The approach in the article only works if you are adding a lot of numbers together, and then indeed doing carry propagation once at the end is obviously faster. But of course there is no way that doing the carry propagation yourself on one addition can possibly be faster on a decent CPU that implements add-with-carry efficienly.
- jeffdavis 6y ago
  Maybe it's worth considering an interface to a big int library that can defer carry work across many operations, and then normalizing at the end? That certainly sounds useful for, e.g., totaling an array of big integers.
adwn 6y ago
> that doesn't necessarily make it faster Did you miss the "And got a 3x speedup" part of the post you were replying to? Actual benchmarks of real code always trump theoretical deliberations.
- jeffdavis 6y ago
  Yikes. I was just trying to link to a relevant technique that the author might find helpful. A big integer library may have many use cases; a benchmark only shows one data point. It's possible that by deferring carry work across more operations he'd see an even bigger improvement.
6y ago

sethhochberg 6y ago

Thanks for this - its been many years since I've done anything touching assembly, and never outside of an academic context, so when I read conversations like this I'm always curious for concrete examples of how people are actually _using_ this stuff beyond something vague like interacting with VT-x or working on an experimental OS.