Hacker News Reader

> The cost of doing it in software is just a highly predictable (not taken) branch after every integer arithmetic operation that the compiler can't prove stays within bounds.

While I agree with you that hardware overflow traps are a bad idea, I think the article's author is referring more to the general overhead of a software BIGNUM implementation. Specifically with his JavaScript example, I think it's very plausible that using integers instead of IEEE754 would incur a 10% overhead if you were throwing lots of big enough numbers around.

What the author really wants is a hardware BIGNUM implementation, not overflow trapping. I just don't think he really thought it through.

His contention that simply checking for overflow in C or C++ incurs a 5% overhead is unquestionably false though. Typically one would check for integer overflow in C like this:

  unsigned int do_addition(unsigned int a, unsigned int b)
  {
	unsigned int tmp;

	tmp = a;
	a += b;
	if (a < tmp)
		asm volatile ("nop;" ::); /* Handle it here */

	return a;
  }

Any decent compiler will do the right thing (GCC with -Os):

  0000000000000000 <do_addition>:
     0:	89 f0                	mov    %esi,%eax
     2:	01 f8                	add    %edi,%eax
     4:	73 01                	jae    7 <do_addition+0x7>
     6:	90                   	nop
     7:	c3                   	retq

I think rwallace is absolutely right in saying the overhead of such a check would be very close to zero in the non-overflow case.

Note, in case someone blindly takes this as advice: This method of expressing it in C doesn't work for multiplication (you could wrap more than once).

I'm not sure you can express an overflow check for multiplication purely in portable C (without library or intrinsic support), actually. Well, I guess you could break the multiplication into checked additions manually, but that's probably not a great idea.

In x86 assembly almost all multiplication operations return a result double the width of the inputs: http://www.aldeid.com/wiki/X86-assembly/Instructions/mul

Checking for overflow is just a matter of testing if the high-order bits are zero.

Yep, in assembly it's usually no question possible. That's why I specified portable C.

C has some interesting gaps for something that's long been described as a macro for assembly. A rotate operator would also be nice.

The correct thing to do is also to check the carry and overflow flags after (I)MUL, which does the right thing even when only the lower bits of the multiplication are saved.

Here's an example where there is overflow, but your suggestion would not catch it:

    mov eax, 0x7fffffff
    mov ecx, 2
    imul ecx ; edx:eax = eax * ecx
    ; edx = 0
    ; eax = 0xfffffffe
    ; overflow flag = 1

There is signed overflow here, but testing edx (the higher word of the result) would not catch it.

Yes. I decided not to mention IMUL to keep the post simple.

There are also issues with detecting overflow of SSE multiplies (signed and unsigned).

> Note, in case someone blindly takes this as advice: This method of expressing it in C doesn't work for multiplication (you could wrap more than once).

Yeah, you're absolutely right.

> I'm not sure you can express an overflow check for multiplication purely in portable C (without library or intrinsic support), actually. Well, I guess you could break the multiplication into checked additions manually, but that's probably not a great idea.

I've never tried to implement this, but couldn't you look at the position of the most significant bit in the multiplicands to guess if the multiply will overflow? You'd have to be okay with false positives I suppose? Naively it would be slow, but if you have a hardware CLZ instruction it could be pretty fast.

I did find this on SO:

  x = a * b;
  if (a != 0 && x / a != b) {
    // overflow handling
  }

That makes sense, but of course it would be HORRENDOUSLY expensive.

