3 ms·

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 pare

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.

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.