The bug only occurs for x/y when both y == -1 AND x == intN::MIN, right?
Could the impact on GPUs be smaller if it were testing for x == intN::MIN instead? Can GPUs skip over instructions if they're masked for all threads in a workgroup?
The reasoning is that division by zero is intended to be a stop-the-program error, whereas overflow in division is intended to be well-defined.
Interesting. I'm curious what this is based on. Every in-the-wild instance I've seen of division by zero in C has been a case where returning 0 or 1 would have been fine. The vast majority of cases have been a result of computers getting faster: they've divided something by some recorded snapshot of measured time and now the time window has become less than the quantum size and so rounded to 0.
In contrast, overflow in division has been the cause of a few security vulnerabilities.
The motivation is basically just that this seems conventional. Integer division by zero is explosive in most languages, but all other integer operations function by overflow (except a few similar cases like power with a negative exponent). The work discussed in the post is orthogonal to what the best semantics might be for integer operations, and personally I'm not sure. Making everything defined (with x/0=0 etc) is certainly compelling.
The motivation is basically just that this seems conventional
This is largely an artefact of implementation substrates.
Integer division by zero is explosive in most languages
This is due to the underlying instructions. For example, x86 will deliver an exception on division by zero. This is fun in most *NIX systems because they will map it to SIGFPE and whether you get a trap or an unspecified result depends on the floating-point environment. But that's not because it's a good behaviour, it's because C decided that they wanted to map the / operator to a single instruction on any platform that had a divide instruction. And then other languages wanted to be 'as fast as C', so picked up this behaviour.
Pony, for example, defines X/0 = 0 and that has very little cost in modern systems.
but all other integer operations function by overflow (except a few similar cases like power with a negative exponent)
This is for the same reason. C says signed overflow is undefined because C was standardised when some targets used explicit sign bits, some used 1s complement, some used 2s complement. So overflow could result in different things between different systems.
The optimisation question grew out and it's not completely clear what the benefit is because a bunch of scalar-evolution optimisations can reason about the fact that loops induction variables won't overflow and so don't need to handle the case.
In hindsight, this was almost certainly the wrong choice. Most integer uses don't want to overflow and integer overflow can lead to security problems. The canonical one is you do malloc(size * count) and count is attacker-influenced. If you just get a huge integer, malloc will fail. If you get overflow, you get a smaller object than you expected. Lisp and Smalltalk default to arbitrary-precision integers and use word-sized integers as an optimisation and then promote to a big-integer representation on the heap. C can't do that because it's used in a bunch of places where heap allocation would be impossible.
Futhark also runs in places where heap allocation is impossible, and while overflow can be detected dynamically (as with division by zero), it has a significant cost, so I'm reluctant to do so. I think the most principled solutions are to fully define all integer arithmetic, or to perform dynamic checks on all questionable behaviour (like overflow). At the moment Futhark is in an awkward middle position, like many languages, really.
Futhark is memory-safe, so overflow will not result in C-style memory errors, but of course it can result in logic bugs that can manifest themselves in various ways for both malicious and innocent input.
while overflow can be detected dynamically (as with division by zero), it has a significant cost
You might be surprised. I did some benchmarking of this about 20 years ago and it was basically in the noise. Most ISAs had flag-setting operations and statically predicted branch-on-carry as not-taken. We did prototypes for saturating arithmetic in C and the performance overhead was negligible. I'm not sure how this works with GPUs though, it's been 15 years since I poked a GPU ISA and everything I know is probably horribly out of date.
The problem on the GPU is not at the ISA level (although I haven't checked), but the ceremony around having to suddenly abort computation. This is not something vector processors are good at. I did some work in the area some years ago to do, on bounds checking which has the same problem: https://futhark-lang.org/blog/2020-07-13-bounds-checking.html
The overhead was about 4% across the entire Futhark benchmark suite, but it is worth remembering that bounds checks are relatively rare (because most indexing is statically safe in an array language), whereas integer arithmetic somewhat more prevalent. I am guesstimating here, but I think the overhead of fully checked integer arithmetic would be untenable for a language targeting Futhark's niche.
dtgriscom | a day ago
At last, someone who appreciates my work.
olliej | a day ago
I liked the comment as well :)
maxholl | 9 hours ago
The bug only occurs for x/y when both y == -1 AND x == intN::MIN, right? Could the impact on GPUs be smaller if it were testing for x == intN::MIN instead? Can GPUs skip over instructions if they're masked for all threads in a workgroup?
david_chisnall | 13 hours ago
The 'correct' version doesn't appear to check for division by zero, which is also UB in C.
athas | 12 hours ago
Indeed, but this is checked using a different mechanism: https://futhark-lang.org/blog/2023-03-17-on-nontermination.html
The reasoning is that division by zero is intended to be a stop-the-program error, whereas overflow in division is intended to be well-defined.
david_chisnall | 12 hours ago
Interesting. I'm curious what this is based on. Every in-the-wild instance I've seen of division by zero in C has been a case where returning 0 or 1 would have been fine. The vast majority of cases have been a result of computers getting faster: they've divided something by some recorded snapshot of measured time and now the time window has become less than the quantum size and so rounded to 0.
In contrast, overflow in division has been the cause of a few security vulnerabilities.
athas | 12 hours ago
The motivation is basically just that this seems conventional. Integer division by zero is explosive in most languages, but all other integer operations function by overflow (except a few similar cases like power with a negative exponent). The work discussed in the post is orthogonal to what the best semantics might be for integer operations, and personally I'm not sure. Making everything defined (with x/0=0 etc) is certainly compelling.
david_chisnall | 11 hours ago
This is largely an artefact of implementation substrates.
This is due to the underlying instructions. For example, x86 will deliver an exception on division by zero. This is fun in most *NIX systems because they will map it to SIGFPE and whether you get a trap or an unspecified result depends on the floating-point environment. But that's not because it's a good behaviour, it's because C decided that they wanted to map the
/operator to a single instruction on any platform that had a divide instruction. And then other languages wanted to be 'as fast as C', so picked up this behaviour.Pony, for example, defines
X/0 = 0and that has very little cost in modern systems.This is for the same reason. C says signed overflow is undefined because C was standardised when some targets used explicit sign bits, some used 1s complement, some used 2s complement. So overflow could result in different things between different systems.
The optimisation question grew out and it's not completely clear what the benefit is because a bunch of scalar-evolution optimisations can reason about the fact that loops induction variables won't overflow and so don't need to handle the case.
In hindsight, this was almost certainly the wrong choice. Most integer uses don't want to overflow and integer overflow can lead to security problems. The canonical one is you do
malloc(size * count)andcountis attacker-influenced. If you just get a huge integer,mallocwill fail. If you get overflow, you get a smaller object than you expected. Lisp and Smalltalk default to arbitrary-precision integers and use word-sized integers as an optimisation and then promote to a big-integer representation on the heap. C can't do that because it's used in a bunch of places where heap allocation would be impossible.athas | 10 hours ago
Futhark also runs in places where heap allocation is impossible, and while overflow can be detected dynamically (as with division by zero), it has a significant cost, so I'm reluctant to do so. I think the most principled solutions are to fully define all integer arithmetic, or to perform dynamic checks on all questionable behaviour (like overflow). At the moment Futhark is in an awkward middle position, like many languages, really.
Futhark is memory-safe, so overflow will not result in C-style memory errors, but of course it can result in logic bugs that can manifest themselves in various ways for both malicious and innocent input.
david_chisnall | 8 hours ago
You might be surprised. I did some benchmarking of this about 20 years ago and it was basically in the noise. Most ISAs had flag-setting operations and statically predicted branch-on-carry as not-taken. We did prototypes for saturating arithmetic in C and the performance overhead was negligible. I'm not sure how this works with GPUs though, it's been 15 years since I poked a GPU ISA and everything I know is probably horribly out of date.
athas | 8 hours ago
The problem on the GPU is not at the ISA level (although I haven't checked), but the ceremony around having to suddenly abort computation. This is not something vector processors are good at. I did some work in the area some years ago to do, on bounds checking which has the same problem: https://futhark-lang.org/blog/2020-07-13-bounds-checking.html
The overhead was about 4% across the entire Futhark benchmark suite, but it is worth remembering that bounds checks are relatively rare (because most indexing is statically safe in an array language), whereas integer arithmetic somewhat more prevalent. I am guesstimating here, but I think the overhead of fully checked integer arithmetic would be untenable for a language targeting Futhark's niche.
david_chisnall | 8 hours ago
That's an orthogonal issue. There are a bunch of choices for overflow:
Saturating arithmetic is often a nice compromise for performance and usability.