Search code examples
javascriptbig-ov8

What is the algorithmic complexity of string slicing? (Practical, Real World)

In modern, v8 Javascript, what is the algorithmic complexity of String.prototype.slice?

To be clear, I'm looking for real-world, practical figures or rules of thumb.

Quick Tests

I tried to get a rough estimate by running two quick tests in the most recent Chrome. Test 1 slices a string of length N in half. Test 2 slices a string of length N each index in the string (so N times). Confusingly, both run in O(N) time. What is going on?

Test 1

let input = '';
let string = ' '.repeat(20000000);
for (let i = 0; i < 50; i++) {
    input += string;
    console.time(i);
    const y = input.slice(i / 2);
    console.timeEnd(i);
}

Test 2

let input = '';
let string = ' '.repeat(20000000);
for (let i = 0; i < 50; i++) {
    input += string;
    console.time(i);
    for (let j = 0; j < i; j++) {
        const y = input.slice(j);
    }
    console.timeEnd(i);
}

Chrome version: Chrome Version 63.0.3239.84 (Official Build) (64-bit)

Solution

  • Yes, V8 has optimised string slicing to O(1). This does of course depend a lot on what else happens to all the strings, they might need to get copied later on.

    The relevant implementation from the above link is:

    Sliced String diagram

    // The Sliced String class describes strings that are substrings of another
// sequential string.  The motivation is to save time and memory when creating
// a substring.  A Sliced String is described as a pointer to the parent,
// the offset from the start of the parent string and the length.  Using
// a Sliced String therefore requires unpacking of the parent string and
// adding the offset to the start address.  A substring of a Sliced String
// are not nested since the double indirection is simplified when creating
// such a substring.
// Currently missing features are:
//  - handling externalized parent strings
//  - external strings as parent
//  - truncating sliced string to enable otherwise unneeded parent to be GC'ed.
class SlicedString: public String {
  // ...
};

    Also beware of your quick test results. As you are doing nothing with the y variable, the slicing and even the whole loop might get eliminated as dead code by the optimiser. If you are doing benchmarks, do them on practical real world data.