JavaScript String Equality – Understanding Time Complexity

javascriptperformancestringstring-interningtime-complexity

After I found that the common/latest Javascript implementations are using String Interning for perfomance boost (Do common JavaScript implementations use string interning?), I thought === for strings would get the constant O(1) time. So I gave a wrong answer to this question:

JavaScript string equality performance comparison

Since according to the OP of that question it is O(N), doubling the string input doubles the time the equality needs. He didn't provide any jsPerf so more investigation is needed,

So my scenario using string interning would be:

var str1 = "stringwithmillionchars"; //stored in address 51242

var str2 = "stringwithmillionchars"; //stored in address 12313

The "stringwithmillionchars" would be stored once let's say in address 201012 of memory
and both str1 and str2 would be "pointing" to this address 201012. This address could then be determined with some kind of hashing to map to specific locations in memory.

So when doing

"stringwithmillionchars" === "stringwithmillionchars"

would look like

getContentOfAddress(51242)===getContentOfAddress(12313)

or 201012 === 201012

which would take O(1)/constant time

JSPerfs/Performance updates:

JSPerf seems to show constant time even if the string is 16 times longer?? Please have a look:

http://jsperf.com/eqaulity-is-constant-time

Probably the strings are too small on the above:
This probably show linear time (thanks to sergioFC) the strings are built with a loop. I tried without functions – still linear time / I changed it a bit http://jsfiddle.net/f8yf3c7d/3/ .

According to https://www.dropbox.com/s/8ty3hev1b109qjj/compare.html?dl=0 (12MB file that sergioFC made) when you have a string and you already have assigned the value in quotes no matter how big the t1 and t2 are (e.g 5930496 chars), it is taking it 0-1ms/instant time.

It seems that when you build a string using a for loop or a function then the string is not interned. So interning happens only when you directly assign a string with quotes like var str = "test";

Best Answer

Based on all the Performance Tests (see original post) for strings a and b the operation a === b takes:

constant time O(1) if the strings are interned. From the examples it seems that interning only happens with directly assigned strings like var str = "test"; and not if you build it with concatenation using for-loops or functions.
linear time O(N) since in all the other cases the length of the two strings is compared first. If it is equal then we have character by character comparison. Else of course they are not equal. N is the length of the string.

Related Solutions

JavaScript – Performance Comparison of === vs == Operators

I feel an answer with easily verifiable evidence would be best.

These operations are so small that it is difficult to performance test them.

== 1648 true
=== 1629 true
control test 1575 true

If you subtract off the control test, it looks like there is a ~30% difference in their speeds on my browser. If you do this multiple times, you can get different answers, but === usually comes up the fastest, which I think is just a testament to just how negligible the difference is.

I think this pretty much proves what others were saying, that the performance difference is a waste of time to think about, but it also shows that === is actually faster. Hopefully this answer can save other people time, those who simply must see proof.

2019 Updates

2019-04-09 Firefox with improved test:

== 1383 true
=== 1167 true
control test 429 true

2019-04-09 Chrome with improved test:

== 249 true
=== 248 true
control test 248 true

2019-04-09 Edge with improved test:

== 22510 true
=== 20315 true
control test 4968 true

Browsers have gotten smarter over the years and it appears my original test has run up against cool optimizations in Chrome and Firefox, rendering it no longer useful. I have made the test more difficult to optimize and increased the number of runs to get meaningful results again. It looks like === is still faster across the board. It is probably still a waste of time to worry about.

var testString = "42";
var testString2 = "43";
var testString3 = "42";
var testNumber = 42;
var testNumber2 = 43;
var testNumber3 = 42;

var testObject = {};
var testObject2 = {};
var testObject3 = testObject;


