3 ms·

"If you’re designing a high level language, the obvious solution is to use true integer semantics (aka bigints) everywhere like Python does. However, this appro

"If you’re designing a high level language, the obvious solution is to use true integer semantics (aka bigints) everywhere like Python does. However, this approach is not popular in low level languages due to the difficulty of optimizing bigint code." I feel like this is a bit of a leap - in a great many scenarios, you don't ever want a number bigger than will fit in a 64-bit int. A number that big likely indicates a bug or corrupt data coming from somewhere else. It can also create a bunch of larger scale problems - a 256-bit int creeps in somewhere and now all your ints are getting promoted from 64-bit register ints to heap allocations, all your operations slow down, the application runs out of memory or just hangs... To me, the obvious solution is to throw/panic on overflow, as some runtime environments can: https://docs.microsoft.com/en-us/dotnet/csharp/language-reference/keywords/checked-and-unchecked https://docs.microsoft.com/en-us/dotnet/csharp/language-refe... The elaborate CS solutions via things like range analysis are very cool, though, and I look forward to being able to use a language in production that does stuff like what's described in the article.

vbezhenar 5y ago
Yep, integer overflow suddenly turns into heap overflow. Not good.
- PaulHoule 5y ago
  I was reading a 1987 article from Byte magazine that reminded me that many of the plots of "fractals" that you've seen are wrong. Specifically, when people make a plot like https://galileo-unbound.blog/2018/12/10/the-wonderful-world-of-hamiltonian-maps/ https://galileo-unbound.blog/2018/12/10/the-wonderful-world-... you see these areas that look like television static that are wrong. The reason why you see chaotic motion in those areas (a infinite number of unstable fixed points) is that there are an infinite number of stable fixed points and they breed unstable fixed points on the separatrices between them. If you look at the edges of the unstable areas you see a hierarchy of stable islands that come out of resonances having resonances with other resonances that have resonances with even more resonances, etc. If you could run the simulation long enough AND you ran it accurately you'd see that throughout the whole unstable region the chaotic motion weaves around numerous islands of stability it which would make a much more detailed and beautiful plot. If you run this with, say, 64-bit fixed point math, you'd find that the dynamics after 64 doubling times is dominated by rounding errors. So a plot like that is showing just a fraction of the detail that's there. Now you could increase the precision as you run over time and it ought to be possible to use interval math to do a grid search and prove the calculations are accurate, but it turns something that is O(N) in time where N is the number of iterations to something that is O(N^2). In terms of storage it goes from O(1) to O(N). It's one of those problems that usually gets ignored and that's some of the reason why chaos and fractals get less respect and less progress than they deserve. I've been thinking about better ways to draw them however, not because I care about the dynamics themselves, but I want to make more beautiful images and see improved dynamics as the royal road to that.
- SuchAnonMuchWow 5y ago
  I think those cases are a minority, and in most cases you would have been fine with just slightly larger ints. It doesn't seems to cause any issue in python for example, because the cases where integers grow exponentially (which is the same as making their size grow linearly, so its still slow memory-wise) and without bounds are not all that common. For example, an overflow bug was famous in java for being present in the standard library for a very long time: in a core function performing a binary search, the operation computing the middle of the two bounds was a simple average (max + min)/2, which overflow when max and min are big enough, even if the final result always fit in a standard integer. In a lot of other cases, integer are used to address memory (or to represent array indexes, etc), so in most code they will naturally be restricted by the available amount of memory, even if intermediate computations can temporarily overflow.
  - kevingadd 5y ago
    Converting a 'numeric overflow exception' to a 'you eventually run out of memory' failure is much worse, because exhausting memory will cause system-wide impact instead of just killing the individual process handling a request/operation. OOM is also generally handled much worse in software vs throwing an exception at the point where data first exceeds the expected range. Do you really want to kick off the linux oom killer every time someone uploads a corrupted png to your server? In general, it's much better to catch out-of-range/corrupt data early, and silently promoting to a 256-bit int is effectively hiding corrupt data in the majority of cases. The maximum 64-bit int is really big.
cratermoon 5y ago
> in a great many scenarios, you don't ever want a number bigger than will fit in a 64-bit int. You might think that, but remember that during math operations the number of bits isn't all that matters, and even if your final result can fit in a 64-bit int, you can get errors in calculations when the intermediate results depend on needing extra precision.
- wongarsu 5y ago
  Adding at least a factor of two for safety is reasonable. So e.g. if you compute with 64-bit integers, you shouldn't ask if you ever need numbers larger than (2^64)-1, but if you need numbers larger than 2^62 (one bit for allowing signed ints, one for intermediates). That catches the most common examples like overflowing when calculating the average of two numbers or when calculating an offset. The less safety factor you have the more carefully you have to consider what your intermediates are doing. But going up one level of precision probably won't hurt performance too bad, if your language makes it easy (like 128-bit ints)
