palmtree3000

6 years agodiscuss

I was briefly very excited when I read that article, actually. But as devit points out in a sibling comment, that technique is only relevant to cases where you're adding more than 2 numbers.

Multiplication initially seemed like a very promising use case, since it's basically repeated addition. But I'm not super optimistic about that, because I think it's dominated by the alternate optimization of noticing that the product of two 64 bit numbers cannot saturate the high 64 bits of the resulting 128 bit number, which causes carries to be bounded [1].

[1] https://github.com/rocurley/bignum/blob/b45448a156fb9100ab06...

palmtree3000

6 years agodiscuss

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

palmtree3000

6 years agodiscuss

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.

comments