purescript
purescript copied to clipboard
purescript
Use Math.imul(a, b) instead of a * b | 0
Math.imul correctly handles arithmetic overflow, whereas | 0 just discards the most significant bits. This affects purescript-prelude as well as the inliner. Using Math.imul would also make Semiring Int lawful.
It'd be better if we can auto-polyfill this or something, since imul does not have solid browser support. It's not even ES5, nevermind the currently-supported ES3. 😕
Ok, there's https://github.com/purescript/purescript/issues/2921, but it was closed, so maybe let's just use this one.
MDN's Math.imul page suggests the following polyfill:
Math.imul = Math.imul || function(a, b) {
var ah = (a >>> 16) & 0xffff;
var al = a & 0xffff;
var bh = (b >>> 16) & 0xffff;
var bl = b & 0xffff;
// the shift by 0 fixes the sign on the high part
// the final |0 converts the unsigned value into a signed value
return ((al * bl) + (((ah * bl + al * bh) << 16) >>> 0)|0);
};
Come to think of it, we shouldn't mutate Math, and we can't exactly inline all that every time someone uses Int's *. Without a stdlib it's hard to see how to achieve this without either giving up inlining or dropping support for platforms which don't provide Math.imul.
If we had a general inliner i.e. one that didn't only use a set of special cases built in to the compiler, this would probably be doable, though.
@hdgarrood Do we have an official stance on JS engine support? It'd be nice to make a requirement that can shift over time like "browsers with >0.1% market share (by page loads) globally" or "browsers with >0.5% market share (by installations) in every individual market" or "browsers released in the last 5 years". A target of "just ES3" is problematic both because it doesn't actually represent meaningful browser support, and it doesn't allow us to improve/adapt as time passes and things get better.
I think it's reasonable to say that PureScript does not require a runtime, but relies on some set of easily polyfilled features, such as Math.imul or Object.keys.
I don't think we really have an official stance. The compiler generates ES3, most of the Node libraries assume node >= 4, and I guess from @natefaubion's comment that maps assumes Object.keys, so there's a mix. I think what you say makes sense though. I guess we haven't really needed to develop a clear stance as I don't think there are that many situations where we can't reasonably accomplish what we want using just ES3.
Would we be able to justify using Math.imul with any of those stances you gave, incidentally?
@hdgarrood I personally don't see a problem with mutating Math
The polyfill will only be added if Math.imul doesn't already exist, and the polyfill should have the correct behavior (it's just slower than native support), so I don't think the polyfill will cause any problems.
@michaelficarra Math.imul is supported in every browser except IE11.
This is because Math.imul is super easy for browsers to support (it's just standard C multiplication), and it was necessary for asm.js support, so all the browsers added it in really fast.
IE11 has ~4% market share, so I don't think it's viable to drop support for it right now.
Is there anything wrong with providing this as a library function in math for now?
If we mutated Math I reckon that in 99% of projects it would work fine, but I'm certain there will be people who have some weird setup that makes strange decisions based on the value of this property and would send them (and possibly also us) on a debugging goose chase for hours. It's maybe justifiable to mutate globals if you're writing a framework but I think it's poor etiquette to do so in a library. I just remember too many instances of this kind of code breaking things in totally unpredictable and unexpected ways back when I was a Rubyist.
If we were going to provide a temporary opt-in solution I'd rather do it in the form of a newtype over Int than a function in math, as I think that would be more useful. But what would we be waiting for if we did that? For IE's market share to die off sufficiently so that we could assume the presence of Math.imul?
It wouldn't fix (*) but I think that might be okay. We could just document that Int works most of the time but that there are catches, and that you can choose to use imul via a newtype if you want the fix at the cost of compatibility.
That sounds like a good thing to do for now — the Semiring documentation is already sufficient in that sense I think. I am still quite keen to get the default Semiring Int instance fixed, though.
@hdgarrood If some code breaks because Math.imul exists, then it's already broken on all modern browsers. The only possible way it could break is if it relied upon the string representation of the Math.imul function (which is a horrible thing to do in any case).
Yes global mutation has been abused in the past in JavaScript, and of course I recommend against it, but in this specific case, it should be fine.
Having said that, I'm okay with putting it in math and using a newtype
I'm not convinced, personally - I've been bitten too many times by conflating "this is safe" with "I cannot think of a way this could be unsafe". And it's not just about that property existing - it seems a reasonable assumption to make that the number of properties of Math isn't going to change over the course of running the code on a webpage, for instance, but this would no longer be true. It probably only is horrible code which could be affected but the quality of any other code on a page containing some PureScript code isn't any of our business, imo.
If we document that overflow on multiplication gives an unspecified result then switching to Math.imul later won't be a breaking change.
Ok, so to recap: since no version of IE supports Math.imul, it will probably be a quite long time before we can just start using it without having to worry about compatibility.
We could say that PureScript depends on some easily-polyfillable features, and just let the user polyfill themselves if they want IE support, but for something as basic as integer multiplication I think this would be a poor UX for devs not familiar with PureScript and/or this specific issue.
We could polyfill it ourselves by getting the compiler to insert some code which mutates window.Math to add the imul property if there are any uses of multiplication with the Int type, but I'd rather not do this because I think it is poor etiquette. It also sounds like it could be quite fiddly, and I think it goes against the "no stdlib" principle.
One alternative option that has just occurred to me is that we change the definition of intMul so that it uses Math.imul via the FFI if it is there, or otherwise it uses a polyfill, but whichever path is taken, it should be done without mutating window.Math. See this PR for how we might achieve that (thanks @matthewleon :smile:). Then, we'd need to improve the inliner so that this could be inlined properly (i.e. by generating a require statement if necessary). I think this would be my preferred option, although I'm not sure how difficult modifying the inliner would be.
Another option is to make it explicit that the user needs to polyfill things, either by moving it into its own module (Math.NonPortable or something), or by using a type class à la Partial, or both.
Anything bad about changing the definition of intMul https://github.com/purescript/purescript-prelude/blob/v4.1.0/src/Data/Semiring.js#L10 to be the defaulted polyfill that @hdgarrood posted?
exports.imul = Math.imul || function(a, b) {
var ah = (a >>> 16) & 0xffff;
var al = a & 0xffff;
var bh = (b >>> 16) & 0xffff;
var bl = b & 0xffff;
// the shift by 0 fixes the sign on the high part
// the final |0 converts the unsigned value into a signed value
return ((al * bl) + (((ah * bl + al * bh) << 16) >>> 0)|0);
};
foreign import imul :: Fn2 Int Int Int
instance semiringInt :: Semiring Int where
add = intAdd
zero = 0
mul = runFn2 imul
one = 1
Ah sorry @hdgarrood, I didn't read your latest comment properly, you already suggested that ^
I guess we would inline from x * y to runFn2 imul x y?
and then delete it when we get better elimination of dictionaries
That sounds like quite the deoptimization for quite a lot of simple numeric code.
I've set up a jsperf (https://jsperf.com/imul-or-mul). Unless it's a bad test, I get unexpectedly comparable performance between the following on Chrome:
(x * y) | 0
((x | 0) * (y | 0)) | 0
Math.imul(x | 0, y | 0) | 0
imulPolyfill(x | 0, y | 0) | 0
And on Firefox, all of the cases have comparable performance to the best of Chrome.
Perhaps a slightly better structure of test? https://jsperf.com/mul-imul-poly-2
But yeah, under the assumption that any of these tests are useful, it seems to me that imulPolyfill(x | 0, y | 0) | 0 would be an acceptable choice of implementation.
There's an alternative implementation from MDN (and of course we are not mutating Math; this is just verbatim):
if (!Math.imul) Math.imul = function(opA, opB) {
opB |= 0; // ensure that opB is an integer. opA will automatically be coerced.
// floating points give us 53 bits of precision to work with plus 1 sign bit
// automatically handled for our convienence:
// 1. 0x003fffff /*opA & 0x000fffff*/ * 0x7fffffff /*opB*/ = 0x1fffff7fc00001
// 0x1fffff7fc00001 < Number.MAX_SAFE_INTEGER /*0x1fffffffffffff*/
var result = (opA & 0x003fffff) * opB;
// 2. We can remove an integer coersion from the statement above because:
// 0x1fffff7fc00001 + 0xffc00000 = 0x1fffffff800001
// 0x1fffffff800001 < Number.MAX_SAFE_INTEGER /*0x1fffffffffffff*/
if (opA & 0xffc00000 /*!== 0*/) result += (opA & 0xffc00000) * opB |0;
return result |0;
};
Those polyfills would basically only target IE, and its JScript engine wouldn't perform any better than this on the more widely known one unless the engine has any optimizations for integer arithmetic, which seems unlikely.
@LiamGoodacre I think the Math.imul option needs to be reevaluated with a correction to fetch the imul property and store it in a closure beforehand, pulling the property get overhead out of the loop. And it's what we're going to do anyway, since that way the mul function in the Semiring Int instance would preserve its referential transparency even if Math.imul is later set to any other value. That is, assuming the property is kept its initial value upon PureScript's runtime initialization.
Is there anything to resolve here? I think we should make a decision one way or the other.
I think we should definitely fix Int multiplication one way or another. My preference is this:
One alternative option that has just occurred to me is that we change the definition of intMul so that it uses Math.imul via the FFI if it is there, or otherwise it uses a polyfill, but whichever path is taken, it should be done without mutating window.Math. See this PR for how we might achieve that (thanks matthewleon). Then, we'd need to improve the inliner so that this could be inlined properly (i.e. by generating a require statement if necessary). I think this would be my preferred option, although I'm not sure how difficult modifying the inliner would be.