1513702 - Array.shift is slower than it should be

Status: REOPENED

(Core :: JavaScript Engine, defect, P3)

Description

[Jim Blandy :jimb]

Attachment: microbenchmark comparing indexing with Array.shift

Processing an array with repeated calls to Array.shift is substantially slower than processing it with a for loop over the indices. In the attached microbenchmark, I got a 2.6x slowdown (of course, the exact number is not too meaningful).

Debugger.html recently landed some changes that use Array.shift to process a large array, and saw an 800% performance regression.

Maybe this is just a WONTFIX, but given that Array.shift on the fast path is just moving a pointer, it seems like there might be something surprising going on here.

Comment 1

[Jan de Mooij [:jandem]]

We could make this faster, maybe by inlining more in JIT code, but ultimately shift has to do GC barrier stuff and involves various memory writes. Using indexing OTOH is just a single load that's trivial to inline completely by the JITs.

Also, when I optimized shift last year, bug 1348772, we were on par with other browsers. Before that bug this would have been way, way slower even.

Comment 2

[Jim Blandy :jimb]

As long as the status is known, this is fine.

Comment 3

[Jan de Mooij [:jandem]]

Actually this testcase is not representative of what was happening in bug 1513737. The problem is that MaybeInIteration was returning true. We should probably optimize this more to avoid bad cliffs like this.

Comment 4

[Jim Blandy :jimb]

Sorry, I don't understand: is MaybeInIteration returning true spuriously in the test case attached to this bug? If not, do we have a reduced test case that does cause it to return true spuriously?

Comment 5

[Jan de Mooij [:jandem]]

See the testcase below. It takes > 4100 ms but commenting out the empty loop I marked improves it to 1 ms.

I'm not sure what the best fix is - ObjectRealm::objectMaybeInIteration should probably support more than just the "single object" case, but to fix the cliff completely we may want some kind of hash table, however that doesn't work well with the JIT inlined iterator code.

function f() {
    var a = [];
    for (var x in a) {}  // <------
    for (var i = 0; i < 20000; i++) {
        a.push(i);
    }
    var t = new Date;
    for (var x1 in [1]) {
        for (var x2 in [1]) {
            while (a.length > 0) {
                a.shift();
            }
        }
    }
    print(new Date - t);
}
f();