If you're willing to not be non-portable, you could just do expanding multiplies and check the high word:

  struct exmulres {
        unsigned long hi;
        unsigned long lo;
  };

  static inline __attribute__((always_inline)) struct exmulres do_one_expanding_multiply(unsigned long a, unsigned long b)
  {
        struct exmulres res;
        #if defined(__x86_64__)
                asm ("movq %0,%%rax; mulq %1; movq %%rdx,%1; movq %%rax,%0"
                : "=r" (res.lo), "=r" (res.hi) : "0" (a), "1" (b) : "%rax","%rdx");
        #elif defined(__i386__)
                asm ("movl %0,%%eax; mull %1; movl %%edx,%1; movl %%eax,%0"
                : "=r" (res.lo), "=r" (res.hi) : "0" (a), "1" (b) : "%eax","%edx");
        #elif defined(__arm__)
                asm ("umull %0,%1,%2,%3"
                : "=r" (res.lo), "=r" (res.hi) : "r" (a), "r" (b) :);
        #else
                #error "No expanding multiply assembly has been written for your architecture"
        #endif
        return res;
  }

It probably wouldn't be very difficult to fill that out for all the CPU architectures Linux supports, which would cover all your bases unless you're doing super embedded stuff.

EDIT: Typo

Yeah that div check works I guess, but as you say is horribly expensive.

