Bug 265554 – REGRESSION(267629@main): create_hash_table script runs forever on i686

• Component: JavaScriptCore
• Status: RESOLVED FIXED

[Michael Catanzaro]

I'm investigating a regression where the create-hash-table script runs forever on i686 GNOME OS. It works fine on i686 Fedora, so something weird is going on.

This is most likely caused by 267532@main, although I still need to confirm this and figure out what exactly is going wrong.

[Radar WebKit Bug Importer]

<rdar://problem/119280476>

[Michael Catanzaro]

OK, I needed a lot of help to get a working edit/compile/test environment for this architecture, but finally some progress to report! The problem is the call to calcPerfectHashSize in generateHashTableHelper runs forever. Now to figure out why.

[Michael Catanzaro]

The size just keeps increasing. Here's the toplevel loop in calcPerfectHashSize:

Outer loop: perfect hash size=64
Outer loop: perfect hash size=128
Outer loop: perfect hash size=256
Outer loop: perfect hash size=512
Outer loop: perfect hash size=1024
Outer loop: perfect hash size=2048
Outer loop: perfect hash size=4096
Outer loop: perfect hash size=8192
Outer loop: perfect hash size=16384
Outer loop: perfect hash size=32768
Outer loop: perfect hash size=65536
Outer loop: perfect hash size=131072
Outer loop: perfect hash size=262144
Outer loop: perfect hash size=524288
Outer loop: perfect hash size=1048576
Outer loop: perfect hash size=2097152
Outer loop: perfect hash size=4194304
Outer loop: perfect hash size=8388608
Outer loop: perfect hash size=16777216
Outer loop: perfect hash size=33554432
Outer loop: perfect hash size=67108864
Outer loop: perfect hash size=134217728
Outer loop: perfect hash size=268435456
Outer loop: perfect hash size=536870912
Outer loop: perfect hash size=1073741824
Outer loop: perfect hash size=2147483648
Outer loop: perfect hash size=4294967296
Outer loop: perfect hash size=8589934592
Outer loop: perfect hash size=17179869184
Outer loop: perfect hash size=34359738368
Outer loop: perfect hash size=68719476736
Outer loop: perfect hash size=137438953472
Outer loop: perfect hash size=274877906944
Outer loop: perfect hash size=549755813888
Outer loop: perfect hash size=1099511627776
Outer loop: perfect hash size=2199023255552
Outer loop: perfect hash size=4398046511104
Outer loop: perfect hash size=8796093022208
Outer loop: perfect hash size=17592186044416
Outer loop: perfect hash size=35184372088832
Outer loop: perfect hash size=70368744177664
Outer loop: perfect hash size=140737488355328
Outer loop: perfect hash size=281474976710656
Outer loop: perfect hash size=562949953421312
Outer loop: perfect hash size=1.12589990684262e+15
Outer loop: perfect hash size=2.25179981368525e+15
Outer loop: perfect hash size=4.5035996273705e+15
Outer loop: perfect hash size=9.00719925474099e+15
Outer loop: perfect hash size=1.8014398509482e+16
Outer loop: perfect hash size=3.6028797018964e+16
Outer loop: perfect hash size=7.20575940379279e+16
Outer loop: perfect hash size=1.44115188075856e+17
Outer loop: perfect hash size=2.88230376151712e+17
Outer loop: perfect hash size=5.76460752303423e+17
Outer loop: perfect hash size=1.15292150460685e+18

And so on. The size just keeps getting larger.

(Notably, none of this work seems to be needed, since the script knows it is not building for macOS, but it's generating the macOS-only code anyway.)

[Michael Catanzaro]

I sabotaged the hashValue function to always call superFastHash rather than the new wyhash, expecting this to fix the problem, but actually no! This didn't make any difference and the script continues to run forever; the size actually reaches infinity. This is unexpected because wyhash is the new thing, but I suppose something went wrong in the adjustments made to superFastHash.

[Michael Catanzaro]

The problem is in avalancheBits. Somehow changing from % $EXP2_32 to & $mask32 there has broken things, although they *seem* like two different ways to do exactly the same thing. I don't know for sure what is wrong, but I have a guess. The original code declares:

my $EXP2_32 = 4294967296;

which is 2^32 + 1, one larger than the largest value that can be represented in a 32-bit integer. I think this means perl cannot represent the number as an integer and must switch to either floating point or decimal representation. I've looked over https://perldoc.perl.org/perlnumber but am not sure which.

Anyway, although I don't fully understand what is wrong, at least now I know how to unbreak the build.

[Michael Catanzaro]

(In reply to Michael Catanzaro from comment #0)
> This is most likely caused by 267532@main, although I still need to confirm
> this and figure out what exactly is going wrong.

So Fedora and Debian both build perl using lots of custom configure flags, notably -Duse64bitint [1][2]. freedesktop-sdk (used by gnome-build-meta) has a much simpler configuration lacking this flag [3]. I don't know for sure that this is to blame, but it sure does seem extremely suspicious, so I'm going to test and find out!

[1] https://src.fedoraproject.org/rpms/perl/blob/b26fbaf78a425b0e5db3701c55e29bbc7e4b146d/f/perl.spec#_4393
[2] http://deb.debian.org/debian/pool/main/p/perl/perl_5.36.0-7.debian.tar.xz containing config.debian
[3] https://gitlab.com/freedesktop-sdk/freedesktop-sdk/-/blob/f41d6422547acca4dee3b190410162011dc640ae/elements/components/perl.bst

[Michael Catanzaro]

(In reply to Michael Catanzaro from comment #3)
> (Notably, none of this work seems to be needed, since the script knows it is
> not building for macOS, but it's generating the macOS-only code anyway.)

(Correction: the script actually does not know what OS it is building for. An Apple developer would need to modify the DerivedSources.make to pass a new arg to the script. Probably isn't worth the effort.)

[Michael Catanzaro]

Cross-reference: https://gitlab.gnome.org/GNOME/gnome-build-meta/-/merge_requests/2537/

[Mark Lam]

Michael, on my macOS build, the highest value that `pefectHashSize` ever reaches is 2048.  I suggest you compare your run on i686 GNOME OS against the run on i686 Fedora, and see where things diverge.

[Michael Catanzaro]

(In reply to Mark Lam from comment #9)
> Michael, on my macOS build, the highest value that `pefectHashSize` ever
> reaches is 2048.  I suggest you compare your run on i686 GNOME OS against
> the run on i686 Fedora, and see where things diverge.

Basically the mask operations in avalancheBits are not working as intended (comment #5). I think that's because they expect the hash to be an integer, but it's not an integer anymore.

However, this script uses bigint [1] which is specifically designed to avoid this problem. I suspect I may have broken this myself in 267629@main because the syntax I used to avoid the build failure does not match the import syntax suggested by [1]. So now I want to figure out how to revert 267629@main without reintroducing bug #261150.

I also want to add a guard to calcPerfectHashSize to bail out if the hash size reaches an unreasonable value.

[1] https://perldoc.perl.org/bigint

[Michael Catanzaro]

Problem is https://perldoc.perl.org/Math::BigInt and https://perldoc.perl.org/bigint are different perl modules that have confusingly-similar names.

[Michael Catanzaro]

Pull request: https://github.com/WebKit/WebKit/pull/21503

[EWS]

Committed 271765@main (08395c362d95): <https://commits.webkit.org/271765@main>

Reviewed commits have been landed. Closing PR #21503 and removing active labels.