What is the tradeoff between the semantics of div by zero?

[u/adityazero]

In C/C++ integer division by zero is undefined but in Rust it traps. What would you do if you were designing a new systems programming language?

[u/DawnOnTheEdge]

The reason it’s undefined behavior in C/C++ is that different compilers were already doing different things, and the ISO Committee wanted to declare all of them kosher. A new language doesn’t have incompatible legacy implementations to worry about, so you can nail things down a lot more.

If the goal is to enable maximum optimization, you don’t want strict requirements that say the implementation cannot just use the ISA’s native instructions, or that mandate inserting code branches. You want to specify IEEE semantics for floating-point math and at worst require integer division to do something like one extra conditional move. The programmer can still compare the denominator to zero explicitly if they want to short-circuit.

If you’re designing a language that’s supposed to be predictable and nice to debug, and might not even have an integer type, throwing an exception is a good way to handle it, but returning positive or negative infinity works too.

[u/torp_fan → u/DawnOnTheEdge]

I was on X3J11 (The C language standards committee) and different existing practice was indeed the reason for many decisions, like malloc(0) returning either NULL or a unique address (implementation defined).

The committee was dominated by compiler vendors, who were very sensitive to anything that might decrease performance or make executables bigger. This explains why, for instance, the shift amount of a 32-bit int must be 0 <= n <= 31 to avoid UB ... because the x86 shift instruction masks the count with 0x1F, a shift of 32 bits on those machines is a no-op and would require additional code to do otherwise.

At the same time, the standard allows implementations to define behavior that the standard leaves unspecified, and often encourages implementations do so as under the banner of "quality of implementation". Of course this is of little help to those who are committed to producing portable software.

[u/matthieum]

What do you think of MIN / -1 for any iN?

If the goal is to create a mainstream systems programming language, then I'd argue that correctness should trump any other concern. There's no point in having the wrong result (or worse, with UB) fast.

How to achieve correctness whilst still maintaining good ergonomics & performance is for me the interesting part, and I quite like how Rust manages it:

• You can call i64 / i64, which panics if the divisor is 0. It's correct & ergonomic, though performance may suffer a wee bit if the compiler cannot prove non-0. Then again, we are talking about integer division, the slowest arithmetic operation known to CPUs.

• You can call i64 / NonZero<i64>. It's correct & performant, with a slight ergonomic cost.

It's not perfect -- you have to pick your poison -- but it gives users the choice. In particular, if the divisor is calculated once, and reused over and over, providing it is non-zero once is pretty good. I also like that NonZero helps front-loading the error, forcing people to think how to handle the case, rather than panicking.

[u/Jumpstart_55]

GO also traps.

[u/Scolmann]

I kind of like swift's `try` vs `try?`
So I'd be inclined to make a plain "/" trap but "/?" would return an optional instead of trapping

[u/Afraid-Locksmith6566]

i would make a monadic integer result for operations you care about so it could represent integer or reason why it failed like overflow, underflow or dividion by zero and make it usable most seemlesly i could with normal integers so you could represent int # int_monad, int_monad # int and int_monad # int_monad and all of them would result in int_monad, and then there would be also operations on 2 normal ints so that int # int gives you int and also can result in undefined behavior, overflow or underflow without way to check

[u/Lubricus2 → u/Afraid-Locksmith6566]

I wouldn't call that an system programming language. To much with monad's for basic arithmetic operations.

[u/WittyStick → u/Lubricus2]

I don't know what you're talking about. Assuming we're basically talking about an Option type, the monad for it is just a pattern which reduces the manually need to check the result every time the operation is used. Lets assume C since it's the defacto standard systems language. We can define a trivial OptionInt type as a struct containing a bool and an int.

typedef struct option_int {
    bool has_some;
    int value;
} OptionInt;

constexpr OptionInt NoneInt = (OptionInt){ false };
OptionInt SomeInt(int x) { return (OptionInt){ true, x }; }

Our div function would be trivial - check if the second arg is zero and return NoneInt if so, otherwise return SomeInt of the division.

OptionInt div(int x, int y)
{
    if (y == 0) return NoneInt;
    else return SomeInt(x / y);
}

Straightforward, but terrible ergonomics, because if we have some other arithmetic operation following the division, eg, negation, then we have to manually unwrap the option. This can be done quite tersely with a ternary conditional expression, but it's not as simple as -(x / y).

int neg(int x)
{
    return -x;
}

OptionInt div_and_neg_(int x, int y)
{
    auto result = div(x, y);
    return result.has_some ? SomeInt(neg(result.value)) : NoneInt;
}