For the latter it looks like at least on recent versions of gcc, you can do something like (WARNING: Just a vague proof of concept, please don't use it. It might kill kittens):

    uint64_t func(uint64_t a, uint64_t b)
    {
        unsigned __int128 res = (unsigned __int128)a * (unsigned __int128)b;
        if (res >> 64) {
            asm volatile ("nop;" ::); /* handle here */
        }
        return (uint64_t)res;
    }

Which compiles to this in gcc -Os and -O3:

    0:	48 89 f8             	mov    %rdi,%rax
    3:	48 f7 e6             	mul    %rsi
    6:	48 85 d2             	test   %rdx,%rdx
    9:	74 01                	je     c <func+0xc>
    b:	90                   	nop
    c:	f3 c3                	repz retq

Which I'm pretty sure could be optimized further by using the overflow flag, but the compiler doesn't seem to want to ignore the upper word.

edit: and it probably suffers the same problem as described here: https://news.ycombinator.com/item?id=7848771 -- and also probably has general issues with signedness that would need to be further checked.

edit2: changed it to uints to simplify and avoid a whole class of problem. I still don't think you should go use this, though.

(inspiration from SO: http://stackoverflow.com/a/13187798)

Looking at the GCC source [1] starting at line 150 this is almost what GCC actually does - perform the multiplication with twice the operand size and then check by shifting right but GCC compares the result of two shift operations differing by one in the shift amount.

[1] https://github.com/mirrors/gcc/blob/master/libgcc/libgcc2.c

For future reference, you can link to a specific line in github with #LNNN. Which you can get by clicking on the line number. Pretty handy.

https://github.com/mirrors/gcc/blob/master/libgcc/libgcc2.c#...

He also picked one of the most trivial cases - unsigned addition. Signed data, especially signed multiplication, requires a lot more steps.

I'm working on a set of numerical problems in C now that involve checking for integer overflow. The best way of doing software overflow checks depends on the larger scope of the problem. You can knit your checks into various places in your code in ways that avoid unnecessary duplication of computational effort. However, that is a lot of work and has the potential for hidden programmer introduced errors.

The real problem is that languages like C simply don't allow you to take advantage of hardware which already exists in the CPU without writing in-line assembler. A standard set of "checked" math macros which handled the portability issues would probably satisfy most C applications.

Edit: For addition, subtraction, and multiplication, you just take one operand, calculate the largest possible second operand for that data type which won't overflow, and check that the actual second operand doesn't exceed it (remembering to take signs into account). For division and modulus, check for division by zero. For multiplication, division, modulus, negation, and absolute value of signed values, check that you are not negating the maximum negative integer, as integer ranges are not symmetrical (e.g. one byte is -128 to +127).

If you are looping over arrays and have multiple checks for different cases (e.g. negative, positive, etc.), then you can have different loops for different cases and so avoid redundant checks for that data. I'm working on this sort of application, so the above works out best for that. If you're doing something a bit different, then different algorithms may make sense. Unfortunately, there's not universal one-size-fits-all solution to this problem in software.

It's surprising there aren't at least intrinsics for some of these things in GCC/clang. At least as far as I can tell.

http://clang.llvm.org/docs/LanguageExtensions.html#builtin-f..., the search for "Checked Arithmetic Builtins"

Nice! Thanks for the link, I admit I didn't do as much looking on the clang side as gcc. Doesn't look like these exist in gcc though, unfortunately. :/

> For addition, subtraction, and multiplication, you just take one operand, calculate the largest possible second operand for that data type which won't overflow, and check that the actual second operand doesn't exceed it

Sure, but that calculation is CPU-dependent, since it depends on how the underlying hardware represents signed integers. By definition, it is impossible to portably check for signed integer overflow in C, as I'm sure you know.

I implemented a simplistic BIGNUM library in C once (that's where I pulled that expanding multiply code in the other comment from). The only truly portable way to do that is to make your bignums sign-magnitude and use exclusively unsigned arithmetic on them. That's what I was envisioning in my original point about performance degradation due to overflow checking.

Realistically of course, most CPU's these days are twos-complement, and you can make signed overflow defined by compiling with "-fwrapv", which I would guess is what you're doing.

Yes I'm assuming two's complement, but there's not a lot of hardware around these days that isn't two's complement. I'm writing a library for something that already assumes two's complement while doing other things.

If the code had to be portable to one's complement hardware, then I would create special cases for that type of hardware. Laying my hands on such hardware for testing would be the big problem, and if you haven't tested it, then how do you know that it works?

As for "-fwrapv", it's not portable either, and I need to cover both signed and unsigned math. It's also not compatible with what I need to link to (I've gone down this road already). I also need to cover the largest native word sizes, so the trick of using a larger word size won't work for me.

I'm only dealing with arrays of numbers though, so I can often amortize the checking calculations over many array elements instead of doing them each time. This is an example of knitting the checks into the overall algorithm instead of using a generic approach.

As things stand, there's currently no universal ones-size-fits-all answer to this problem in most languages.

I do like how Python has handled this - integers are infinitely expandable and simply can't overflow. This comes at the expense of performance though. What this type of solution needs is an option for unchecked native arithmetic for cases where you need maximum speed.

> As for "-fwrapv" [...] It's also not compatible with what I need to link to (I've gone down this road already)

I'm actually really curious: exactly what issues did you run into with this? Intuitively I wouldn't think it would be a problem.

A smarter way is to split both numbers to multiply into two halves, and pretend to do two-word arithmetic on a machine with words half the size.

In decimal, that means that you compute the product of two-digit numbers using single-digit multiplications and shifts (= multiplications by 10):

  23 x 67
  = (20+3) x (60+7)
  = (2x3) x 100 + (2x6) x 10 + (3x7) x 10 + 3x7

There are better checks. I'm generally not a fan of Microsoft, but the SafeInt library ( https://safeint.codeplex.com/ ) does those kinds of checks in sofware.

I don't remember where I read it, but regarding multiplication: if you multiply two N-bit numbers together, the result will always fit in a 2N-bit number. For instance, the product of two 16 bit numbers will fit in 32 bits, the product of two 32 bit numbers will fit in 64 bits, etc. You can assign the product to an integer able to hold the larger size and then check if it would also fit in an integer of the smaller size.

There probably is close to zero overhead in a small benchmark. Hardware branch prediction is indeed good. However, it's a finite resource. In a large application, lots of needless branches everywhere translates into fewer branch prediction resources available for the branches that matter, which means more mispredictions. Also, they take up icache, itlb, etc. It's not at all obvious that the overhead would be close to zero in context.

Would it be possible to mark the JO instruction (jump-if-overflow) as unlikely, so that the CPU would always predict the branch to not be taken, without consuming one branch prediction slot?

> so that the CPU would always predict the branch to not be taken

AFAIK there isn't any notion of likely/unlikely in object code on most CPU architectures. I'm only really familiar with x86 and ARM though.

__builtin_expect() in GCC (the "likely()" and "unlikely()" macros in the Linux kernel use this) can do a lot of things to optimize branches, like prefetch instructions and decide whether or not the jump should be the usually taken or usually not taken side, but it can't actually emit instructions that directly tell the CPU "always predict this" AFAIK.

> It's not at all obvious that the overhead would be close to zero in context.

That's a fair point, although I think using a single function for all your checked addition like the one above would go a long way towards mitigating the resource waste you mention.

Maybe that's a naive assumption on my part: I suppose you could construct a branch predictor that maintains state based on the function call chain as opposed simply using the address of the branch... but that seems like it would be prohibitively complex.

> The cost of doing it in software is just a highly predictable (not taken) branch after every integer arithmetic operation that the compiler can't prove stays within bounds. The article presents no data on this cost.

The article does mention a 5-10% cost on JavaScript VMs, as one datapoint. And as another, that languages like Rust choose to allow overflow to avoid the overhead, despite preferring the security of not having silent overflows (implying they measured a slowdown they find unacceptable).

Here's another point, how much clockspeed suffers from adding this feature? What about instruction latencies? Does it increase the pipeline length for bigger branch missprediction penalty? Does it interfere with microarchitecture optimizations we are using or could be using? All these are performance questions that may result from adding this instruction. There is reason why RISC eliminated most of mixing control flow with arithmetic.

As for his numbers on the performance penalty of doing it in software it surely depends on micro-architecture. All intel x86 processors before HASWELL did only ONE branch per cycle, then in haswell they increased that to two. So the cost of doing it in software should of went down recently. And Intel is adding new instructions to speed up arbitrary precision arithmetics in broadwell so they probably have already thought about this and decided its not worth the cost in hardware.

> I have none to hand either, but I'm going to predict that on a modern CPU with typical workloads it will be small enough that it would be very hard to measure.

I write in a language that does (sort of) this (Python!), and I'd argue that I'd agree. Python gives, by default, integers that aren't bounded, so overflow doesn't happen. Of course, under the hood, it must be keeping track of all the bits of the number somehow, and determining when it can't store a section of the integer in the underlying uintxx_t; it must use some sort of overflow here, even if perhaps it's not truly overflowing. Integer objects (for those interested) are 28 bytes by default and more if they get larger; a rough test with multiplication just now seems to take ~25-50ns (compared to ~2-3ns for a int32t in C) and in my experience, most of the time, this doesn't matter.

With this flurry of new languages, I had hoped to see more of "integer" just being an integer, and fixed-sized integers being a special case. Often, I feel I really don't know what the bounds on the input will be. (Sometimes, there aren't, aside from available memory constraints.) Obviously, there will need to be code that needs to run fast and can use a more restrictive type.

Something like, `ranged_integer<0, 200>`, which I can use when I know my inputs should never exceed [0, 200], and has some well-defined behavior if I over/underflow. (Or even, configurable!) In the `ranged_integer<0, 200>` case, I'd expect the compiler/library to be able to easily optimize that into a `uint8_t`. (You could have `native::uint8_t`, which is just whatever the processor has, and you're on you're own, but it's more obvious that you're on your own.)

Eh, new instructions are added all the time. Just look at BMI - I'd be willing to bet the static power cost of adding that dwarfs what trapping arithmetic would cost. And most of those instructions are more esoteric and/or give less benefit over existing instructions than trapping arithmetic would.

Also the current branches for overflow checks might be well-predicted, but only if it uses branch prediction resources that could go to other branches. Not to mention the extra codesize and issue resources taken.

The processor is already calculating overflow with every operation. All it has to do is allow that bit to trigger a trap.

Which isn't as trivial as you are implying because it requires a feedback back trap handling parts of the core.

I agree and would add: What do you do when an integer overflow occurs? This would add additional complexity to transferring and handling this knowledge all way up to the application level.