1543055 - AllocationSiteKey hashing can cause quadratic behavior

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Jan de Mooij [:jandem]]

The testcase below runs in 42 ms. Now if you change |var x = i| to |var x = 0|, we hit a terrible perf cliff and it takes > 6700 ms.

What's happening is that AllocationSiteKey::hash uses the bytecode pc but AllocationSiteKey::match uses script + offset. This breaks down when a ton of scripts use the same underlying bytecode because they'll all have the same hash.

Noticed this while looking into bug 1542995.

---

function test() {
    var arr = [];
    for (var i = 0; i < 50000; i++) {
        var x = i;
        var f = Function("return [Math, " + x + "]");
        arr.push(f);
    }
    var t = new Date;
    for (var i = 0; i < arr.length; i++) {
        arr[i]();
    }
    print(new Date - t);
}
test();

Comment 1

[Jan de Mooij [:jandem]]

Attachment: Bug 1543055 - Fix AllocationSiteKey hashing to not have quadratic behavior when many scripts share bytecode. r?jonco!

This also uses HashGeneric/AddToHash instead of manual XOR'ing.

Comment 2

[Jon Coppeard (:jonco)]

As suggested on IRC, it might make sense to give every script a unique ID if this operation is common, and save adding/looking one up in the unique ID hash table.

Comment 3

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/21ee37c5b888
Fix AllocationSiteKey hashing to not have quadratic behavior when many scripts share bytecode. r=jonco

Comment 4

[Stefan Hindli [:stefan_hindli]]

https://hg.mozilla.org/mozilla-central/rev/21ee37c5b888