3 ms·

I am not familiar with Julia, but it seems like the common feature of “automatic big num conversion” would work against optimization like this correct? Because

I am not familiar with Julia, but it seems like the common feature of “automatic big num conversion” would work against optimization like this correct? Because the output type no longer depends on the input types, but also there values.

freemint 5y ago
You are correct that “automatic big num conversion” works much against optimization. Int{8,16,32,64,128} in Julia also overflow silently. If you want other behaviour you can write your own custom behavior and "overload" +,* for your type. SafeIntegers throws an exception on overflow. Switching to BigInt would also be possible to implement but i am not aware of any package that does that or if it would give performance benefit over just using BitInt to begin with.
- Sukera 5y ago
  Another alternative is to use the Base.Checked.* family of functions, though they have different names than (+) like checked_add and thus have to be explicitly used.
  - freemint 5y ago
    Which is what SafeInteger does internally. Checked is kinda obscure but i added a doc string to it which was merged with the main branch today.
Sukera 5y ago
If you're thinking about how in e.g. python, integer addition never overflows and is always a big integer, then yes. If "small"/machine integers and big integers are seperated each have a distinct type, promotion on overflow would introduce a type instability on every addition (not only the overflowing one!). This is precisely because the type would depend on the result of the addition, not only the input types (which may both be machine integer types). A "solution" to this conundrum is to have big integers by default, which sadly isn't feasible for performance reasons - you can't then take advantage of hardware, because every operation necessarily has to do more work than would be required for machine integers. -- To add on to this, when encountering overflow (which doesn't happen often in the first place), it's usually sufficient to go for 128 bit integers first instead of jumping directly to big integers. They're still quite a bit faster and offer a much larger space to work with.
StefanKarpinski 5y ago
This is one of the reasons that Julia doesn't do automatic big num conversion, instead using native machine two's complement modular arithmetic for integers. It would be a good optimization to use an immediate representation for small bignums, however. See this FAQ entry https://docs.julialang.org/en/v1/manual/faq/#faq-integer-arithmetic https://docs.julialang.org/en/v1/manual/faq/#faq-integer-ari... on the subject.
chrisseaton 5y ago
It would only depend on the value if the operation had actually overflowed in the past, in which case performance is already going to be poor.
- StefanKarpinski 5y ago
  That means it does depend on the value.
  - chrisseaton 5y ago
    That’s not quite what I mean - I mean the code to handle cases that depend on the value only needs to be included based on the observed values. That’s different to the code always being there and the control flow depending on the value.
    - StefanKarpinski 5y ago
      That's not how Julia's JIT works—it's "Just Ahead of Time" which is a term we use to distinguish it from what other modern JITs tend to do, which is generate code after some interpreted execution based on observed behavior. What Julia does is much more akin to static compilation but done the first time you need the code, based on strictly in advance data flow type analysis of the code. One of the interesting things about the language that this paper touches on is that Julia and its libraries are designed so that you can analyze code well enough in advance to perfectly predict types much of the time, even though that is not a static requirement of the language.

freemint 5y ago

You are correct that “automatic big num conversion” works much against optimization. Int{8,16,32,64,128} in Julia also overflow silently. If you want other behaviour you can write your own custom behavior and "overload" +,* for your type. SafeIntegers throws an exception on overflow. Switching to BigInt would also be possible to implement but i am not aware of any package that does that or if it would give performance benefit over just using BitInt to begin with.

Sukera 5y ago
Another alternative is to use the Base.Checked.* family of functions, though they have different names than (+) like checked_add and thus have to be explicitly used.
- freemint 5y ago
  Which is what SafeInteger does internally. Checked is kinda obscure but i added a doc string to it which was merged with the main branch today.

Sukera 5y ago

If you're thinking about how in e.g. python, integer addition never overflows and is always a big integer, then yes. If "small"/machine integers and big integers are seperated each have a distinct type, promotion on overflow would introduce a type instability on every addition (not only the overflowing one!). This is precisely because the type would depend on the result of the addition, not only the input types (which may both be machine integer types). A "solution" to this conundrum is to have big integers by default, which sadly isn't feasible for performance reasons - you can't then take advantage of hardware, because every operation necessarily has to do more work than would be required for machine integers. -- To add on to this, when encountering overflow (which doesn't happen often in the first place), it's usually sufficient to go for 128 bit integers first instead of jumping directly to big integers. They're still quite a bit faster and offer a much larger space to work with.

StefanKarpinski 5y ago

This is one of the reasons that Julia doesn't do automatic big num conversion, instead using native machine two's complement modular arithmetic for integers. It would be a good optimization to use an immediate representation for small bignums, however. See this FAQ entry https://docs.julialang.org/en/v1/manual/faq/#faq-integer-arithmetic https://docs.julialang.org/en/v1/manual/faq/#faq-integer-ari... on the subject.

chrisseaton 5y ago

It would only depend on the value if the operation had actually overflowed in the past, in which case performance is already going to be poor.

StefanKarpinski 5y ago
That means it does depend on the value.
- chrisseaton 5y ago
  That’s not quite what I mean - I mean the code to handle cases that depend on the value only needs to be included based on the observed values. That’s different to the code always being there and the control flow depending on the value.
  - StefanKarpinski 5y ago
    That's not how Julia's JIT works—it's "Just Ahead of Time" which is a term we use to distinguish it from what other modern JITs tend to do, which is generate code after some interpreted execution based on observed behavior. What Julia does is much more akin to static compilation but done the first time you need the code, based on strictly in advance data flow type analysis of the code. One of the interesting things about the language that this paper touches on is that Julia and its libraries are designed so that you can analyze code well enough in advance to perfectly predict types much of the time, even though that is not a static requirement of the language.