CODEWITHSUNDEEP
performancerust
llogiq
llogiq

Reputation: 14541

What is the fastest way to handle overflow on integer division/remainder without panic?

I'm still improving overflower to handle integer overflow. One goal was to be able use #[overflow(wrap)] to avoid panics on overflow. However, I found out that the .wrapping_div(_) and .wrapping_rem(_) functions of the standard integer types do in fact panic when dividing by zero. Edit: To motivate this use case better: Within interrupt handlers, we absolutely want to avoid panics. I assume that the div-by-zero condition is highly unlikely, but we still need to return a "valid" value for some definition of valid.

One possible solution is saturating the value (which I do when code is annotated with #[overflow(saturate)]), but this is likely relatively slow (especially since other,more operations are also saturated). So I want to add an #[overflow(no_panic)] mode that avoids panics completely, and is almost as fast as #[overflow(wrap)] in all cases.

My question is: What is the fastest way to return something (don't care what) without panicking on dividing (or getting the remainder) by zero?

Upvotes: 0

Views: 478

Answers (2)

Eli Friedman
Eli Friedman

Reputation: 2393

pub fn nopanic_signed_div(x: i32, y: i32) -> i32 {
    if y == 0 || y == -1 {
        // Divide by -1 is equivalent to neg; we don't care what
        // divide by zero returns.
        x.wrapping_neg()
    } else {
        // (You can replace this with unchecked_div to make it more
        // obvious this will never panic.)
        x / y
    }
}

This produces the following on x86-64 with "rustc 1.11.0-nightly (6e00b5556 2016-05-29)":

    movl    %edi, %eax
    leal    1(%rsi), %ecx
    cmpl    $1, %ecx
    ja  .LBB0_2
    negl    %eax
    retq
.LBB0_2:
    cltd
    idivl   %esi
    retq

It should produce something similar on other platforms.

At least one branch is necessary because LLVM IR considers divide by zero to be undefined behavior. Checking for 0 and -1 separately would involve an extra branch. With those constraints, there isn't really any other choice.

(It might be possible to come up with something slightly faster with inline assembly, but it would be a terrible idea because you would end up generating much worse code in the case of dividing by a constant.)

Whether this solution is actually appropriate probably depends on what your goal is; a divide by zero is probably a logic error, so silently accepting it seems like a bad idea.

Upvotes: 1

Adrian
Adrian

Reputation: 15171

Disclaimer: this isn't really a serious answer. It is almost certainly slower than the naive solution of using an if statement to check whether the divisor is zero.

#![feature(asm)]

fn main() {
    println!("18 / 3 = {}", f(18, 3));
    println!("2555 / 10 = {}", f(2555, 10));
    println!("-16 / 3 = {}", f(-16, 3));
    println!("7784388 / 0 = {}", f(7784388, 0));
}

fn f(x: i32, y: i32) -> i32 {
    let z: i32;
    unsafe {
        asm!(
            "
            test %ecx, %ecx
            lahf
            and $$0x4000, %eax
            or %eax, %ecx
            mov %ebx, %eax
            cdq
            idiv %ecx
            "
            : "={eax}"(z)
            : "{ebx}"(x), "{ecx}"(y)
            : "{edx}"
        );
    }
    z
}

Rust Playground

Upvotes: 2

Related Questions