4

I have a noob javascript question. Let's say we have two very large strings (~ million characters or more) that are equal - they have the same length and the same content. Let's say we have these two function that both do the same thing (compare strings):

function equals1(a, b) {
    return a === b;
}

function equals2(a, b) {
    if (a.length !== b.length) {
           return false;
    }
    for (var i = 0; i < a.length; ++i) {
        if (a[i] !== b[i]) {
            return false;
         }
    }
    return true;
}

Why is the first function (equals1()) almost as twice as fast as the second one? How can the second one be improved so that it performs as good as the first one?

Improve this question
10
  • 8
    ... Because it is implemented in native code? Why do you want to reimplement string comparison? Commented Oct 23, 2014 at 16:17
  • 1
    The most simple explanation is to just look at the code. The first function has a single line of code. The second has more than one line of code. Why would the second be any faster than the first? Why would you want it to be? Commented Oct 23, 2014 at 16:18
  • 2
    @joel apart from not being exactly accurate - why do you think it would be faster? Commented Oct 23, 2014 at 16:20
  • 3
    I swear, people will upvote any question that has the word "performance" in the title. Commented Oct 23, 2014 at 16:21
  • 2
    I do not want to reimplement String comparison :). This is just a hypothetical question... Commented Oct 23, 2014 at 16:32

4 Answers 4

Reset to default
8
+100

Most probably Javascript is doing string interning (Do common JavaScript implementations use string interning?) according to a person that is in ECMAScript committee. I thought that then === would be O(1) but based on performance test of the original poster it is O(n) as doubling the string doubles the time for the equality.. That is really sad that string interning is not used they way it should be.

Update: JSPerf

The orginal poster claims should be backed up for O(N) complexity From http://jsperf.com/eqaulity-is-constant-time It seems that even if I have 16x bigger string the time doesn't change more than 1-2%

So please reconsider those things that I have striked-through and your down votes

In other words:

when you do 

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

the "stringwithmillionchars" will be stored once let's say in address 201012 of memory and both str1 and str2 will be "pointing in this address 201012. This address could 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 takes O(1)/constant time

The for loop in your example (equals2()) has O(N) time, where N the length of both strings. That is because it has to do N comparisons between each pair of characters and N comparisons between i and str.length.

Note: the address numbers were chosen randomly for illustration purposes..

Important: Based on performance comparisons from my question(Why Javascript ===/== string equality sometimes has constant time complexity and some times has linear time complexity) interning happens only when the strings are assigned directly with quotes otherwise the comparison will take linear time instead of constant because char-to-char comparison happens.

Improve this answer
Sign up to request clarification or add additional context in comments.

13 Comments

@Bergi stackoverflow.com/questions/5276915/… If you are familiar with String interning then what it needs to do is compare the memory addresses of the two strings - if it is the same then the two strings are the same
Thank for the answer but I think that this is not what happens. I tried increasing the length of Strings by the factor of 2, and the comparison (a === b) takes twice as much time (hence, it is also O (n))
I'd recommend you to leave it and don't waste more time on this. Your effort is remarkable, but I think you made your point. You're getting 100 bounty from me for your efforts.
Interesting. It looks like javascript will do string interning when you use string literals. However, in my test case, I generated the strings by simply concatenating them in a loop (it would be difficult to type one million characters :). jsperf.com/equality-no-interning
@TihomirMeščić "... constant strings are interned automatically, results of string concatenation, etc aren't" (See comment by olliej on accepted answer)
|
2

The first function is faster because it doesn't have to check if i < a.length one million times, and perform an increment operation on i one million times.

Improve this answer

1 Comment

(in addition to one million comparisons)
1

You can do something like the following to make your equals2 function twice faster:

function equals2(a, b) {
    if (a.length !== b.length) {
           return false;
    }
    for (var i = 0; i < a.length/2; ++i) {
        if (a[i] !== b[i] || a[a.length-i-1] !== b[b.length-i-1]) {
            return false;
         }
    }
    return true;
}
Improve this answer

1 Comment

this seems pretty logical
0

The first does the same things. If the strings are different lengths, it will return false. Then it checks to see if the characters are the same at the same indices. However, it is implemented at the JS implementation level, so it is running as fast as C, C++, Java or whatever language the JavaScript implementation is written in.

Improve this answer

4 Comments

Yes, which is what I said here
He wrote the code so he knows that. He is interested only in the example of two same length and content strings. The performance issue is that the one is doing 2*1000000 comparisons and the other only one .
It has to do more than one comparison though, how do you think it does the comparison behind the scenes?
it just compares the two integers (hashes) which is way faster than char-per-char comparison ;). Of course in the ALU of your CPU an int comparison is not a single instruction but this is offtopic and we consider it O(1) or constant time

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.