Is Javascript String Comparison Just As Fast As Number Comparison?

I'd like to write a little library for JavaScript enums. For me to do that, I need to decide how to store the enum values. Therefore, I'd like to use the fastest way when comparing

Solution 1:

String comparison could be "just as fast" (depending on implementation and values) - or it could be "much slower".

The ECMAScript specification describes the semantics, not the implementation. The only way to Know for Certain is to create an applicable performance benchmark on run it on a particular implementation.

Trivially, and I expect this is the case, the effects of string interning for a particular implementation are being observed.

That is, all string values (not String Objects) from literals can be trivially interned into a pool such that implIdentityEq("foo", "foo") is true - that is, there need only one string object. Such interning can be done after constant folding, such that "f" + "oo" -> "foo" - again, per a particular implementation as long as it upholds the ECMAScript semantics.

If such interning is done, then for implStringEq the first check could be to evaluate implIdentityEq(x,y) and, if true, the comparison is trivially-true and performed in O(1). If false, then a normal string character-wise comparison would need to be done which is O(min(n,m)).

(Immediate falseness can also be determined with x.length != y.length, but that seems less relevant here.)

---

While in the above I argue for string interning being a likely cause, modern JavaScript implementations perform a lot of optimizations - as such, interning is only a small part of the various optimizations and code hoistings that can (and are) done!

I've created an "intern breaker" jsperf. The numbers agree with the hypothesis presented above.

1. If a string is interned then comparison is approximate in performance to testing for "identity" - while it is slower than a numeric comparison, this is still much faster than a character-by-character string comparison.

2. Holding the above assertion, IE10 does not appear to consider object-identity for pass-fast string comparisons although it does use a fast-fail length check.

3. In Chrome and Firefox, two intern'ed strings which are not equal are also compared as quickly as two that are - there is likely a special case for comparing between two different interned strings.

4. Even for small strings (length = 8), interning can be much faster. IE10 again shows it doesn't have this "optimization" even though it appears to have an efficient string comparison implementation.

5. The string comparison can fail as soon as the first different character is encountered: even comparing long strings of equal length might only compare the first few characters.

---

• Do common JavaScript implementations use string interning? (but no references given)

  Yes. In general any literal string, identifier, or other constant string in JS source is interned. However implementation details (exactly what is interned for instance) varies, as well as when the interning occurs

• See JS_InternString (FF does have string interning, although where/how the strings are implicitly interened from JavaScript, I know not)

Solution 2:

There are cases when string comparison can be much slower (comparing dynamically generated strings)

The following is 77% slower (in chrome and IE) than all the other tests

var StringEarth = 'Ear' + 'th';
for (var i = 0; i < ITERATIONS; i++) {
  x = StringPlanets.Venus === StringEarth;
}

The flaw in the tests mentioned in the question is the fact that we are testing against literal strings. It seems that JavaScript is optimized so that string comparison for string literals is done just by testing a pointer. This can be observed by creating the strings dynamically. My best guess is that strings from the literal string pool are marked so that they can be compared using addresses only.

Note that string comparison seems just as fast in FF even for dynamic strings. Also, that it's just as slow for even literal strings.

Conclusion All browsers behave differently so string comparison may or may not be slower.

Solution 3:

In general, at best String interning (making a string with a given value into a unique reference or a O(1) comparable symbol) is going to take O(n) time, as it can't do that effectively without looking at all the characters involved.

The question of relative efficiency then amounts to over how many comparisons the interning is going to be amortized.

In the limit, a very clever optimizer can pull out static expressions which build up strings and intern them once.

Some of the tests above, use strings which will have been interned in which case the comparison is potentially O(1). In the case where enums are based on mapping to integers, it will be O(1) in any implementation.

The expensive comparison cases arise when at least one of the operands is a truly dynamic string. In this case it is impossible to compare equality against it in less than O(n).

As applied to the original question, if the desire is to create something akin to an enum in a different language, the only lookout is to ensure that the interning can is done in only a few places. As pointed out above, different Browser use different implementations, so that can be tricky, and as pointed out in IE10 maybe impossible.

Caveat lacking string interning (in which case you need the integer version of the enum implementation give), @JuanMendes' string-based enum implementations will be essentially O(1) if he arranges for the value of the myPlanet variable to be set in O(1) time. If that is set using Planets.value where value is an established planet it will be O(1).