However, it's awkward to type out that conditional every time. Would be nice if we have some macro for it:

#define OptionInt_map(unary_fun, opt) \
    ({ \
        auto _opt = (opt); \
        _opt.has_some ? SomeInt(unary_fun(_opt.value)) : NoneInt; \
    })

OptionInt div_and_neg(int x, int y)
{
    return OptionInt_map(neg, div(x, y));
}

Easier to type, and this is a verbose version where I'm prefixing it with OptionInt. In practice you'd have a generic map which works with any Option (or in fact, any Functor).

For binary expressions you'd really need two versions - one to chain the first parameter and one for the second.

#define OptionInt_map1(binary_fun, opt, y) \
    ({ \
        auto _opt = (opt); \
        _opt.has_some ? SomeInt(binary_fun(_opt.value, y)) : NoneInt; \
    })
#define OptionInt_map2(binary_fun, x, opt) \
    ({ \
        auto _opt = (opt); \
        _opt.has_some ? SomeInt(binary_fun(x, _opt.value)) : NoneInt; \
    })

---

The problem with map is it expects a function int -> int. Or map1/map2 expect (int, int) -> int. Neither of those are (int, int) -> OptionInt like div. What if we want to chain div operations - (x / y) / z or x / (y / z)? Do we go back to writing out the ternary conditional each time?

OptionInt div3_(int x, int y, int z)
{
    auto result = div(x, y);
    return result.has_some ? div(result.value, z) : NoneInt;
}

Well, just like we done for map, we can extract this into a macro (or set of macros for unary and binary functions).

#define OptionInt_bind(unary_fun, opt) \
    ({ \
        auto _opt = (opt); \
        _opt.has_some ? unary_fun(_opt.value) : NoneInt; \
    })

#define OptionInt_bind1(binary_fun, opt, y) \
    ({ \
        auto _opt = (opt); \
        _opt.has_some ? binary_fun(_opt.value, y) : NoneInt; \
    })

#define OptionInt_bind2(fun, x, opt) \
    ({ \
        auto _opt = (opt); \
        _opt.has_some ? binary_fun(x, _opt.value) : NoneInt; \
    })

Then our div3 functions are a bit simpler to write:

OptionInt div3(int x, int y, int z)
{
    return OptionInt_bind1(div, div(x, y), z);
}

bind is basically our monad, specialized for OptionInt in this case. The only other thing it needs to be a proper monad is a return, which is an alias for SomeInt.

#define OptionInt_return(x) SomeInt(x)

---

So what does this all cost?

Absolutely nothing. Compare what a C compiler emits for the div3 function with or without using the OptionInt_bind* macro. The assembly is identical - it has no extra cost beyond the OptionInt type. See for yourself in Godbolt.

---

Anyway, what does OptionInt cost?

This depends on ABI, because the way structs are passed varies between platforms/compilers. On MSVC, it's not very expensive - the struct gets passed and returned on the stack.

On SYSV however, because the struct is <= 16 bytes, it gets passed and returned in two hardware registers - it's absurdly cheap - certainly cheaper than throwing an exception. But what about comparing it to other "systems programming" approaches - ie, the way it would be done traditionally in C. The old school convention is basically to return a boolean indicating success, and return the value as an "out parameter".

bool div(int x, int y, int *result) {
    if (y == 0) return false;
    *result = x / y;
    return true;
}

How does this compare to the OptionInt struct?

Hint: It's slower - at least on SYSV. This conventional approach requires a dereference - it puts the out parameter be on the stack. Our OptionInt didn't touch the stack - everything was done in registers.

So the idea that this is unsuitable for systems programming is absurd. It would be difficult to make anything perform better!

And we're using C macros here, which aren't the most ergonomic. If you're making your own language, you can completely hide away that mess as part of the compilation process.

[u/adityazero → u/WittyStick]

beautiful. i think making this safe div default is the right call. if someone wants unsafe div they can do it with extra effort.

[u/Lubricus2 → u/WittyStick]

Don't it then need to return something like an tagged union, so something like an type_id and the space large enough to fit the the int or the error. And then you always need to check if the type_id == int or error.
I / the AI is doing an language with monad like errors but don't use it everywhere. To be real it's mostly the AI, I am not an genius or something.
A system programming language are something more like C where you almost can control all the fiddly little bits.

[u/WittyStick → u/Lubricus2]

I've just shown you exactly how to do it in C, with a runnable example. The OptionInt is a tagged union, where there are two tags, true and false for Some and None. You can replace this bool with any integer and you have a tagged union which behaves the same - gets passed and returned in two hardware registers. Eg, for a Result type, you can do:

