[rust-dev] Division and modulo for signed numbers

Erik S swede at earthling.net
Tue Apr 23 08:50:48 PDT 2013


On 4/23/2013 9:02 AM, Patrick Walton wrote:
> On 4/23/13 7:48 AM, swede at earthling.net wrote:
>> Performance should be about the same when using F-division:
>>   * Performance will go up for division by constant powers of two.
>>   * Performance will stay the same for division by compile-time
>> constants, since these are transformed by the compiler into
>> multiplies. (I actually think performance will go up slightly in this
>> case, but it's been a while since I looked at the algorithm.)
>>   * Performance on ARM will stay the same for divides by variables
>> (not known at compile-time), since ARM does not have a hardware divider.
>>   * Performance on x86/x64 for divides by variables will go down
>> slightly, since Intel's idiv instruction implements F-division.
>>
>> So one already very slow operation (x86 idiv) gets slightly slower,
>> one fast operation (divide by power-of-two) gets quite a bit faster.
>> It probably nets out near zero.
>
> I worry quite a bit about that last one. Rust language semantics
> strive to mirror the CPU instructions as closely as possible. This is
> why, for example, we were forced to make `<` respect NaN, unlike
> Haskell--if we didn't, we couldn't use the hardware floating point
> comparison instructions.
>
> I'm also nervous about C interoperability.
>
> Including F-division as a library function sounds fine to me
> though--macros or dot notation may be able to sweeten the syntax.
>
> Patrick
>
> _______________________________________________
> Rust-dev mailing list
> Rust-dev at mozilla.org
> https://mail.mozilla.org/listinfo/rust-dev
>
Patrick,
I would agree with you if it weren't for the cases where F-division
performs *better*. Division by a constant power-of-two is pretty common,
and is much faster in F-division.

I don't think correctness should be sacrificed for a slight performance
improvement in one case on one supported architecture. I've had real
bugs in my C code caused by incorrectly casting (or forgetting to cast)
to unsigned before a % operation. T-division causes *real* bugs.

I'm willing to spend some time implementing F-division, if I can get
some buy-in that the patch would be accepted.

Erik


More information about the Rust-dev mailing list