nerdponx 5y ago
Sounds like a good use case for refinement types or general dependent types, where you can elide overflow checks if (and only if) you can prove to the compiler that a computation won't overflow. That way you can put explicit overflow checks at the boundaries of your application, and then internally you pass around compile-time "proofs" of safety and/or perform explicit overflow checks where needed.

vbezhenar 5y ago

Yep, integer overflow suddenly turns into heap overflow. Not good.

PaulHoule 5y ago
I was reading a 1987 article from Byte magazine that reminded me that many of the plots of "fractals" that you've seen are wrong. Specifically, when people make a plot like https://galileo-unbound.blog/2018/12/10/the-wonderful-world-of-hamiltonian-maps/ https://galileo-unbound.blog/2018/12/10/the-wonderful-world-... you see these areas that look like television static that are wrong. The reason why you see chaotic motion in those areas (a infinite number of unstable fixed points) is that there are an infinite number of stable fixed points and they breed unstable fixed points on the separatrices between them. If you look at the edges of the unstable areas you see a hierarchy of stable islands that come out of resonances having resonances with other resonances that have resonances with even more resonances, etc. If you could run the simulation long enough AND you ran it accurately you'd see that throughout the whole unstable region the chaotic motion weaves around numerous islands of stability it which would make a much more detailed and beautiful plot. If you run this with, say, 64-bit fixed point math, you'd find that the dynamics after 64 doubling times is dominated by rounding errors. So a plot like that is showing just a fraction of the detail that's there. Now you could increase the precision as you run over time and it ought to be possible to use interval math to do a grid search and prove the calculations are accurate, but it turns something that is O(N) in time where N is the number of iterations to something that is O(N^2). In terms of storage it goes from O(1) to O(N). It's one of those problems that usually gets ignored and that's some of the reason why chaos and fractals get less respect and less progress than they deserve. I've been thinking about better ways to draw them however, not because I care about the dynamics themselves, but I want to make more beautiful images and see improved dynamics as the royal road to that.
SuchAnonMuchWow 5y ago
I think those cases are a minority, and in most cases you would have been fine with just slightly larger ints. It doesn't seems to cause any issue in python for example, because the cases where integers grow exponentially (which is the same as making their size grow linearly, so its still slow memory-wise) and without bounds are not all that common. For example, an overflow bug was famous in java for being present in the standard library for a very long time: in a core function performing a binary search, the operation computing the middle of the two bounds was a simple average (max + min)/2, which overflow when max and min are big enough, even if the final result always fit in a standard integer. In a lot of other cases, integer are used to address memory (or to represent array indexes, etc), so in most code they will naturally be restricted by the available amount of memory, even if intermediate computations can temporarily overflow.
- kevingadd 5y ago
  Converting a 'numeric overflow exception' to a 'you eventually run out of memory' failure is much worse, because exhausting memory will cause system-wide impact instead of just killing the individual process handling a request/operation. OOM is also generally handled much worse in software vs throwing an exception at the point where data first exceeds the expected range. Do you really want to kick off the linux oom killer every time someone uploads a corrupted png to your server? In general, it's much better to catch out-of-range/corrupt data early, and silently promoting to a 256-bit int is effectively hiding corrupt data in the majority of cases. The maximum 64-bit int is really big.

cratermoon 5y ago

> in a great many scenarios, you don't ever want a number bigger than will fit in a 64-bit int. You might think that, but remember that during math operations the number of bits isn't all that matters, and even if your final result can fit in a 64-bit int, you can get errors in calculations when the intermediate results depend on needing extra precision.

wongarsu 5y ago
Adding at least a factor of two for safety is reasonable. So e.g. if you compute with 64-bit integers, you shouldn't ask if you ever need numbers larger than (2^64)-1, but if you need numbers larger than 2^62 (one bit for allowing signed ints, one for intermediates). That catches the most common examples like overflowing when calculating the average of two numbers or when calculating an offset. The less safety factor you have the more carefully you have to consider what your intermediates are doing. But going up one level of precision probably won't hurt performance too bad, if your language makes it easy (like 128-bit ints)

nerdponx 5y ago

Sounds like a good use case for refinement types or general dependent types, where you can elide overflow checks if (and only if) you can prove to the compiler that a computation won't overflow. That way you can put explicit overflow checks at the boundaries of your application, and then internally you pass around compile-time "proofs" of safety and/or perform explicit overflow checks where needed.