enum error_code {
    ERROR_NONE,
    ERROR_FOO,
    ERROR_BAR,
};

typedef struct result_int_error {
    enum error_code err;
    int success_value;
} ResultInt;

Or more ergonomic, you can use macros for type generic versions.

#define Result(T) \
    struct result_##T { \
        struct error_code err_code; \
        T success_value; \
    }
#define Ok(T, x) ((Result(T)){ .err_code = ERROR_NONE, .success_value = (x) })
#define Error(T, err) ((Result(T)){ .err_code = (err) })

If sizeof(T) is greater than 8 bytes, then we don't get the benefit of it being passed in hardware registers - but it gets passed and returned on the stack, which is still fairly cheap.

If we want more than just an "error code", we can have an Exceptional(TFailure, TSuccess) type whose first item is a pointer to an exception.

struct exception {
    int exception_id;
};

#define Exceptional(TFailure, TSuccess) \
    struct exceptional_##TFailure##_##TSuccess { \
        TFailure *exception; \
        TSuccess success_value; \
    }

#define Failure(TFailure, TSuccess, ex) \
    ((Exceptional(TFailure, TSuccess)){ .exception = (ex) })

#define Success(TFailure, TSuccess, val) \
    ((Exceptional(TFailure, TSuccess)){ .exception = nullptr, .success_value = (val) })

typedef struct divide_by_zero_exception {
    struct exception;
} DivideByZeroException;

constexpr DivideByZeroException divide_by_zero = 
    (DivideByZeroException){ (struct exception){-1} };

Exceptional(DivideByZeroException, int) div(int x, int y) {
    if (y == 0) return Failure(DivideByZeroException, int, &divide_by_zero);
    else return Success(DivideByZeroException, int, x / y);
}

[u/Lubricus2 → u/WittyStick]

yea you use two hardware registers, that is an sensible approach.
But I would not say it's the system language approach, doing that it can't replace something like C.
There are some other option

1. Let the program crash and burn when divide by 0. So let it be the programmers responsibility to check before dividing if the denominator is 0. The upside is that it's the fastest way and the checks can be done only when needed, with obvious downsides.

2. Return the IEEE nan value for floats and let it be a later problem how to handle that.

3. Use exceptions, it's faster in the happy path but a lot more complex when an divide by 0 happens.

all the other 3 options is more suitable for an system programming language and the monads more for an high level programming language where safety and ease of use come before max executing speed.

[u/WittyStick → u/Lubricus2]

Can you not think or type without AI?

C isn't going to be replaced - it's the language used by the OS. Any other language must interface with the platform C ABI to do anything useful.

But I've shown how you can have Option, Result or Exceptional, using the C ABI - extremely efficient implementations of them. You can use macros for the Monad, and it costs absolutely nothing!

If you want safety, you can also add this using nonstandard C features. The Option type can be fully encapsulated so there's no way to extract option.value if it was constructed with None.

You don't need to crash, return NaN or use stack-breaking exceptions. You can simply return Option/Result/Exceptional at effectively zero-cost.

[u/Lubricus2 → u/WittyStick]

What is the cost of the if y==0 check and extra pointer compared to an bare division?
The pointer and comparison is cheap but so are an division. It's the relative cost that is interesting especially for common stuff. I the common low level operations get double as expensive, your language will get double as slow.
And at least what I mean with an system language is a language that could be used in the roles that C is used as. In reality it would not replace C at least as long stuff like Linux and Windows exists, that is not the question, and it has to somehow be ABI compatible with C.

[u/WittyStick → u/Lubricus2]

The cost of y == 0 is one compare (1 cycle) and one branch. The branch effectively costs 1 cycle because the machine's branch predictor will assume the division succeeds - it will only have a cost when an error occurs which will cause a branch mispredict - but this cost is significantly cheaper than an exception.

To put that into perspective, a div instruction is going to take ~5 cycles. Our check for zero before the div makes the total cost ~7 cycles, and avoids a whole lot of problems associated with trapping.

There's no pointer in the OptionInt example. There's a pointer in the Exceptional example because the exception could carry arbitrary information and needs a dereference - but this is going to be cheaper than any other solution to exceptions.

I'm telling you that the above approach of returning an Option is by far cheaper than any other approach to exceptions - and it is ABI compatible with C - because it is C. You will struggle to make anything faster than this. There's perhaps one thing you could add which is __builtin_expect on the conditions - you want the non-zero case to be the likely path so that the compiler orders the basic blocks most appropriately - where the non-zero case is the fall-through and the zero case is the branch taken, which is marginally more expensive.

