String Comparison vs. Hashing

Question

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.

Answer 1

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.