AllocationSiteKey hashing can cause quadratic behavior

RESOLVED FIXED in Firefox 68

Status

()

defect
RESOLVED FIXED
3 months ago
2 months ago

People

(Reporter: jandem, Assigned: jandem)

Tracking

(Blocks 1 bug)

unspecified
mozilla68
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(firefox68 fixed)

Details

Attachments

(1 attachment)

Assignee

Description

3 months ago

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();
Assignee

Updated

3 months ago
Type: task → defect
Assignee

Comment 1

3 months ago

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

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

3 months ago
Pushed by jdemooij@mozilla.com:
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

2 months ago
bugherder
Status: ASSIGNED → RESOLVED
Closed: 2 months ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla68
You need to log in before you can comment on or make changes to this bug.