5 ms·

I would argue that the bug is not in the algorithm -- the bug is in languages that don't detect integer overflow by default. Arbitrary-precision integers, as a

I would argue that the bug is not in the algorithm -- the bug is in languages that don't detect integer overflow by default. Arbitrary-precision integers, as are the default in Lisp and Python, are ideal, but at the very least the implementation ought to throw an exception. Yes, occasionally one specifically wants arithmetic modulo 2^32 or some other word size, and languages should provide that as an option, but it shouldn't be the default.

RogerL 11y ago
"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.
- Retric 11y ago
  Overflow detection at the CPU level is almost free. If common languages add it by default you quickly get HW speed ups.
  - exDM69 11y ago
    > 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.
    - Demiurge 11y ago
      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.
      - detrino 11y ago
        Are you overloading "expense" here to mean something other than runtime performance?
        Demiurge 11y ago
        Yes, any expense, for example satellite crashing on white house starting WW3.
      - SiVal 11y ago
        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.
      - ScottBurson 11y ago
        Sometimes you specifically want arithmetic modulo 2^32 (or some other word length). This comes up in cryptography, for example.
    - 11y ago
  - hga 11y ago
    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.
    - mark-r 11y ago
      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.
      - kybernetikos 11y ago
        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.
        hga 11y ago
        Indeed. I'm not sure how far back this goes, but definitely to the PDP-11, and looks like the IBM 360.
        mark-r 11y ago
        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.
Demiurge 11y ago
I just finished reading and was going to say the same. It's not a logical error of the algorithm. The algorithm is not concerned with maximum index value, so it's an implementation detail.
sanderjd 11y ago
The Rust community had a series of long discussions about this earlier this year (see [0] and [1] mainly), and I came out of it thinking that a more perfect world would have arbitrary sized integers by default and convenient types for explicitly choosing wrapping, error-ing, or undefined behavior for overflow and underflow. But there are lots of reasons why that world is hard to achieve (for instance, arbitrarily sized integers require heap allocation and indirection, which makes them quite a different beast), and while I think the compromise Rust came to is fairly awkward, the trade-offs seem pretty tough and the path to an optimal solution is not at all obvious. [0]: https://github.com/rust-lang/rfcs/blob/master/text/0560-integer-overflow.md https://github.com/rust-lang/rfcs/blob/master/text/0560-inte... [1]: https://internals.rust-lang.org/t/on-casts-and-checked-overflow/1710 https://internals.rust-lang.org/t/on-casts-and-checked-overf...

RogerL 11y ago

"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.

Retric 11y ago
Overflow detection at the CPU level is almost free. If common languages add it by default you quickly get HW speed ups.
- exDM69 11y ago
  > 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.
  - Demiurge 11y ago
    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.
    - detrino 11y ago
      Are you overloading "expense" here to mean something other than runtime performance?
      - Demiurge 11y ago
        Yes, any expense, for example satellite crashing on white house starting WW3.
    - SiVal 11y ago
      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.
    - ScottBurson 11y ago
      Sometimes you specifically want arithmetic modulo 2^32 (or some other word length). This comes up in cryptography, for example.
  - 11y ago
- hga 11y ago
  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.
  - mark-r 11y ago
    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.
    - kybernetikos 11y ago
      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.
      - hga 11y ago
        Indeed. I'm not sure how far back this goes, but definitely to the PDP-11, and looks like the IBM 360.
      - mark-r 11y ago
        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.

Demiurge 11y ago

I just finished reading and was going to say the same. It's not a logical error of the algorithm. The algorithm is not concerned with maximum index value, so it's an implementation detail.

sanderjd 11y ago

The Rust community had a series of long discussions about this earlier this year (see [0] and [1] mainly), and I came out of it thinking that a more perfect world would have arbitrary sized integers by default and convenient types for explicitly choosing wrapping, error-ing, or undefined behavior for overflow and underflow. But there are lots of reasons why that world is hard to achieve (for instance, arbitrarily sized integers require heap allocation and indirection, which makes them quite a different beast), and while I think the compromise Rust came to is fairly awkward, the trade-offs seem pretty tough and the path to an optimal solution is not at all obvious. [0]: https://github.com/rust-lang/rfcs/blob/master/text/0560-integer-overflow.md https://github.com/rust-lang/rfcs/blob/master/text/0560-inte... [1]: https://internals.rust-lang.org/t/on-casts-and-checked-overflow/1710 https://internals.rust-lang.org/t/on-casts-and-checked-overf...