[ACCEPTED]-Is JavaScript string comparison just as fast as number comparison?-enums

Accepted answer
Score: 26

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Score: 2

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

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

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

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

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

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

Score: 1

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

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

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

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

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

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

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

More Related questions