Array size 114467 good, 114468 not work

Question

I have a strange problem with my alghoritm, which work if array size less than 114468 and doesn't work if more than 114468. Browse with google chrome. Can't understand why =\ Here is the code:

Generate array:

    var arr = [];
    var res = [];
    for (var i = 114467; i > 0; i--) {
        arr.push([i - 1, i]);
    }

Find first elem in array to sort:

        for (var i = 0, j = arr.length; i < j && res.length == 0; i++) {
            var found = false;
            for (var m = 0; m < j; m++) {
                if (i == m || arr[i][0] == arr[m][1] || arr[i][1] == arr[m][0]) {
                    found = true;
                    break;
                }

                if (!found) {
                    res.push(arr[m]);
                    arr.splice(m, 1);
                }
            }
        }

Sorting:

        do {
            for (var i = 0, j = arr.length; i < j; i++) {
                var resLength = res.length - 1;
                if (arr[i][1] == res[resLength][0] || arr[i][0] == res[resLength][1]) {
                    res.push(arr[i]);
                    arr.splice(i, 1);
                    break;
                }
            }
        } while (arr.length > 0);

On the step sorting it stops to work.

All code:

var t = function () {
    var arr = [];
    var res = [];
    for (var i = 114467; i > 0; i--) {
        arr.push([i - 1, i]);
    }

    var startsec = new Date().getSeconds();
    var startmilsec = new Date().getMilliseconds();
    document.write(startsec + '.' + startmilsec + '<br>');

    for (var i = 0, j = arr.length; i < j && res.length == 0; i++) {
        var found = false;
        for (var m = 0; m < j; m++) {
            if (i == m || arr[i][0] == arr[m][1] || arr[i][1] == arr[m][0]) {
                found = true;
                break;
            }

            if (!found) {
                res.push(arr[m]);
                arr.splice(m, 1);
            }
        }
    }

    do {
        for (var i = 0, j = arr.length; i < j; i++) {
            var resLength = res.length - 1;
            if (arr[i][1] == res[resLength][0] || arr[i][0] == res[resLength][1]) {
                res.push(arr[i]);
                arr.splice(i, 1);
                break;
            }
        }
    } while (arr.length > 0);

    var stopsec = new Date().getSeconds();
    var stopmilsec = new Date().getMilliseconds();
    document.write(stopsec + '.' + stopmilsec + '<br>');
    var executionTime = (stopsec - startsec).toString() + "s" + (stopmilsec - startmilsec).toString() + "'ms";
    document.write(executionTime + '<br>');
} ();

Do i get my memory limit?

Answer 1

Alright, I isolated the problem. It seems that splice(0,1) slows down astronomically when the array size increases from 114467 to 114468.

Using this custom benchmark:

var t;
function startBench(){t=new Date().getTime();}
function stopBench(){console.log(new Date().getTime()-t);}
var arr=[];
    for (var i = 114467; i > 0; i--) {
        arr.push([i - 1, i]);
    }
var arr2=[];
    for (var i = 114468; i > 0; i--) {
        arr2.push([i - 1, i]);
    }
startBench();
for(i=0;i<1000;i++){
arr.splice(0,1);
}

stopBench();
startBench();
for(i=0;i<1000;i++){
arr2.splice(0,1);
}
stopBench();

I get 3 ms for 114467 and 2740ms for 114468 on Chrome (1000 iterations), but 170 each on Firefox. Maybe you ought to be using a different way to remove elements? Using a variant of bubble sort may work better.

I've submitted a bug report on this. Looking at the reply, it seems to be a valid bug. Hopefully it'll be fixed.