current community

your communities

more stack exchange communities

Stack Exchange
tour help
stack overflow careers
Take the 2-minute tour ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 2 down vote favorite
1

After I found that Javascript common/latest implementations are using String Interning for perfomance boost from here (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.

Can someone please explain why string interning is not used for equality as such (so we have constant time ?):

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 in this address 201012. This address could theb 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

EDIT (NEW) 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

share|improve this question
1  
I think its because === operator compares memory addresses only when comparing objects (similar to Java). But "something" its not an object, its type is the builtin string. The same as comparing numbers, var a=2; var b=2;, if you do a===b you are not comparing objects nor memory adresses. –  sergioFC 50 mins ago
    
Thanks! Could you think of a reason why strings are not objects internally so equality would be blazing fast? –  Michail Michailidis 49 mins ago
    
Some languages (such as Java) provides both posibilities: primitive types (int) and wrapper objects (Integer); I don't know why javascript doesn't have something similar. –  sergioFC 22 mins ago
    
I know you can do var str = new String("test"); but I don't know the implications there either.. –  Michail Michailidis 19 mins ago
1  
Even doing so typeof str would be 'string', not object. –  sergioFC 7 mins ago

2 Answers 2

up vote 1 down vote

According to ECMA Script 5.1 Specification's Strict Equal Comparison algorithm, even if the type of Objects being compared is String, all the characters are checked to see if they are equal.

  1. If Type(x) is String, then return true if x and y are exactly the same sequence of characters (same length and same characters in corresponding positions); otherwise, return false.

Interning is strictly an implementation thingy, to boost performance. The language standard doesn't impose any rules in that regard. So, its up to the implementers of the specification to intern strings or not.

share|improve this answer
    
Thanks. Could you think of a reason why this is a better choice than handling strings as objects two? Is there such an overhead? –  Michail Michailidis 47 mins ago
2  
I fail to see how this forces the engine to actually make the full string comparison. If two variables point to the same string kept somewhere in memory, then they will satisfy this requirement. –  lexicore 40 mins ago
    
@MichailMichailidis Interning is strictly an implementation thingy, to boost performance. The language standard doesn't impose any rules in that regard. –  thefourtheye 39 mins ago
    
Well we are talking about the latest/common implementations- Is it actually being used? Can someone more familiar with jsperf make one please? Case1: "test"==="test", Case2: "testtest"==="testtest" (double the length) Case3: strings are different but same length and Case 4: different and same length. –  Michail Michailidis 38 mins ago
    
@MichailMichailidis Why don't you do one yourself? It's not hard an it's your question. –  lexicore 37 mins ago
up vote 0 down vote

First of all, it would be nice to see a JSPerf test which demonstrates the claim that doubling the string size doubles the execution time.

Next, let's take that as granted. Here's my (unproven, unchecked, and probably unrelated to reality) theory.

Compairing two memory addresses is fast, no matter how much data is references. But you have to INTERN this strings first. If you have in your code

var a = "1234";
var b = "1234";

Then the engine first has to understand that these two strings are the same and can point to the same address. So at least once these strings has to be compared fully. So basically here are the following options:

  • The engine compares and interns strings directly when parsing the code. In this case equals strings should get the same address.
  • The engine may say "these strings are two big, I don't want to intern them" and has two copies.
  • The engine may intern these strings later.

In the two latter cases string comparison will influence the test results. In the last case - even if the strings are finally interned.

But as I wrote, a wild theory, for theory's sage. I'd first like to see some JSPerf.

share|improve this answer
    
I agree with you - The original poster of the other question said it and I took it for granted - I will soon prepare a JSPerf to elaborate more on the numbers if he doesn't. –  Michail Michailidis 40 mins ago

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.