5 ms·

Integer overflow is really a strange problem - it is no problem at all on the assembly level but then we abstracted away the details in our higher level languag

by danbruc 12y ago

Integer overflow is really a strange problem - it is no problem at all on the assembly level but then we abstracted away the details in our higher level languages for convenience or what ever only to realize that we now regularly shoot our feet. It is nothing more than a language design mistake.

sillysaurus3 12y ago
Hm? In Lisp or Python, you don't have overflow issues because ints can't overflow. It's only a problem at the assembly/low level. EDIT: The point of the parent comment is that integer overflow "isn't a problem at the assembly level, only in high level languages." But high level languages actually prevent the problem. You don't even have to worry about ints overflowing when you use Python or Lisp. You do have to worry if you're assembly or are using a lower level language like C. So the situation is actually opposite from what the parent comment describes.
- danbruc 12y ago
  Arbitrary-precision arithmetic is probably not a general solution but it might indeed be worthwhile to consider using it more often and especially if performance is not a major concern.
  - sillysaurus3 12y ago
    Performance is not a major concern. Security and reliability trump performance considerations. In my experience, especially at large companies, unfounded "performance concerns" are the root of much evil. This isn't true all of the time. HFT and gamedev, for example. But gamedev only uses C++ because everyone else uses C++, and HFT often uses languages other than C/C++ from what I've heard. Though the performance-critical sections are usually transformed into C. Though as I write this, I think of Chromium and Firefox and realize that C++ was probably the correct choice for both. On the other hand, I hear Rust is making some pretty great strides in that context.
    - danbruc 12y ago
      I would be interested in the impact of just replacing every fixed size integer with variable length ones. Plain integer array - gone. Single cycle math operations - gone. I really can't tell what the impact would be.
      - dezgeg 12y ago
        A sane implementation of bigints uses pointer tagging such that arithmetic on sufficiently small numbers (e.g. two 63-bit operands on a 64-bit machine) is still just a couple of cycles, with just an extra comparison and a (most likely optimally predicted) branch in the hot path. Then, assuming the bigints are implemented in the core language, we could make the compiler optimize the bigint checks away when possible. For example, consider this hypothetical function: void memzero_range(char* array, int start, int end) { for(int i = start; i < end; i++) array[i] = 0; } Now, what can we infer from the 'array[i] = 0;' in the body of the loop? Certainly, on a 64-bit machine it's not possible for i to go over 2^64 without experiencing undefined behaviour. So a smart (and conforming) compiler could just do if (is_bigint(start) || is_bigint(end)) abort(); once, and then execute the loop itself without any overhead from bigints. Or well, that's at least my personal dream of what should happen.
- Dylan16807 12y ago
  HighER level than assembly is where the problem exists. You point out that it's even stranger. It doesn't exist at very low levels or at very high levels. But C has this problem anyway.
- rurban 12y ago
  No, it is a problem with languages if you want to have competitive performance or precision. On the assembly level it's trivial to check the OF. But compilers and the libm didn't care enough, and languages didn't know better, as old knowledge was forgotten or ignored. The good old Lisp's used those assembly ops to detect the overflow flag for decades and promote to bigint afterwards, and bad languages like Perl, Python, Ruby (created much later then the good old languages) did it the slow way with multiple checks before and after and then promote to float and loose precision then. lua at least refused to deal with this crap and does everything with double and looses precision by definition. Newer languages are now coming back to the old lisps and auto-promote to bigint, not double. But they haven't found out yet how to check the OF after the op, as only a few can compile natively or deal with inline assembly.
nly 12y ago
> It is nothing more than a language design mistake. Well, Ada[0] had ranged integer types which allowed the compiler to determine whether overflow can occur statically. I don't know why modern languages like C#, Java, Go and Rust don't do this instead of taking the performance hit... in general no JIT will save you, and it's useful for things like formatted I/O and parsing as well [0] https://en.wikipedia.org/wiki/Ada_%28programming_language%29#Data_types https://en.wikipedia.org/wiki/Ada_%28programming_language%29...
- danbruc 12y ago
  Interoperability may be a factor. Everything that enters your world will tell you nothing about the possible ranges and you pretty quickly have to assume the worst case everywhere or add range limiting assertion early. It still sounds like a good idea but maybe it's harder to do than it seems.
  - nly 12y ago
    Range checking early doesn't strike me as a bad thing at all.
    - danbruc 12y ago
      Me neither. But it won't be for free and integer overflow is only an issue for a tiny fraction of all the code and developers are lazy...
- eric_bullington 12y ago
  I'm pretty sure Ada's ranged integer is tested dynamically, not statically. It's still a cool language feature. To get a static detection of integer overflow, I think that you need to use some variation of dependent typing. So it's possible in Liquid Haskell. And of course, it's easily done in dependent-typed languages like Agda, Coq, and Idris. Edit: I had earlier written Nim has this static range checking capability, but it looks like it also uses a runtime check.

