Why does the comparison operator work faster regardless of the length of string?
Consider the following two functions which I use to compare strings with a length of 100 million:
With ===:
// O(?)
const compare1(a, b) {
return a === b;
}
With character by character comparison:
// O(N)
const compare2(a, b) {
if(a.length !== b.length) return false;
const n = Math.max(a.length, b.length);
for(var i=0; i<n; i++){
if(a[i] !== b[i]) return false;
}
return true;
}
When testing these two functions, I find that the speed of the compare1 function is significantly faster.
In the case of the compare2 function, I think the overhead will be severe in interpreting JavaScript code, accessing and comparing memory.
But from my understanding, the compare1 function may also have to compare N characters. Does it run so much faster because it all happens at a lower level?
There are two considerations:
=== comparison of string primitives is implemented with lower level, compiled code, which indeed executes faster than explicit JavaScript looping, which has additional work, including in updating a JavaScript variable (i), performing an access with that variable (a[i]); where all the prescribed ECMAScript procedures must be followed.
The JavaScript engine may optimise memory usage and use the knowledge that two strings are the same (for instance when that is already detected at parsing time, or one string is assigned to a second variable/property) and only store that string once (cf. String pool). In that case the comparison is a trivial O(1) comparison of two references. There is however no way in JavaScript to inspect whether two string primitives actually share the same memory.
As an illustration of the second point, note how the comparison-time is different for two cases of comparing long strings that are equal -- which probably is a hint that this string pooling is happening:
function compare(a, b) {
let sum = 0, start, p;
for (let i = 0; i < 10; i++) { // Perform 10 comparisons
start = performance.now();
p = a === b;
sum += performance.now() - start;
}
return sum / 10; // Return average time to make the comparison
}
console.log("Hold on while strings are being created...");
setTimeout(function () {
// Create long, non-trivial string
let a = Array.from({length: 10000000}, (_, i) => i).join("");
let b = a.slice(0); // Plain Copy - engine realises it is the same string & does not allocate space
let c = a[0] + a.slice(1); // More complex - engine does not realise it is the same string
console.log("Strings created. Test whether they are equal:", a === b && b === c);
console.log(compare(a, b) + "ms");
console.log(compare(a, c) + "ms");
});