Weird Codility timeout error: DisappearingPairs

I solved the Codility task DisappearingPairs(https://app.codility.com/programmers/trainings/4/disappearing_pairs/) in two ways, each is O(n) time complexity.

Solution 1:

function solution(S) {
    const chars = [...S];
    let i = 1;

    while (i < chars.length) {
        while (i > 0 && i < chars.length && chars[i - 1] === chars[i]) {
            chars.splice(i - 1, 2);
            i--;
        }
        i++;
    }

    return chars.join('');
}

Solution 2:

function solution(S) {
    const result = [];

    for (const ch of S) {
        const {length} = result;
        if (length === 0 || ch !== result[length - 1])  {
            result.push(ch);
        } else {
            result.splice(length - 1, 1);
        }
    }

    return result.join('');
}

The first solution fails performance tests and the second doesn't. Why does the first one fails even it is also efficient?

I tried adding a test case like max_C(a string with length 50,000 with letters C only) taken from their performance tests(the test-input file doesn't allow a long input like this so added it in the code):

function solution(S) {
    console.time('repeat')
    if (S === 'C') {
        S = S.repeat(50000);
    }
    console.timeEnd('repeat')
    // Implement your solution here
    console.time('restOperator')
    const chars = [...S];
    let i = 1;
    console.timeEnd('restOperator')

    console.time('while')
    while (i < chars.length) {
        while (i > 0 && i < chars.length && chars[i - 1] === chars[i]) {
            chars.splice(i - 1, 2);
            i--;
        }
        i++;
    }
    console.timeEnd('while')

    console.time('join')
    const result = chars.join('');
    console.timeEnd('join')
    return result;
}

The results are(varying between runs):

repeat: 0.066ms
restOperator: 1.564ms
while: 3.668s
join: 0.005ms

I noticed the issue is in the while loop. I tested the splice run time and it seems like the bottleneck is there. I also added a duplicate array and tested the splice on it and somehow it is significantly slower. It seems like the problem might be related to V8 implementation.

const dummy = Array(50000).fill('C');
while (i < chars.length) {
        console.time('innerWhile');

        while (i > 0 && i < chars.length && chars[i - 1] === chars[i]) {
            console.time('splice');
            chars.splice(i - 1, 2);
            console.timeEnd('splice');
        
            console.time('spliceDummy');
            dummy.splice(i - 1, 2);
            console.timeEnd('spliceDummy');
            
            i--;
        }
        i++;

        console.timeEnd('innerWhile');
    }

And the truncated output:

repeat: 0.066ms
restOperator: 0.391ms
splice: 0.417ms
spliceDummy: 0.012ms
innerWhile: 0.527ms
splice: 0.38ms
spliceDummy: 0.012ms
innerWhile: 0.47ms
splice: 0.386ms
spliceDummy: 0.012ms
innerWhile: 0.478ms
splice: 0.379ms
spliceDummy: 0.013ms
innerWhile: 0.454ms
splice: 0.389ms
spliceDummy: 0.011ms
innerWhile: 0.533ms
splice: 0.383ms
spliceDummy: 0.012ms
innerWhile: 0.462ms
splice: 0.398ms
spliceDummy: 0.011ms
innerWhile: 0.458ms
splice: 0.382ms
spliceDummy: 0.012ms
innerWhile: 0.447ms
splice: 0.412ms
spliceDummy: 0.013ms
innerWhile: 0.478ms
splice: 0.389ms
spliceDummy: 0.013ms
innerWhile: 0.448ms
splice: 0.382ms
spliceDummy: 0.012ms
innerWhile: 0.435ms
splice: 0.378ms
spliceDummy: 0.012ms
innerWhile: 0.431ms
splice: 0.379ms
spliceDummy: 0.012ms
innerWhile: 0.43ms
splice: 0.378ms
spliceDummy: 0.012ms
innerWhile: 0.434ms
splice: 0.385ms
spliceDummy: 0.012ms
innerWhile: 0.437ms
splice: 0.393ms
spliceDummy: 0.011ms
innerWhile: 0.445ms
splice: 0.378ms
spliceDummy: 0.012ms
innerWhile: 0.429ms
splice: 0.414ms
spliceDummy: 0.012ms
innerWhile: 0.475ms
splice: 0.397ms
spliceDummy: 0.014ms
innerWhile: 0.46ms
splice: 0.386ms
spliceDummy: 0.015ms
innerWhile: 0.444ms
splice: 0.379ms
spliceDummy: 0.012ms
innerWhile: 0.432ms
splice: 0.436ms
spliceDummy: 0.012ms
innerWhile: 0.486ms
splice: 0.382ms
spliceDummy: 0.011ms
innerWhile: 0.432ms
splice: 0.381ms
spliceDummy: 0.012ms
innerWhile: 0.431ms
splice: 0.395ms
spliceDummy: 0.013ms
innerWhile: 0.553ms
splice: 0.43ms
spliceDummy: 0.011ms
innerWhile: 0.488ms
splice: 0.384ms
spliceDummy: 0.011ms
innerWhile: 0.434ms
splice: 0.428ms
spliceDummy: 0.012ms
innerWhile: 0.481ms
splice: 0.381ms
spliceDummy: 0.013ms
innerWhile: 0.434ms
splice: 0.406ms
spliceDummy: 0.012ms
innerWhile: 0.456ms
splice: 0.378ms
spliceDummy: 0.012ms
innerWhile: 0.431ms
splice: 0.39ms
spliceDummy: 0.011ms
innerWhile: 0.439ms
splice: 0.4ms
spliceDummy: 0.012ms
innerWhile: 0.452ms
splice: 0.392ms
spliceDummy: 0.011ms
innerWhile: 0.441ms
splice: 0.403ms
spliceDummy: 0.012ms
innerWhile: 0.458ms
splice: 0.378ms

when I ran the failed solution through my browser's console with the same input it took like 65 milliseconds for the whole function.

Why does the code takes so long in Codility in contrast to my browser? And why does the duplicate array's splice is significantly faster then the original one?

Passed tests

Failed tests

each is O(n) time complexity.

Nope. When deleting array elements with Array.prototype.splice, that operation must move all remaining elements to fill in the deleted slots, so when splice is called for an index near the beginning of the array, that operation alone has O(n) cost. So if you call that O(n) times, you have O(n²) overall cost. (Codility "detecting" O(2**N) means that their detection mechanism produced an incorrect result.)

It seems like the problem might be related to V8 implementation.

I see no reason why that would be the case.

Why does the code takes so long in Codility in contrast to my browser?

Perhaps Codility is running the evaluation on slower hardware, or on a slower JS engine, or with larger inputs. You'll have to ask them.

And why does the duplicate array's splice is significantly faster then the original one?

That's some kind of measurement artifact. If you duplicate the entire loop and let one copy operate on the dummy array, you'll see that they run at the same speed. As a rule of thumb, don't try to time thousands of tiny operations individually to figure out how long they take; because doing so tends to report all sorts of weird/misleading artifacts but not the insight you're truly after.