Very high processing difference between two almost similar while loops

Question

I'm writing a function that draws an image to a canvas element pixel by pixel. I noticed that there was a point, where the function suddenly took way longer to process than before - specifically going from a 338x338 pixel canvas to a 339x339 pixel canvas.

Putting a similar looking function into jsfiddle, I get the same result. The while loop processing an array of 338x338 takes approx. 6-7 seconds, while an array of 339x339 takes approx. 24-25 seconds.

This is happening on Chrome. In Firefox both takes approx. 16 seconds.

Here is the fiddle: http://jsfiddle.net/8pb89/5/

The code looks like this:

var ary1 = [];
var ary2 = [];
var mapData = {};
var colorMatrix = {};

for (var i = 0; i < (338 * 338); i++) {
    ary1.push([i, i + 2]);
}

for (var i = 0; i < (339 * 339); i++) {
    ary2.push([i, i + 2]);
}

//Light operation
function test(i, j) {
    return Math.floor((i * j + i + j) / j);
}

//Heavy operation on objects
function calcTest(ary){
    var point = ary.splice(0, 1);
    var i = point[0];
    var j = point[1];

    if (!mapData[i]) {
        mapData[i] = [];
    }
    if (!mapData[i][j]) {
        mapData[i][j] = [];
    }

    mapData[i][j]["one"] = test(i, j);
    mapData[i][j]["two"] = test(i, j);

    colorMatrix[mapData[i][j]["two"]] = mapData[i][j]["one"];

}

var len = ary1.length;
var start = new Date().getTime();

while (len--) {
    calcTest(ary1);
}

var end = new Date().getTime();
var time = end - start;
alert('Execution for 338x338: ' + time);

var len2 = ary2.length;
obj = {};
obj2 = {};

start = new Date().getTime();
while (len2--) {
    calcTest(ary2);
}
end = new Date().getTime();
time = end - start;
alert('Execution for 339x339: ' + time);

Is this a memory issue with javascript on Chrome, or am I doing something wrong with the objects? Is there a way to avoid this higher processing duration?

Answer 1

I would guess that it's one or both of the following.

• Chrome is resizing the underlying hashtable somewhere between 338 * 338 and 339 * 339.
• Garbage collection is happening in the same timeframe.

I doubt this is a memory issue.

Answer 2

Consider what your SPLICE operation is actually doing. Let's run through splicing this array:

[0,1,2,3,4,5]

I'd have to:

STORE the 0
READ the 1, WRITE to where the 0 was
READ the 2, WRITE to where the 1 was
READ the 3, WRITE to where the 2 was
READ the 4, WRITE to where the 3 was
READ the 5, WRITE to where the 4 was
DELETE the 5

that's 12 operations (on an array that's 6 items big)... your arrays are much, much bigger (over 100k items)... and you're iterating through them, whittling them down as you go. I make that about 26 billion calculations you're requesting in your code!!!

I have re-factored your code to put the while loop inside the test and NOT use the SPLICE function - I now get the tests down to 23ms and 25ms on my machine (achieving the same result as your tests)... your example took 3599ms and 19464ms - that's nearly 500 times more efficient :)

You have many other issues with this code, but this gets to the heart of your biggest problem!

var ary1 = [];
var ary2 = [];
var mapData = {};
var colorMatrix = {};

for (var i = 0; i < (338 * 338); i++) {
    ary1.push([i, i + 2]);
}

for (var i = 0; i < (339 * 339); i++) {
    ary2.push([i, i + 2]);
}

//Light operation
function test(i, j) {
    return Math.floor((i * j + i + j) / j);
}

//Heavy operation on objects
function calcTest(ary){
    for (index=ary.length-1;index>=0;index--){
        var point=ary[index];

        var i = point[0];
        var j = point[1];

        if (!mapData[i]) {
            mapData[i] = [];
        }
        if (!mapData[i][j]) {
            mapData[i][j] = [];
        }

        mapData[i][j]["one"] = test(i, j);
        mapData[i][j]["two"] = test(i, j);

        colorMatrix[mapData[i][j]["two"]] = mapData[i][j]["one"];
    }
}

//I'm only putting the following lines in first to show that the first
//Operation takes longer by populating the mapData and colorMatrix arrays
//If you delete the next two lines you'll find that the 339 option takes
//less time than the 338 (because it's going second!)
calcTest(ary1);
calcTest(ary2);

var start = new Date().getTime();
calcTest(ary1);
var end = new Date().getTime();
var time = end - start;
alert('Execution for 338x338: ' + time);

start = new Date().getTime();
calcTest(ary2);
end = new Date().getTime();
time = end - start;
alert('Execution for 339x339: ' + time);