News for hackers. Stuff that matters.
Re:The Performance Cost of Integer Overflow Checking by derefr on Wednesday December 17, 2014 @11:56PM (#8766021)
It seems to me that, despite all the flexibility people demand, they only really want (and use) exactly three integer data-types in a language:

1. machine bit-string of size 8(2^n) bits (e.g. b/w/d/q fields) with no concept of being a signed/unsigned integer, but where you can apply both signed and unsigned integer operations to it in an optimized manner. Such code will be shimmed with sets of clever shifting ops if the target architecture doesn't actually have a storage type of that width, but you have to be explicit about what you'll allow (e.g. if an integer is of type "d|2w", then it will compile fine on a 16-bit architecture (and operate using shimmed ops), but fail to compile on an 8-bit architecture.

2. unsigned integer of fixed exactly-specified bitsize, which exactly matches the semantics of a having a value on a modular-arithmetic ring. You go up, it wraps around at 2^bitsize; you go down, it wraps back. This stays true even if the code is compiled on an architecture where the exactly-specified bitsize isn't a clean processor storage-width: a 27-bit ring on a 32-bit processor is A-OK, and shims will be inserted to enforce the semantics. Shims will also be inserted if you're targeting an ISA that doesn't have an integer type with wrapping semantics (e.g. the JVM.)

3. signed arbitrary-precision integer (i.e. optimal-machine-word-size-minus-a-tag-bit with bignum promotion checks). The optimizer might convert one of these to something of type #1 if it can be very, very sure of the value range you're operating within.

#1 is for doing pointer math in unsafe regions; #2 is for implementing cryptographic primitives; #3 is for everyone else.

(There's also a variant on #1—let's call it #1A—which is a fixed-size array of #1s you can repeat signed/unsigned integer transformations over, where this will generate optimized SIMD code. This would be the "buffer" type for wire protocol packing/unpacking, and also the backing store for non-sparse matrix ADTs, bloom filters, etc.)

The only place integer overflow raising an exception would make sense, to me, are if you want some sort of hybrid type between #1 and #3: a value that pretends to be arbitrary-precision, but in fact only has a constant-size bitstring to operate within. I could see the use of this in something like Cap'n Proto, where you're keeping wire-encoded integer bitstrings (#1s from a #1A) around and pretending they're fully-functional integers (#3) for the sake of zero-copy—but do you really gain that much by not letting a data structure be recreated resized on the stack, if you're not also throwing down optimizations like intrusive lists in fixed arenas?

Re:The Performance Cost of Integer Overflow Checking by the_why_of_y on Saturday December 27, 2014 @07:50AM (#8802406)
> an ISA that doesn't have an integer type with wrapping semantics (e.g. the JVM.)

This is incorrect: the JVM has fully well-defined modulo arithmetic:

http://docs.oracle.com/javase/specs/jvms/se7/html/jvms-6.htm...

"The result is the 32 low-order bits of the true mathematical result in a sufficiently wide two's-complement format, represented as a value of type int. If overflow occurs, then the sign of the result may not be the same as the sign of the mathematical sum of the two values. Despite the fact that overflow may occur, execution of an iadd instruction never throws a run-time exception."

With this definition the JVM doesn't need distinct instructions for unsigned arithmetic since they're identical to signed arithmetic in two's complement (with some exceptions like shifting for which there are both ishr / iushr instructions).

Re:The Performance Cost of Integer Overflow Checking by nkurz on Thursday December 18, 2014 @12:38AM (#8766130)
I have a small nit about #2 that doesn't affect your main argument. Similar to the 'overflow' flag the processor automatically sets to signal signed overflow, the processor flag for 'carry' is already being set by the processor when you add or subtract unsigned numbers that overflow. There is no separate signed or unsigned addition in x86/x64 assembly --- the processor just sets the flags for both cases, and they can either be used or ignored.

This is the reason that overflow checking can be so inexpensive --- no additional checking is necessary, just a conditional branch on an existing flag. Correctly predicted branches not taken are very inexpensive, and this branch will almost always be correctly predicted. The issue is that standard C doesn't allow any direct defined way to make use of the overflow flag. Instead you have to write something awkward and hope the compiler optimizes it down for you.

Re:The Performance Cost of Integer Overflow Checking by TazeTSchnitzel on Thursday December 18, 2014 @12:56AM (#8766169)
Irritatingly, GCC lacks a "branch on overflow" intrinsic or "add and branch on overflow" intrinsic, forcing you to write inline asm to do fast overflow checking.
Re:The Performance Cost of Integer Overflow Checking by dbaupp on Thursday December 18, 2014 @01:10AM (#8766204)
GCC 5.0 has them:

> A new set of built-in functions for arithmetics with overflow checking has been added: __builtin_add_overflow, __builtin_sub_overflow and __builtin_mul_overflow and for compatibility with clang also other variants

-- https://gcc.gnu.org/gcc-5/changes.html

Re:The Performance Cost of Integer Overflow Checking by daniel02216 on Thursday December 18, 2014 @01:13AM (#8766210)
As of GCC 5, it has __builtin_add_overflow, __builtin_sub_overflow, __builtin_mul_overflow

https://gcc.gnu.org/gcc-5/changes.html

Re:The Performance Cost of Integer Overflow Checking by derefr on Thursday December 18, 2014 @01:00AM (#8766177)
Kind of makes sense, though. Since the C standard says that integer overflow is undefined, you can think of the "C abstract machine" as being built on an assumption of an underlying architecture that provides magic fixed-width-yet-arbitrary-precision integers (and/or an assumption of omniscient programmers who always know what their inputs will be and never let math happen if it would result in overflow.) Basically, you can't talk about overflow in C, or even to a C compiler, because as soon as you make the fact that overflow is happening explicit, you've stepped outside the C abstract machine.

It's like trying to talk to Haskell about explicit thunks, or Lisp about stack-vs-heap allocation. The language encapsulates the concept away from you, so if you wrench it back, you're no longer quite writing the language; you're writing a union of it and something else.

Re:The Performance Cost of Integer Overflow Checking by marvy on Thursday December 18, 2014 @02:37AM (#8766371)
Yes, but in practice, that's what people do: write in a language more powerful than the standard gives them. You kind of have to if you want to get anything done without driving yourself crazy. For example:

long mega_byte = 1024 * 1024 * 8; // bits per MB long mega_bit = 1000 * 1000; // bits per megabit

If you follow the C90 standard, this code has all sorts of issues. First, // comments are not allowed. Second, identifiers are only guaranteed to have six significant characters, so the above two variables might actually be the same variable. Finally, ints are only guaranteed to be 2 bytes, so the multiplication may overflow and the program is undefined. (Assigning to longs doesn't help: the multiplication already happened.)

Re:The Performance Cost of Integer Overflow Checking by scott_s on Thursday December 18, 2014 @04:40PM (#8769788)
You are correct that such things are outside of the C abstract machine, but GCC provides a lot of extensions that are outside of the C abstract machine. For example, __sync_synchronize and other atomic intrinsics (https://gcc.gnu.org/onlinedocs/gcc-4.6.2/gcc/Atomic-Builtins...). C had no memory model when these were introduced (which, of course, is why they were introduced), so they were outside of the C abstract machine.
Re:The Performance Cost of Integer Overflow Checking by gsnedders on Thursday December 18, 2014 @07:47AM (#8766994)
signed integer overflow is undefined; undefined integer overflow is well defined (to use mod arithmetic).
Re:The Performance Cost of Integer Overflow Checking by Someone on Thursday December 18, 2014 @02:32AM (#8766366)
Why limit #2 to 2^bitsize? Arithmetic modulo 86400 (or 12, 24, 60) can be handy, too (especially if there is an 'on overflow do' facility)

And people will want complex numbers, quarternions, non-Abelian groups, etc.

Re:The Performance Cost of Integer Overflow Checking by derefr on Thursday December 18, 2014 @04:59PM (#8769898)
The important thing when giving people primitives to work with is that they come with time and space guarantees. People are writing low-level code basically in order to be able to explicitly make that choice, rather than having the compiler make it for them.

So, #2 is just a few extra guarantees about the intrinsics of regular machine-words, with minimal overhead for the fast path (even on the slower path of e.g. a 30-bit ring on 32-bit storage, there's still an O(1) set of barrel-shifts and masks that can be used to implement that.)

A fully-general ringed arithmetic value, on the other hand, is more of an ADT. It could certainly be implemented in the same language and act like a number, but it wouldn't be useful as backing storage for other types in the way #1, #2, and #3 are. (Note that #2 is a better backing store than #1 for many use-cases, e.g. encoding IP addresses and subnet masks.)

Re:The Performance Cost of Integer Overflow Checking by Someone on Thursday December 18, 2014 @07:56PM (#8770621)
Time guarantees on a modern out-of-order processor with some complicated cache structure of three or more levels, with virtual memory enabled? Forget it.

Also, if you include bigints in your list of things people want, I do not find it unreasonable to add timestamps (maybe not the best example because of leap seconds) or 'day of the week', 'month of the year' to that list. Most language libraries get those (often including those perfect 86400 second days) before they get bigints.

Re:The Performance Cost of Integer Overflow Checking by SamReidHughes on Thursday December 18, 2014 @12:24AM (#8766097)
I don't want 3, because I don't want tag bits or space wastage, but also because I don't want to have to link a bigint library.
Re:The Performance Cost of Integer Overflow Checking by derefr on Thursday December 18, 2014 @12:50AM (#8766156)
What do you expect to happen, then, in cases where you have a "can't fail" transparent deserialization operation from a wire format that doesn't limit the precision of its integers? Say, a web request that receives and decodes a JSON object. Now, JSON itself has no integer type, just a double type—but when people are manually generating JSON, they tend to forget this and shove arbitrary-precision integers in as naked \d+ tokens; and when people are receiving JSON, they also tend to expect to receive integers, not doubles. So what would you expect this JSON-decoding library to do, in a sensible language:

• crash the request thread?

• output a floating-point value with some of the precision thrown away?

• output a machine integer with the overflow flag set?

• output an arbitrary-precision integer?

Basically, arbitrary-precision integers are a necessary part of any platform that needs to be able to hold onto, and do math to, externally-generated numbers that didn't arrive packed in #1A type structs.

To insist, in the modern day, on attempting to do arbitrary math with arbitrary numbers using strictly machine words, is like insisting on defining a Postgres column as a VARCHAR, when TEXT is just as optimal for the average case, while automatically coping with edge-cases.

Most numbers computers touch don't have bit patterns that fit in 8(2^n) bits, but not 8(2^n) - 1 bits. Tag bits are cheap, especially if you have the other two integer types to fall back on.

Re:The Performance Cost of Integer Overflow Checking by SamReidHughes on Thursday December 18, 2014 @01:30AM (#8766250)
I would expect the JSON-decoding library to do one of the following, depending on the library author's or callee's wishes:

- output a floating-point value with some lost precision

- output an arbitrary-precision integer, or some general "number" type that can be an arbitrary-precision integer or double-precision float

- output an "integer too precise to decode" placeholder in that location in the data structure

- fail to decode the document entirely

In no case should it crash.

I don't know what you mean by "a machine integer with the overflow flag set", since it doesn't exactly work that way, so the "integer too precise to decode" value is my alternative.

For example, suppose you're making a "JSON document"-based database engine and its query language only supports double-precision numbers. In that case, I would output a correctly-rounded floating point value, if I were decoding JSON.

Usually in other cases of decoding an integer, unless you're hosting an arbitrary precision integer calculator web application, there should be maximum acceptable values on any integer you'd read off the wire. For example, there's a maximum data size, maximum timeout duration, and such.

Re:The Performance Cost of Integer Overflow Checking by derefr on Thursday December 18, 2014 @04:51PM (#8769856)
> fail to decode the document entirely [...] in no case should it crash

Note that I was using the Erlang sense of "crash"—a crash from a pattern-matching failure is the default clause of most case statements, and you want those to be bubbled up by crashing linked and supervising processes until they hit something that has generic "something went wrong; I'm going to report this to the user" code in it (like e.g. Rack does in Ruby.) You don't want to specifically be throwing, immediately catching, and then converting exceptions into 500 errors in every part of your code.

Also, I was assuming in this example that you're using a modern web framework, where the JSON decoding is handled by the framework—not by you—so the framework likely doesn't expose any configuration for something like its JSON deserialization library, which it wants you to just consider an implementation detail. So you won't get to specify anything like "maximum data size". Instead, the JSON library needs to "just work" in all cases, returning its best-effort interpretation of the wire message to you. (The parallel for HTML parsing would be libraries like Beautiful Soup.)

Re:The Performance Cost of Integer Overflow Checking by lmm on Thursday December 18, 2014 @05:30AM (#8766736)
Punting the choice up to application code is not a good idea; maybe you should allow them to override the config, but good defaults are important.
Re:The Performance Cost of Integer Overflow Checking by nly on Thursday December 18, 2014 @09:02AM (#8767207)
The only sane default is to return an arbitrary precision arithmetic type with an optional mode for truncation to double for performance.
Re:The Performance Cost of Integer Overflow Checking by xxgreg on Thursday December 18, 2014 @02:41AM (#8766376)
"JSON itself has no integer type, just a double type"

Nit - actually the JSON standard doesn't specify a precision for the number type, but most JSON implementations don't support arbitrary precision numbers.

Though the more recent RFC does have some implementation notes for interoperability.

http://rfc7159.net/rfc7159#rfc.section.6

> "This specification allows implementations to set limits on the range and precision of numbers accepted. Since software that implements IEEE 754-2008 binary64 (double precision) numbers [IEEE754] is generally available and widely used, good interoperability can be achieved by implementations that expect no more precision or range than these provide, in the sense that implementations will approximate JSON numbers within the expected precision. A JSON number such as 1E400 or 3.141592653589793238462643383279 may indicate potential interoperability problems, since it suggests that the software that created it expects receiving software to have greater capabilities for numeric magnitude and precision than is widely available."

> "Note that when such software is used, numbers that are integers and are in the range [-(253)+1, (253)-1] are interoperable in the sense that implementations will agree exactly on their numeric values."