22

I recently learned about the rolling hash data structure, and basically one of its prime uses to searching for a substring within a string. Here are some advantages that I noticed:

  • Comparing two strings can be expensive so this should be avoided if possible
  • Hashing the strings and comparing the hashes is generally much faster than comparing strings, however rehashing the new substring each time traditionally takes linear time
  • A rolling hash is able to rehash the new substring in constant time, making it much quicker and more efficient for this task

I went ahead and implemented a rolling hash in JavaScript and began to analyze the speed between a rolling hash, traditional rehashing, and just comparing the substrings against each other.

In my findings, the larger the substring, the longer it took for the traditional rehashing approach to run (as expected) where the rolling hash ran incredibly fast (as expected). However, comparing the substrings together ran much faster than the rolling hash. How could this be?

For the sake of perspective, let's say the running times for the functions searching through a ~2.4 million character string for a 100 character substring were the following:

  • Rolling Hash - 0.809 seconds
  • Traditional Rehashing - 71.009 seconds
  • Just comparing the strings (no hashing) 0.089 seconds

How could the string comparing be so much faster than the rolling hash? Could it just have something to do with JavaScript in particular? Strings are a primitive type in JavaScript; would this cause string comparisons to run in constant time?

My main confusion is as to how/why string comparisons are so fast in JavaScript, when I was under the impression that they were supposed to be relatively slow.

Note: By string comparisons I'm referring to something like stringA === stringB

Note: I asked this question over on the Computer Science Community and was informed that I should ask it here as well because this is most likely JavaScript specific.

Improve this question
6
  • 1
    What does your rolling hash implentation look like, and maybe you could set this up on jsperf so we can test it ourselves. Most likely the javascript engine you're using is much faster in comparing simple strings, than anything you can write in javascript will ever be. Commented Jan 16, 2016 at 18:47
  • You could write your own string comarison and compare that with the rolling hash. Commented Jan 16, 2016 at 18:49
  • My rolling hash implementation can be found here, however the main concern is how fast string comparisons are in JavaScript. I thought comparing strings was supposed to be relatively slow, so I'm confused as to why/how it's so fast in JavaScript Commented Jan 16, 2016 at 18:51
  • And again, that's probably implementation dependent, it's how the engine is written in languages like C++ that determines how fast the == and ===, indexOf etc comparisons are internally when using strings. Commented Jan 16, 2016 at 19:11
  • 1
    That's great, and a good answer +1 Commented Jan 18, 2016 at 13:58

1 Answer 1

Reset to default
24

After some testing and analysis, I've come to the conclusion that there were a few reasons as to why my rolling hash approach was running slightly slower than simply comparing the two strings.

  • If the rolling hash claims to run in constant time, how can it be slower than comparing strings?

    Functions are relatively slow - calling a function is slightly slower than simply executing code inline. In my particular case, a function had to be called on my object every time the rolling hash rehashes its internal window, therefore taking slightly longer to run compared to the string comparison, since that code was simply inline. Especially since my benchmark has the rolling hash "shift" over 2 million iterations, this function slow down can be seen more clearly.

  • But why is the string comparison so fast?

    Strings are primitive - Basically, because strings are a primitive type in JavaScript, the attempting to compare two strings will most likely invoke some routine that is coded directly within the interpreter. This low level evaluation can be done as fast as the architecture possibly can (similar to comparing numbers).

In Conclusion

Comparing strings in JavaScript will end up being faster than a rolling hash in this scenario because the strings are primitive, therefore allowing the interpreter to work with these elements very quickly, and because simply calling functions will create a slight overhead and slow down the process on a very small scale.

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

1 Comment

it's people like you that make Stack overflow great. thank you for writing this question and answer.

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.