by danbruc 12y ago

sillysaurus3 12y ago

Hm? In Lisp or Python, you don't have overflow issues because ints can't overflow. It's only a problem at the assembly/low level. EDIT: The point of the parent comment is that integer overflow "isn't a problem at the assembly level, only in high level languages." But high level languages actually prevent the problem. You don't even have to worry about ints overflowing when you use Python or Lisp. You do have to worry if you're assembly or are using a lower level language like C. So the situation is actually opposite from what the parent comment describes.

danbruc 12y ago
Arbitrary-precision arithmetic is probably not a general solution but it might indeed be worthwhile to consider using it more often and especially if performance is not a major concern.
- sillysaurus3 12y ago
  Performance is not a major concern. Security and reliability trump performance considerations. In my experience, especially at large companies, unfounded "performance concerns" are the root of much evil. This isn't true all of the time. HFT and gamedev, for example. But gamedev only uses C++ because everyone else uses C++, and HFT often uses languages other than C/C++ from what I've heard. Though the performance-critical sections are usually transformed into C. Though as I write this, I think of Chromium and Firefox and realize that C++ was probably the correct choice for both. On the other hand, I hear Rust is making some pretty great strides in that context.
  - danbruc 12y ago
    I would be interested in the impact of just replacing every fixed size integer with variable length ones. Plain integer array - gone. Single cycle math operations - gone. I really can't tell what the impact would be.
    - dezgeg 12y ago
      A sane implementation of bigints uses pointer tagging such that arithmetic on sufficiently small numbers (e.g. two 63-bit operands on a 64-bit machine) is still just a couple of cycles, with just an extra comparison and a (most likely optimally predicted) branch in the hot path. Then, assuming the bigints are implemented in the core language, we could make the compiler optimize the bigint checks away when possible. For example, consider this hypothetical function: void memzero_range(char* array, int start, int end) { for(int i = start; i < end; i++) array[i] = 0; } Now, what can we infer from the 'array[i] = 0;' in the body of the loop? Certainly, on a 64-bit machine it's not possible for i to go over 2^64 without experiencing undefined behaviour. So a smart (and conforming) compiler could just do if (is_bigint(start) || is_bigint(end)) abort(); once, and then execute the loop itself without any overhead from bigints. Or well, that's at least my personal dream of what should happen.
Dylan16807 12y ago
HighER level than assembly is where the problem exists. You point out that it's even stranger. It doesn't exist at very low levels or at very high levels. But C has this problem anyway.
rurban 12y ago
No, it is a problem with languages if you want to have competitive performance or precision. On the assembly level it's trivial to check the OF. But compilers and the libm didn't care enough, and languages didn't know better, as old knowledge was forgotten or ignored. The good old Lisp's used those assembly ops to detect the overflow flag for decades and promote to bigint afterwards, and bad languages like Perl, Python, Ruby (created much later then the good old languages) did it the slow way with multiple checks before and after and then promote to float and loose precision then. lua at least refused to deal with this crap and does everything with double and looses precision by definition. Newer languages are now coming back to the old lisps and auto-promote to bigint, not double. But they haven't found out yet how to check the OF after the op, as only a few can compile natively or deal with inline assembly.

nly 12y ago

> It is nothing more than a language design mistake. Well, Ada[0] had ranged integer types which allowed the compiler to determine whether overflow can occur statically. I don't know why modern languages like C#, Java, Go and Rust don't do this instead of taking the performance hit... in general no JIT will save you, and it's useful for things like formatted I/O and parsing as well [0] https://en.wikipedia.org/wiki/Ada_%28programming_language%29#Data_types https://en.wikipedia.org/wiki/Ada_%28programming_language%29...

danbruc 12y ago
Interoperability may be a factor. Everything that enters your world will tell you nothing about the possible ranges and you pretty quickly have to assume the worst case everywhere or add range limiting assertion early. It still sounds like a good idea but maybe it's harder to do than it seems.
- nly 12y ago
  Range checking early doesn't strike me as a bad thing at all.
  - danbruc 12y ago
    Me neither. But it won't be for free and integer overflow is only an issue for a tiny fraction of all the code and developers are lazy...
eric_bullington 12y ago
I'm pretty sure Ada's ranged integer is tested dynamically, not statically. It's still a cool language feature. To get a static detection of integer overflow, I think that you need to use some variation of dependent typing. So it's possible in Liquid Haskell. And of course, it's easily done in dependent-typed languages like Agda, Coq, and Idris. Edit: I had earlier written Nim has this static range checking capability, but it looks like it also uses a runtime check.