CODEWITHSUNDEEP
javascriptarraysperformance
dev1223
dev1223

Reputation: 1159

Array slow elements removal

I have array and I want to remove N elements from its head.

Lets say, array (with floats) has 1M elements and I want first 500K to go out. I have two ways, call shift 500K times in loop or call splice(0,500000).

The thing is, first solution is horrible idea (it's very very slow). Second is slow too because splice returns removed part from array in a new array (well, it just allocate 500K floats and throw them out of window).

In my app, I'm doing some things with really big matrices, and unfortunately, elements removal via splice is slow for me. Is there some faster way how to achieve it?

Upvotes: 4

Views: 395

Answers (2)

T.J. Crowder
T.J. Crowder

Reputation: 1075635

I would expect that Array#slice would be at least as fast as either of those options and probably faster. It does mean temporarily allocating duplicated memory, but 1M numbers is only about 64MB of memory (assuming the JavaScript engine has been able to use a true array under the covers), so temporarily having the original 64MB plus the 32MB for the ones you want to keep before releasing the original 64MB seems fairly cheap:

array = array.slice(500000);

This also has the advantage that it won't force the JavaScript engine into using an object rather than an array under the covers. (Other things you're doing may cause that, but...)

You've said you're doing this with floats, you might look at using Float64Array rather than untyped arrays. That limits the operations you can perform, but ensures that you don't end up with unoptimized arrays. When you delete entries from arrays, you can end up with unoptimized arrays with markedly slower access times than optimized arrays, as they end up being objects with named properties rather than offset accesses. (A good JavaScript engine will keep them optimized if it can; using typed arrays would help prevent you from blowing its optimizations.)

This (dashed off and quite certainly flawed) NodeJS test suggests that splice is anywhere from 60% to 95% slower than slice, and that V8 does a great job keeping the array optimized as the result for the typed array is virtually identical to the result for the untyped array in the slice case:

"use strict";
let sliceStats = createStats();
let sliceTypedStats = createStats();
let spliceStats = createStats();
for (let c = 0; c < 100; ++c) {
    if (test(buildUntyped, sliceStats, testSlice).length != 500000) throw new Error("1");
    if (test(buildTyped, sliceTypedStats, testSlice).length != 500000) throw new Error("2");
    if (test(buildUntyped, spliceStats, testSplice).length != 500000) throw new Error("3");
    console.log(c);
}
console.log("slice     ", avg(sliceStats.sum, sliceStats.count));
console.log("sliceTyped", avg(sliceTypedStats.sum, sliceTypedStats.count));
console.log("splice    ", avg(spliceStats.sum, spliceStats.count));

function avg(sum, count) {
    return (sum / count).toFixed(3);
}

function createStats() {
    return {
        count: 0,
        sum:   0
    };
}
function buildUntyped() {
    let a = [];
    for (let n = 0; n < 1000000; ++n) {
        a[n] = Math.random();
    }
    return a;
}

function buildTyped() {
    let a = new Float64Array(1000000);
    for (let n = 0; n < 1000000; ++n) {
        a[n] = Math.random();
    }
    return a;
}

function test(build, stats, f) {
    let a;
    let ignore = 0;
    let start = Date.now();
    for (let i = 0; i < 10; ++i) {
        let s = Date.now();
        a = build();
        ignore += Date.now() - s;
        a = f(a);
    }
    stats.sum += Date.now() - start - ignore;
    ++stats.count;
    return a;
}

function testSlice(a) {
    return a.slice(500000);
}
function testSplice(a) {
    a.splice(0, 500000);
    return a;
}

Upvotes: 2

Daniel Schmidt
Daniel Schmidt

Reputation: 11921

Immutable.js solves this problem by structural sharing. It does not copy the entries as splice would do but returns a reference on the included parts of the array. You would need to move your array to the Immutable.js data structure and then call the immutable operation splice.

Upvotes: 1

Related Questions