node.js splice too slow for more than 70000 items

user_6128012 0
Viewed 662

I am newbie in node.js.

i tried to insert 70000 items into array , and then delete all of them:

var Stopwatch = require("node-stopwatch").Stopwatch;
var stopwatch = Stopwatch.create();


var a = []
stopwatch.start();

for (var i = 1 ; i < 70000 ; i++){
    a.push((parseInt(Math.random() * 10000)) + "test");
}

for (var i = 1 ; i < 70000 ; i++){
    a.splice(0,1);
}

stopwatch.stop();

console.log("End: " + stopwatch.elapsedMilliseconds + " : " + a.length);

It works fine and output is:

PS C:\Users\Documents\VSCode> node test.js
End: 51 : 0

But when i increase number of items to 72000 , it takes too much time to end:

var Stopwatch = require("node-stopwatch").Stopwatch;
var stopwatch = Stopwatch.create();


var a = []
stopwatch.start();

for (var i = 1 ; i < 72000 ; i++){
    a.push((parseInt(Math.random() * 10000)) + "test");
}

for (var i = 1 ; i < 72000 ; i++){
    a.splice(0,1);
}

stopwatch.stop();

console.log("End: " + stopwatch.elapsedMilliseconds + " : " + a.length);

And the output is:

End: 9554 : 0

Why it occurs? only 2000 items added more , but it takes too much time.

Node.js version is: v6.11.3

v8 node.js arrays
2 Answers

V8 developer here. Removing (or inserting) array elements at the start (at array[0]) is generally very expensive, because all the remaining elements have to be moved. Essentially, what the engine has to do under the hood for every one of these .splice(0, 1) operations is:

for (var j = 0; j < a.length - 1; j++) {
  a[j] = a[j+1];
}
a.length = a.length - 1`

In some cases, V8 can employ a trick under the hood where the beginning of the object is moved instead -- in the fast cases, you can see the amazing speedup that this trick provides. However, for technical reasons, this trick cannot be applied for arrays beyond a certain size. The resulting "slowdown" is actually the "true" speed of this very expensive operation.

If you want to delete array elements fast, delete them from the end (at array[array.length - 1]), e.g. using Array.pop(). If you want to delete all elements in one go, just set array.length = 0. If you need fast FIFO/"queue" semantics, consider taking inspiration from ring buffers: have a "cursor" for the next element to be read/returned, and only shrink the array when there's a big chunk of elements to be freed up. Roughly:

function Queue() {
  this.enqueue = function(x) {
    this.array_.push(x);
  }
  this.dequeue = function() {
    var x = this.array_[this.cursor_++];
    // Free up space if half the array is unused.
    if (this.cursor_ > this.array_.length / 2) {
      this.array_.splice(0, this.cursor_);
      this.cursor_ = 0;
    }
    return x;
  }
  this.array_ = [];
  this.cursor_ = 0;
}

Side note: It doesn't matter here, but for the record, to push 70,000 elements into your array, your loop should start at 0: for (var i = 0; i < 70000; i++) {...}. As written, you're only pushing 69,999 elements.

Side note 2: Rounding a double to an integer via "parseInt" is pretty slow, because it first formats the double as a string, then reads that string back as an integer. A faster way would be Math.floor(Math.random() * 10000)). (For the purposes of this test, you could also simply push i.)

user_60364280

Interesting, I did something like

if (i % 1000 === 0) {
    console.log(i + " " + stopwatch.elapsedMilliseconds + " : " + a.length);
}

inside the 2nd loop. (This is painfull to compute, but it will help diagnose the problem)

I was not suffer the performance loss. But, I think, that I found why "only" 2000 more things to do is that hard for node. First - my difference: [loop max num, unit, 3 benchmarks results]

70k: [ms] ~26k, ~25.7k, ~26k 72k: [ms] ~25.6k, 27k, 25.7k

Okay, as I saw the logging, I seen that, the last 10k records are computed like instant. I think that splice removes 1 item from the front, and then - one by one it shifts array 1 index "to the start", let's change our test to 10 arrays every with 10k records to see if it will be much better. I will do this in the most lazy way:

var Stopwatch = require("node-stopwatch").Stopwatch;
var stopwatch = Stopwatch.create();

var a1 = [], a2 = [], a3 = [], a4 = [], a5 = [];
var a6 = [], a7 = [], a8 = [], a9 = [], a10 = [];

stopwatch.start();

function fill (arr) {
    for (var i = 1 ; i < 10000 ; i++){
        arr.push((parseInt(Math.random() * 10000)) + "test");
    }
}

fill(a1); fill(a2); fill(a3); fill(a4); fill(a5);
fill(a6); fill(a7); fill(a8); fill(a9); fill(a10);

let removeCount = 0;
function unfill(arr) {
    for (var i = 1 ; i < 10000 ; i++){
        arr.splice(0,1);
        removeCount++;

        if (i % 1000 === 0) {
            console.log(i + " " + stopwatch.elapsedMilliseconds + " : " + arr.length);
        }
    }
}

unfill(a1); unfill(a2); unfill(a3); unfill(a4); unfill(a5);
unfill(a6); unfill(a7); unfill(a8); unfill(a9); unfill(a10);

stopwatch.stop();

console.log("End: " + stopwatch.elapsedMilliseconds + " removeCount " + removeCount);

And, yes... I did not answered why exacly your pc have such performance loss between 70k and 72k records - I belive it is something machine dependant... probably lack of RAM, but don't get it wrong - I don't know.

I solved how to improve that. The 100k(-10) on 10 arrays execution time was around 73-74 ms. I think, you can write it into 2d array and modify logic to compute length and rest of things as you want.

Thanks for attention.

user_56942060
Related