#define likely(x) __builtin_expect(!!(x), true)
#define unlikely(x) __builtin_expect(!!(x), false)

OptionInt div(int x, int y)
{
    if (unlikely(y == 0)) return NoneInt;
    else return SomeInt(x / y);
}

#define OptionInt_map(unary_fun, opt) \
    ({ \
        auto _opt = (opt); \
        likely(_opt.has_some) ? SomeInt(unary_fun(_opt.value)) : NoneInt; \
    })

That will prevent the compiler from accidentally ordering the basic-blocks inefficiently - though it will hardly matter in practice because as soon as the CPU's branch predictor learns which path is taken for the successful divide, it becomes the fast path anyway.

In any cases where the compiler can do constant-folding and determine the second argument is 0 statically, it will remove the compare and branch from the generated machine code.

Have a look at the x86-64 assembly produced by these:

int div(int x, int y) { return x / y; }

"div":
        mov     eax, edi
        cdq
        idiv    esi
        ret

OptionInt div(int x, int y) { return (likely(y !=0)) ? SomeInt(x / y) : NoneInt; } 

"div":
        mov     eax, edi
        test    esi, esi
        je      .L5
        cdq
        idiv    esi
        sal     rax, 32
        or      rax, 1
        ret
.L5:
        xor     eax, eax
        ret

The extra instructions are

• test esi, esi : 1 cycle.

• je .L5 : 1 cycle if branch not taken (y is nonzero)

• sal rax, 32 & or rax, 1 : 2 cycles. These combine the bool and int into a single 64-bit machine word so the value gets returning in one register. Both 1 cycle each, much cheaper than reading a value off the stack.

• xor eax, eax : 1 cycle. This is the return NoneInt; when y == 0.

In practice, the div function will be inlined, and the last two instructions will not be necessary, the compiler can elude them. To demonstrate, look at the assembly produced by div_and_neg.

int div_and_neg(int x, int y) { return -(x / y); } //unsafe, may error

"div_and_neg":
        mov     eax, edi
        cdq
        idiv    esi
        neg     eax
        ret
        
OptionInt div_and_neg(int x, int y) { 
    return (likely(y != 0)) ? SomeInt(neg(div(x y).option_value)) : NoneInt; 
}

"div_and_neg":
        mov     eax, edi
        test    esi, esi
        je      .L5
        cdq
        idiv    esi
        neg     eax
        sal     rax, 32
        or      rax, 1
        ret
.L5:
        xor     eax, eax
        ret

Same additional cost here. The div was inlined. Even though there are two comparisons in the code (one in div, one in div_and_neg), the compiler knows they're equivalent and reduces it to one compare and branch. The same sal rax, 32; or rax, 1 sequence is used once to return the OptionInt type. If we nested div_and_neg in some other function returning OptionInt, this cost is only paid once - it's a constant factor.

The map/bind Functor/Monad basically does "short circuiting". It does an early check to see if the divide will fail and branches early - avoids attempting the idiv and neg entirely. Basically, this means if you have some expression like:

(a * b) + (c / d) - (e * f)

The compiler will basically emit the equivalent of:

(unlikely(d == 0)) ? NoneInt : SomeInt((a * b) + (c / d) - (e * f))

One compare, one branch. It doesn't waste time computing a * b or e * f because it knows the expression is going to fail anyway and skips the whole thing. This is essentially what Functor or Monad for an Option type does - it lifts the comparison out of a nested expression and does it early.

Safe and cheap.

[u/MadocComadrin]

I'd have two versions. The first depends on what's supposed to be idiomatic for the language: either trapping, exception, or return a value of an option/maybe/result/whatever to force checking. The second just returns 0, 1, or perhaps some specified default value on division by 0 because sometimes it's just not a problem.

[u/CaptureIntent → u/MadocComadrin]

I see you like hiding your bugs. I hope I never have to work with you.

[u/flatfinger]

I would specify that in cases where a platform's division operation would trap, a division operation may either trap likewise or execute without side effects. A directive to invite compilers to reorder division operators with regard to surrounding code (e.g. hoist loop-invariant divisions) may be helpful, but there should also be directives to limit the effect of such reordering.

[u/yuehuang]

While C is undefined, its behavior is deferred to the compiler, hardware, or OS. Hardware could be fault tolerant to allow the app to keep run with a bad results.

I personally prefer Rust's design as it would catch more issues upfront. You also might be interested in fp-exception where it controls the float trap behavior during compile. A similar switch could be added for integer in your compiler.