2
$\begingroup$

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.691 seconds
  • Traditional Rehashing - 71.009 seconds
  • Just comparing the strings (no hashing) 0.100 seconds

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

$\endgroup$
  • $\begingroup$ Not sure whether this question is on-topic, or whether it'd be more appropriate on Stack Overflow. Community votes? $\endgroup$ – D.W. Jan 16 '16 at 17:43
  • $\begingroup$ @D.W. I spent a while thinking about whether I should post it here or on SO - I figured here would be a good place because it's pretty conceptual, however I'll gladly remove it here and ask it on SO if it belongs over there $\endgroup$ – Nick Zuber Jan 16 '16 at 17:44
  • $\begingroup$ This depends on implementation details, and so more appropriate for stackoverflow. $\endgroup$ – Yuval Filmus Jan 16 '16 at 18:07
  • $\begingroup$ @YuvalFilmus Should I remove my post here and ask it on SO or leave it here and also ask it on SO? $\endgroup$ – Nick Zuber Jan 16 '16 at 18:09
  • 1
    $\begingroup$ You can ask it over there, but mention that you asked it here and explain why you are cross posting it there. $\endgroup$ – Yuval Filmus Jan 16 '16 at 18:36
3
$\begingroup$

One possible hypothesis:

Javascript is interpreted, which can slow things down.

When you compare two strings, this will invoke a string comparison routine that is coded directly in assembly language or C, and thus string comparison will probably be about as fast as the architecture can possibly compare strings. In contrast, when you hash strings, you have to execute multiple instructions in Javascript, which might incur overhead from an interpreter.

Another possible hypothesis:

Numbers in Javascript are a floating-point type. There is no integer type in Javascript. Your rolling hash probably involves what looks like integer arithmetic. However, under the covers this is probably getting interpreted as operations on double-precision floats, which can be a bit slower. This might also make your hash-based schemes slower. Some Javascript engines might optimize this to integer arithmetic in certain circumstances, but no guarantees about whether any particular Javascript engine will or won't be able to do that in any particular case.

$\endgroup$
  • $\begingroup$ I also suspected something like this - the fact that strings are primitive types in javascript might mean they can be compared on a very low level which can be incredibly fast, where as my rolling hash has some overhead on the initial hashing portion. It's reasurring to know that someone else has a similar hypothesis - thank you for your answer :) $\endgroup$ – Nick Zuber Jan 16 '16 at 17:50
  • $\begingroup$ You're correct - because strings are primitive, the interpreter is able to perform comparison operations as quickly as comparing numbers, for example. This explains the speedy comparing with the strings. My rolling hash was slower because function calls create a slight overhead, therefore slightly slowing down the overall speed. $\endgroup$ – Nick Zuber Jan 18 '16 at 23:29
2
$\begingroup$

Comparing two strings can be really fast if their initial segments differ. String comparison is usually implemented with a loop over the characters, immediately returning false if any one of them differs and returning true when all characters have been examined.

If the strings being compared differ in one of their first characters, then such a comparison function would run really fast. If your strings were "random" then this very likely explains why the string comparison route was so fast.

To get the string comparison approach to display its worst case, I suggest testing it by searching for

aaaa [...] aaaab

in a string consisting entirely of a's. This will trigger the worst case every time.

$\endgroup$
1
$\begingroup$

Numbers are double in standard, you can do typed array, overhead comes mainly from missuse of functions, closures and types.

Problem is strictly in JS usage - C has one byte char*, JS uses multibyte.
Optimizing for integers is possible in two scenarios - all operations are truncated or typed arrays are used, otherwise no can do.

Although this is my fav lang, its quirks are heavy...

Also there is one very big problem - modulo operator is defined on doubles, while in the most programming languages it is defined for integers, also sign is expected to be +.
In JS % is defined for double precission - so it is the bottleneck when used with $var$.
Without actually showing the code any guess is valid.

The problem you are suffering is strictly due to implementation, and browser (or node.js or whathever environment you are using) it is not comming from concept, but if you think otherwise, maybe test cases are not reasonable enough.
If you have small amount of strings or they differ on first places - compare is faster as this is built in.

The next step is really looking at your code, as this is not any code review, but JS review - take into account all quirks, types and operations.

Remember that built in sort operate on strings (not doubles), so on the first glance everything should work but it slows somewhere on the type coercion or toString function.
Intermixing strings and numbers is possible, resulting type is not symmetric.

Also take DOM operations in profiling separately - putting your result into DOM context results in repainting and reflow on the whole page.

Try to make local variables and denote $const$ where you can, profile code, if some operation is out of blue too heavy, probable type coercion or prototype chaining kicked in, which is devastating in execution time and makes it impossible to optimize in advance.

If your variables are out of the scope - force them by reference to local variables or rewrite code, try jsperf for similar tasks, try using strict code.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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