var start = Date.now();
var result = null;
for(var i = 0; i < 200000000; i++){
	result = 
	testString == testString2 || testNumber == testNumber2 || testObject == testObject2 || 
	testString == testString2 || testNumber == testNumber2 || testObject == testObject2 || 
	testString == testString2 || testNumber == testNumber2 || testObject == testObject2 || 
	testString == testString2 || testNumber == testNumber2 || testObject == testObject2 || 
	testString == testString2 || testNumber == testNumber2 || testObject == testObject2 || 
	testString == testString2 || testNumber == testNumber2 || testObject == testObject2 || 
	testString == testString2 || testNumber == testNumber2 || testObject == testObject2 || 
	testString == testString2 || testNumber == testNumber2 || testObject == testObject2 || 
	testString == testString2 || testNumber == testNumber2 || testObject == testObject2 || 
	testString == testString2 || testNumber == testNumber2 || testObject == testObject2 || 
	testString == testString3 && testNumber == testNumber3 && testObject == testObject3 && 
	testString == testString3 && testNumber == testNumber3 && testObject == testObject3 && 
	testString == testString3 && testNumber == testNumber3 && testObject == testObject3 && 
	testString == testString3 && testNumber == testNumber3 && testObject == testObject3 && 
	testString == testString3 && testNumber == testNumber3 && testObject == testObject3 && 
	testString == testString3 && testNumber == testNumber3 && testObject == testObject3 && 
	testString == testString3 && testNumber == testNumber3 && testObject == testObject3 && 
	testString == testString3 && testNumber == testNumber3 && testObject == testObject3 && 
	testString == testString3 && testNumber == testNumber3 && testObject == testObject3 && 
	testString == testString3 && testNumber == testNumber3 && testObject == testObject3
}

console.log("==", Date.now() - start, result);

var start = Date.now();
var result = null;
for(var i = 0; i < 200000000; i++){
	result =
	testString === testString2 || testNumber === testNumber2 || testObject === testObject2 || 
	testString === testString2 || testNumber === testNumber2 || testObject === testObject2 || 
	testString === testString2 || testNumber === testNumber2 || testObject === testObject2 || 
	testString === testString2 || testNumber === testNumber2 || testObject === testObject2 || 
	testString === testString2 || testNumber === testNumber2 || testObject === testObject2 || 
	testString === testString2 || testNumber === testNumber2 || testObject === testObject2 || 
	testString === testString2 || testNumber === testNumber2 || testObject === testObject2 || 
	testString === testString2 || testNumber === testNumber2 || testObject === testObject2 || 
	testString === testString2 || testNumber === testNumber2 || testObject === testObject2 || 
	testString === testString2 || testNumber === testNumber2 || testObject === testObject2 || 
	testString === testString3 && testNumber === testNumber3 && testObject === testObject3 && 
	testString === testString3 && testNumber === testNumber3 && testObject === testObject3 && 
	testString === testString3 && testNumber === testNumber3 && testObject === testObject3 && 
	testString === testString3 && testNumber === testNumber3 && testObject === testObject3 && 
	testString === testString3 && testNumber === testNumber3 && testObject === testObject3 && 
	testString === testString3 && testNumber === testNumber3 && testObject === testObject3 && 
	testString === testString3 && testNumber === testNumber3 && testObject === testObject3 && 
	testString === testString3 && testNumber === testNumber3 && testObject === testObject3 && 
	testString === testString3 && testNumber === testNumber3 && testObject === testObject3 && 
	testString === testString3 && testNumber === testNumber3 && testObject === testObject3
}
console.log("===", Date.now() - start, result);
var start = Date.now();
var alwaysTrue = true;
var alwaysFalse = false;
for(var i = 0; i < 200000000; i++){
	result = 
	alwaysFalse || alwaysFalse || alwaysFalse || 
	alwaysFalse || alwaysFalse || alwaysFalse || 
	alwaysFalse || alwaysFalse || alwaysFalse || 
	alwaysFalse || alwaysFalse || alwaysFalse || 
	alwaysFalse || alwaysFalse || alwaysFalse || 
	alwaysFalse || alwaysFalse || alwaysFalse || 
	alwaysFalse || alwaysFalse || alwaysFalse || 
	alwaysFalse || alwaysFalse || alwaysFalse || 
	alwaysFalse || alwaysFalse || alwaysFalse || 
	alwaysFalse || alwaysFalse || alwaysFalse || 
	alwaysTrue && alwaysTrue && alwaysTrue && 
	alwaysTrue && alwaysTrue && alwaysTrue && 
	alwaysTrue && alwaysTrue && alwaysTrue && 
	alwaysTrue && alwaysTrue && alwaysTrue && 
	alwaysTrue && alwaysTrue && alwaysTrue && 
	alwaysTrue && alwaysTrue && alwaysTrue && 
	alwaysTrue && alwaysTrue && alwaysTrue && 
	alwaysTrue && alwaysTrue && alwaysTrue && 
	alwaysTrue && alwaysTrue && alwaysTrue && 
	alwaysTrue && alwaysTrue && alwaysTrue
}
console.log("control test", Date.now() - start, result);

Best Answer

Related Solutions

JavaScript – Performance Comparison of === vs == Operators

Related Question