Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

[js] Undefined values when iterating over IntMap when keys are larger than the max signed 32 bit integer #10316

Closed
theJenix opened this issue Jul 12, 2021 · 5 comments
Closed

[js] Undefined values when iterating over IntMap when keys are larger than the max signed 32 bit integer #10316

theJenix opened this issue Jul 12, 2021 · 5 comments
Labels
platform-javascript Everything related to JS / JavaScript
Milestone
4.2 Hotfix

Comments

@theJenix
Copy link
Contributor

I'm actually not sure where the real issue is here, but the symptom is that if a IntMap contains a key that is larger in value than 2147483647, when iterating over that map, the value will be undefined.

Code

Main.hx:

class Main {
    static function main() {
        final map = new Map<Int,Int>();
        final largeKey:Int = 2147483647 + 1; // 2^31, computed
        trace(largeKey);

        map[largeKey] = largeKey;

        for (k => v in map) {
            trace('${k} => ${v}');
        }
    }
}

index.html:

<!doctype html><html><body><script src="main.js"></script></body></html>

Compile with: haxe Main.hx -js main.js --main Main and open index.html in a browser. The console output will be:

Main.hx:7: 2147483648
Main.hx:12: -2147483648 => undefined

What appears to be going on is: the key/value iteration iterates over the keys in a JavaScript object that is used to hold the IntMap data, and the generated code uses key | 0 to convert the object key to a number. The problem is that bitwise operators like | will convert the value to a 32 bit integer (see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Bitwise_OR), which in this case is different than the key stored in the map. This causes a subsequent call to map.get to fail, which results in the undefined value.

In the code above, I had to add 2147483647 + 1 to show this error. If I just declared final largeKey = 2147483648 the Haxe compiler would complain that Float should be Int, but it let me add numbers to create larger integers (as done here). So it's also possible that the issue here is not the use of | 0 to convert object keys to numbers, but rather that all of that was designed assuming that a positive integer key would never exceed 2147483647. This is why I said above that I'm not sure where the real issue lies. The Haxe library docs are not very clear on what the precision of an Int should be (only that it is platform specific).

For what it's worth, Javascript's number type represents a 64 bit double value which does not hold a full 64 bit integer, so I think it would be reasonable to restrict integer precision to 32 bits but if that's the case the Haxe language/compiler should probably overflow in a consistent way (e.g. 2147483647 + 1 should result in -2147483648, or emit the same compiler error I mentioned above). Or, it would be reasonable to support "native precision" integers (which is ~ 2^53) but then the compiler error and the use of | 0 are probably not right.
@back2dos
Copy link
Member

Hmm, I'm beginning to wonder if #10179 wasn't such a bad idea after all.

That said, this particular issue would also go away by switching to native maps (via #10290 or something).

@RealyUniqueName
Copy link
Member

I think this is ok. We can only guarantee IntMap to behave correctly across targets for 32bits.
If anything we need Int64Map.

@back2dos
Copy link
Member

We can only guarantee IntMap to behave correctly across targets for 32bits.

The name IntMap (as opposed to Int32Map) implies that all Ints are valid keys. Defining just what those are in the documentation would arguably close the gap.

That said, the issue is slight different. On all other platforms, the ints either overflow or not. The map will handle the resulting values consistently.

The discrepancy observed on JS is caused directly by the implementation's key | 0 business, so perhaps that's worth reconsidering. We could use +key or Number(key) instead, and a benchmark would suggest similar performance for the former:

Chrome (and Edge) 91

  "x | 0" took 0.007006000000238417s
  "+x" took 0.004476000000238418s
  "Number(x)" took 0.0044060000002384215s

Safari 14

  "x | 0" took 0.05806000000000001s
  "+x" took 0.04564s
  "Number(x)" took 0.05169999999999998s

Firefox 89

  "x | 0" took 0.029979999999999993s
  "+x" took 0.03548s
  "Number(x)" took 0.05065999999999999s

@RealyUniqueName RealyUniqueName added this to the Hotfix milestone Jul 13, 2021
@RealyUniqueName RealyUniqueName added the platform-javascript Everything related to JS / JavaScript label Jul 13, 2021
RealyUniqueName added a commit that referenced this issue Jul 13, 2021
@RealyUniqueName
[js] use +key instead of key | 0 in IntMap (fixes #10316)
a7ef93d
@theJenix
Copy link
Contributor Author

Wow that was fast, thanks! It does look like | 0 is used in other places; it actually looks like Std.int(x) might compile down to x | 0 on Javascript, which means I think the same issue potentially arises for:

final x = 2147483648;
trace(Std.int(x) == x); // prints false

Should I open another ticket for that? Or should that be fixed as part of this ticket?

@back2dos
Copy link
Member

That's a different matter. While the signature of Std.int could be interpreted the way you expect, the spec clearly states it is undefined outside the signed 32bit int range (because its focus is on speed).

You can propose to move the Haxe implementation to Math.floor, which when put in the above benchmark seems to be ~20% faster on V8, but ~50% slower on SpiderMonkey (so arguably on a planetary scale it will result in a net speedup :D). Whether or not it'll be accepted, I can't tell. Should you feel strongly about altering undefined behavior on a specific target, you can always try ;)

If you need runtime conversion from float to int beyond the supported range, you can use Math.floor (or round / ceil), which in Haxe returns ints (a mere compile time distinction when targeting JS).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
platform-javascript Everything related to JS / JavaScript
Projects
None yet
Milestone
4.2 Hotfix
Development

No branches or pull requests
3 participants
@back2dos @theJenix @RealyUniqueName