News for hackers. Stuff that matters.
Re:Nearly All Binary Searches and Mergesorts are Broken (2006) by RogerL on Thursday July 09, 2015 @03:34PM (#9860183)
"shouldn't be" is in the eye of the beholder.

None of my input is in the range where a+b generates an overflow. I "shouldn't" have to pay for something I am not using - overflow detection. If you want to pay that price, fine, use a BigNum library and pay it.

I'm not saying I'm right, I'm pointing out the thinking behind the 'only pay for what you ask for' type languages.

edit: more context is in order. This is a trivial example of numeric issues. Try writing numeric code using IEEE floating point. There is a large number of concerns to keep in mind. While we can envision schemes that would make it safer to write naive code, I'm going to bet the average person is willing to accept a frame rate of 5 because "safety". Any real language design is going to make trade offs in this sort of thing, and any given line drawn in the sand will inconvenience somebody.

Re:Nearly All Binary Searches and Mergesorts are Broken (2006) by Retric on Thursday July 09, 2015 @03:41PM (#9860231)
Overflow detection at the CPU level is almost free. If common languages add it by default you quickly get HW speed ups.
Re:Nearly All Binary Searches and Mergesorts are Broken (2006) by exDM69 on Thursday July 09, 2015 @03:54PM (#9860282)
> Overflow detection at the CPU level is almost free.

Yes, detecting the overflow is free but reacting to it is expensive. If you do care about it, you'll fire off some kind of trap handler or at least do a data dependent branch which has a performance hit with pipelining.

It's definitely not something that should be enabled for every integer operation for all languages.

Re:Nearly All Binary Searches and Mergesorts are Broken (2006) by Natsu on Thursday July 09, 2015 @04:16PM (#9860395)
> Yes, detecting the overflow is free but reacting to it is expensive.

And if you tell the compiler not to care, it won't be doing that reaction (only the 'free' detection) and I thought you already stipulated that your hypothetical code would be doing math where that simply didn't happen, meaning that the expensive reaction would not be triggered.

Re:Nearly All Binary Searches and Mergesorts are Broken (2006) by Retric on Thursday July 09, 2015 @04:11PM (#9860366)
Are you really suggesting that because dealing with a bug takes longer your better off ignoring it and returning a huge negative number by default?

  Car designer: What happens if they run out of gas?
  Pump designer:  Hmm, that's out of spec, ahh we set off a stick of TNT to notify the user of the problem.
  Car designer: Sounds reasonable.
Re:Nearly All Binary Searches and Mergesorts are Broken (2006) by exDM69 on Thursday July 09, 2015 @04:27PM (#9860453)
> Are you really suggesting that because dealing with a bug takes longer your better off ignoring it and returning a huge negative number by default?

You're lucky if you get a huge negative number. Signed integer overflow is undefined behavior and may have awkward consequences when coupled with compiler optimization. E.g. if(x+1 > x) may be replaced with if(true) legally.

And this is why computers programs are fast. Yes, it may be a good idea to do something else in a high level language but if your kernel, web browser, etc were written with a nanny language that checks for every possible corner case for every operation, it would be painfully slow. Integer addition arithmetic is one of the most common operations your computer does, making that 2-10x or more slower would have catastrophic consequences.

And despite all this "danger", your kernel and web browser and http server just work.

Re:Nearly All Binary Searches and Mergesorts are Broken (2006) by Retric on Thursday July 09, 2015 @05:07PM (#9860684)
CPU speed is rarely a limitation because RAM is just stupid slow, and in MIPS and Alpha CPU's with HW support it's a rounding error as in well under 1% for most code. Even software based overflow detection runs in the 5-10% range not 100-1,000% range your suggesting.

PS: There are several models you can test yourself. http://blog.regehr.org/archives/1154

edit: http://resources.sei.cmu.edu/asset_files/TechnicalNote/2010_... Has actual benchmarks in the 6-8% range.

Re:Nearly All Binary Searches and Mergesorts are Broken (2006) by wtallis on Thursday July 09, 2015 @05:22PM (#9860778)
Yeah, it's pretty much a given that checking for overflow won't be the bottleneck when you're doing pointer arithmetic to traverse a large data structure. The memory accesses will dominate over the cost of the highly-predictable branches.
Re:Nearly All Binary Searches and Mergesorts are Broken (2006) by ScottBurson on Thursday July 09, 2015 @06:39PM (#9861161)
> Integer addition arithmetic is one of the most common operations your computer does, making that 2-10x or more slower would have catastrophic consequences.

Common Lisp is a compiled language that has arbitrary-precision integer arithmetic by default. What we generally find is that in most kinds of code the cost of the conditional branch is negligible; it's dwarfed by memory access, function call, and other conditional logic in the program.

There are, of course, exceptions. Most of these are array operations where one is doing a small amount of work on each of a large number of array elements; array index computations are a good example of a place where one doesn't generally want to pay the cost of overflow checking. For those situations, Common Lisp provides declarations one can write to cause the overflow checking to be skipped.

The overall effect is far from catastrophic. Common Lisp is competitive with other compiled languages -- not the very fastest, perhaps, but definitely in that range, and a good 10 to 30 times faster than interpreted Python or Ruby -- languages in which a lot of code is being written these days.

Now to this specific example. What would have happened if it were written in CL? If the programmer had not specified otherwise, the arithmetic would be done in arbitrary precision and would work correctly. That's clearly the correct choice in this case: even though an array index is being computed, it's effectively a random index from the hardware's point of view; cache prefetching will be no help at all. That being the case, the performance will be dominated by memory latency (at least to the L2 and L3 caches, if not all the way to main memory). Also, in many applications, the comparison between two elements will involve a function call; it won't be just an integer less-than instruction. So worrying about a couple of integer overflow tests would be pretty silly.

I concede the possibility that, this argument notwithstanding, the programmer might have turned off overflow checking anyway. Well, you can shoot yourself in the foot in any language. Lisp just tries to make it not be the default.

Re:Nearly All Binary Searches and Mergesorts are Broken (2006) by Demiurge on Thursday July 09, 2015 @04:02PM (#9860323)
What are the potential instances when you want to ignore integer overflow, or the expense of ignoring it is less than handling it? I can't think of anything.
Re:Nearly All Binary Searches and Mergesorts are Broken (2006) by SiVal on Thursday July 09, 2015 @05:02PM (#9860659)
When you want to ignore integer overflow is when your code isn't going to get near the overflow value and every bit of speed improvement (of that portion of the code) matters.

BUT, just because there are cases where a certain choice is the right one doesn't mean that choice should be the default. I strongly believe that the safe choice is right default. You add two numbers, and the default is the sum of those numbers or a message that the sum cannot be calculated, not a fast, confident answer that is occasionally wrong. You try to access an array and either get part of the array or get an error telling you the part you asked for doesn't exist, not you sometimes get the array and sometimes do wacky, unpredictable things that corrupt data randomly and open you up to hacking exploits as fast as possible.

Make doing the proper, safe, reliable, predictable thing the default behavior, but allow for explicit removal of the safeguards as an optimization once you have enough information about runtime behavior to determine that you can do so and get better results from certain parts of your code.

Re:Nearly All Binary Searches and Mergesorts are Broken (2006) by ScottBurson on Thursday July 09, 2015 @06:42PM (#9861173)
Sometimes you specifically want arithmetic modulo 2^32 (or some other word length). This comes up in cryptography, for example.
Re:Nearly All Binary Searches and Mergesorts are Broken (2006) by detrino on Thursday July 09, 2015 @04:12PM (#9860376)
Are you overloading "expense" here to mean something other than runtime performance?
Re:Nearly All Binary Searches and Mergesorts are Broken (2006) by Demiurge on Thursday July 09, 2015 @04:38PM (#9860512)
Yes, any expense, for example satellite crashing on white house starting WW3.
Re:Nearly All Binary Searches and Mergesorts are Broken (2006) by renox on Friday July 10, 2015 @07:17AM (#9863248)
> Yes, detecting the overflow is free but reacting to it is expensive.

Who cares?? There should not be integer overflow in your program, so the 'reaction time' is free because it isn't used.

If you have an overflow, then there is a bug in your program, and in C it's perfectly legal to STOP your program in case of integer overflow, so again the reaction time doesn't matter.

Re:Nearly All Binary Searches and Mergesorts are Broken (2006) by rayiner on Thursday July 09, 2015 @05:08PM (#9860698)
But you'll almost never overflow.
Re:Nearly All Binary Searches and Mergesorts are Broken (2006) by hga on Thursday July 09, 2015 @04:08PM (#9860351)
Not in RISC-V, which despite saying it wants to be relevant to industry, is entirely lacking in extra features for integer error detection besides divide by zero.

They justify it ... with all the popular languages that silently allow these errors.

Re:Nearly All Binary Searches and Mergesorts are Broken (2006) by mark-r on Thursday July 09, 2015 @05:00PM (#9860646)
This is the chicken or egg problem. If one of the leading languages had required bounds checking back when the processor instruction sets were being defined, those instructions would already exist and the cost today would be negligible. But the languages didn't include it because it would have been expensive at the time.
Re:Nearly All Binary Searches and Mergesorts are Broken (2006) by kybernetikos on Thursday July 09, 2015 @07:36PM (#9861417)
I'm sure I did a bunch of assembly programming on a CPU that had a flag telling you if the last calculation overflowed or not. Branch if overflow was a straightforward opcode.
Re:Nearly All Binary Searches and Mergesorts are Broken (2006) by mark-r on Friday July 10, 2015 @12:18PM (#9864830)
Yes, but adding the branch instruction itself is the killer. If the processor had some kind of trap to set for overflow, there would be no extra instructions and no timing overhead when there wasn't an overflow.
Re:Nearly All Binary Searches and Mergesorts are Broken (2006) by hga on Thursday July 09, 2015 @08:13PM (#9861576)
Indeed. I'm not sure how far back this goes, but definitely to the PDP-11, and looks like the IBM 360.