Almost all modern machines use two’s\ncomplement to\nrepresent integers. This representation is asymmetric, in the sense that the\nmost negative number has no corresponding positive number. For example, with\nsigned 8-bit numbers, the most negative number is -128, whilst the most\npositive number is 127. This quirk shows up in various cases, but for the\npurpose of this post, I am concerned with signed integer division, where x/-1\nmathematically should produce -x, but in the case where x is the most\nnegative number, that is not possible. For 32-bit integers, which I arbitrarily\ndecide are the most common, this means that one out of every 2⁶⁴ possible inputs\nis impossible to represent correctly - leading to the somewhat clickbaity title\nof this post, and some recently fixed troubles in the Futhark compiler. In this\npost I will explain what the actual problem is for a language implementation,\nhow we fix it, and what the performance cost looks like. The main audience of\nthis post is other language implementers, but I think the concepts involved are\nsimple enough that anyone curious about low level issues can follow along.
The Futhark compiler has multiple backends, but the most important ones work by\ngenerating C code. This has many practical advantages:
\nIt is easy to debug the generated code because it is easy to read and modify
by hand.
Most systems have a C compiler (or easy access to one), meaning Futhark has
fewer dependencies, is portable, and doesn’t need to bundle native code\n generators.
Many languages can interoperate with C, so by exposing Futhark as a C API,
those languages can also call\n Futhark.
That said, there are also disadvantages:
\nSome code patterns are hard to express (or express efficiently) in C. This is
mainly the case for advanced language features such as coroutines, tail\n calls, or garbage collection. Fortunately Futhark is pretty boring from a\n semantic perspective, so this\n does not affect us too much.
It is very easy to accidentally generate C code that is subtly wrong. This
does unfortunately keep pestering us.
C is of course renowned as a very safe and easy-to-use language, because C\nprogrammers never make coding mistakes. The few times they do make mistakes, it\nis often due to mishandling of pointers or array sizes, leading to buffer\noverflows, heap smashing, etc. These are actually not the main problem with\ngenerating C from Futhark, as Futhark itself is memory-safe, and systematically\ninserting in bounds checks in generated code is easy (although a little more\ninteresting in GPU code).
\nNo, the main problem we’ve had is actually undefined behaviour. As is by now\nwell-known, C specifies various events as explicitly undefined, meaning not only\nthat a C compiler can assume it will never occur, but also that no particular\nresult is guaranteed should a program perform one of the undefined operations.\nSome causes of undefined behaviour are obvious and easy to avoid: reading arrays\nout-of-bounds, using freed memory, etc. But C has a long list of more obscure\ncases. My favourite example is that in C99, it is undefined behaviour if a\nsource code file does not end with a final newline character. Yet we have\nhonestly not spent that much time dealing with that particular issue in Futhark.
\nNo, the main problem, and now we are finally returning to the premise in the\npost, is that signed integer overflow is undefined behaviour in C. This is\nparticularly insidious since most programmers have a mental model of fixed-size\ninteger arithmetic where overflow is a natural event, and so does the actual\nmachines we use, but a C compiler may assume it never happens. The reason behind\nthis specification is so the C compiler can optimise based on useful properties\nsuch as x+1>x, which are not true in the presence of overflow, but the\nmotivation does not actually matter to us. In a language like Futhark, where\ninteger overflow is defined behaviour (it wraps around), this creates a very\nunfortunate mismatch between what we want to do, and what we can express in our\ntarget language.
Fortunately, C is merciful enough to specify that for unsigned numbers,\noverflow is well-defined, and behaves just as you would expect (on a\ntwo’s-complement machine, anyway). For this reason, Futhark’s C code generation\nactually represents all integer types using unsigned C types, (so i64 becomes\nuint64_t), and then performs the arithmetic on unsigned types. This works due\nto the nice property of two’s complement representation that most arithmetic\noperations are done exactly the same, at the bit level, as for unsigned\nintegers. One exception is comparison operators, in which we cast to the signed\ntype (e.g. int64_t) before performing the comparison. Such conversions are\nfree, since they do not need to change the bit representation of the number, but\nonly affect what instructions the C compiler emits for e.g. a <= operation.
Another operator where sign matters is division. If we do x/-1, then it is\nquite important whether we are dividing with a small negative number, or with\nthe number that arises if we interpret the two’s complement bit pattern for -1\nas an unsigned integer. This means that for signed integer division, Futhark\ngenerates a signed C division. This means that if we do x/-1 where x is the\nmost negative number, we are stuck with the issue described in the post opener -\nthe correct result (-x) cannot be represented as a signed integer, so this is\na signed integer overflow, and that is undefined behaviour in C.
Futhark is a principled language, and therefore producing undefined behaviour is\nunacceptable. (I realise the hypocrisy of this puritan declaration whilst\nleaving in the bug for ten years.) Further, on x86 this kind of division will\nactually signal a CPU exception, crashing the program, so this is not merely a\nviolation of the sanctity of the C specification. Fixing it in principle is\neasy. This is the definition of 32-bit signed division in the Futhark runtime\nsystem:
\nint32_t squot32(int32_t x, int32_t y) {\n return x / y;\n}And this is the version that avoids the 0.000000000000000000542% undefined cases:
\nint32_t squot32(int32_t x, int32_t y) {\n return y == -1 ? (int32_t)(0 - (uint32_t)x) : x / y;\n}This function simply checks whether the divisor is -1, and if so does the\nnegation with unsigned (well-defined) arithmetic. The cost is a branch on every\nsingle division. The behaviour is still implementation-defined, but produces\nthe right results on the machines we care about.
(Why quot instead of div? Futhark actually has two division operators -\none that rounds sensibly towards negative infinity, and one that rounds towards\nzero like C. The function above is the one that follows C’s behaviour because it\nis less code, but the issue is the same either way.)
Correctness is not really a thing we can compromise on, but in principle it is\nfrustrating that every integer division needs an additional branch just to\nhandle a single special case that may never actually happen, as it is highly\nunlikely that a program’s correctness depends on wraparound for signed integer\ndivision at the ends of the numeric scale. But apart from the principal\nfrustration, what is the actual overhead?
\nMeasured on the Futhark benchmark\nsuite on GPU, I was unable to\nmeasure an impact. This is likely because signed integer divisions are\nrelatively rare, and even when they do occur, they likely occur due to index\narithmetic, where the resulting memory loads have so much latency that they\neasily hide the cost of\ndoing the divisions.
\nBut what if we try to construct a contrived program where the bottleneck is\nsigned division throughput? That would demonstrate something close to worst-case\noverhead of adding the branch. Behold, divisions.fut:
-- ==\n-- random input { 1000000 [1000]i32 [1000]i32 }\n\nentry main [n] (k: i32) (xs: [n]i32) (ys: [n]i32) : [n]i32 =\n map2 (\\x y ->\n loop z = x\n for _i < k do\n #[unsafe]\n z // y)\n xs\n ysThe program accepts a number k and two arrays of integers. For each\ncorresponding pair x and y, it k times divides x by y, using // to\ntarget the squot32 function, and using #[unsafe] to remove division-by-zero\nchecks.
For most values of k, repeated division quickly produces zero, but the\ncompiler cannot assume this, so it will have to actually perform the divisions.\nYou may reasonably argue that the program is not purely division bound, as the\nbookkeeping around the loop also involves costly things such as adding and\ncomparing integers, but a program that contains a very long unrolled sequence\nof divisions stretches my credulity too far.
Using the handy futhark\nbench tool, we can then\nmeasure the impact using the compiler with a fixed implementation of squot32\n(part of this pull request).\nFirst on sequential code, using the c backend:
$ futhark-old-and-busted bench divisions.fut\n...\n\ndivisions.fut (no tuning file):\n100000i32 [10000]i32 [10000]i32: 3390148μs (95% CI: [ 3387613.7, 3396498.1])\n\n$ futhark-new-hotness bench divisions.fut\n...\n\ndivisions.fut (no tuning file):\n100000i32 [10000]i32 [10000]i32: 3389215μs (95% CI: [ 3387626.2, 3391036.4])There is no measurable difference, which is not a surprise on a modern\nspeculatively executing CPU for a program with an easily predicted branch.
\nBut what about GPUs? After all, “GPUs are bad at branching” is a common motto by\nthose of my students who like to replace an if with ten lines of dense\nbranchfree code. Let’s try the experiment again with Futhark’s cuda backend:
$ futhark-old-and-busted bench --backend=cuda divisions.fut\n...\n\ndivisions.fut (no tuning file):\n100000i32 [10000]i32 [10000]i32: 5548μs (95% CI: [ 5546.4, 5552.2])\n\n$ futhark-new-hotness bench --backend=cuda divisions.fut\n...\n\ndivisions.fut (no tuning file):\n100000i32 [10000]i32 [10000]i32: 12592μs (95% CI: [ 12563.5, 12622.1])Well then! This really is a major difference. Much more than I expected when I\nbegan this work, actually. Reading the generated PTX (CUDA machine code), the\nold version is partially unrolled into four consecutive div.s32 instructions\nin a single basic block, whilst the fixed compiler still triggers unrolling, but\nwith many branches between the divisions.
I observed a similar result on an AMD GPU with the hip backend, although the\nimpact was slightly less there.
The cost of fixing those 0.000000000000000000542% of divisions is real and\nunfortunate, and I would certainly like to have a cheaper fix. Having undefined\nbehaviour in the generated code is of course not acceptable, so we will have to\nlive with this for now. On non-contrived benchmarks, it seems there is\nessentially no impact. For programmers unwilling to pay this cost, you can\nalways stick to unsigned divisions, if you know that you will never have\nnegative numbers.
\nThis is the last instance of undefined behaviour in Futhark’s generated C code\nthat I remember. There is however at least one instance of\nimplementation-defined behaviour, namely in the code generation for\nbit-shifting integers by more bits than their size, but I have yet to gather the\ncourage to fix it.
","headings":[{"level":3,"text":"The C issue","id":"the-c-issue"},{"level":3,"text":"The cost","id":"the-cost"},{"level":3,"text":"Conclusions","id":"conclusions"}]}}