JavaScript Rules

A few days ago I introduced a friend of mine Jorge Rocha to SPOJ an online judge system for user-submitted programs, one of the first problems that he tried was the Prime Generator it consisted in finding all primes in a given range of numbers, after some time and few different algorithms he asked me if I had any tips to help him, although he had the correct algorithm (Sieve of Eratosthenes) something was clearly missing, the solution wasn’t fast enough and I had no clue where to go from there, so as usual when a question like that comes up I resort to Mauro Persano… and obviously he knew the answer, he taught us how to apply a heuristic to the algorithm to help solve the problem and after doing so the code worked and the solution was approved.

Although I’m not really into crazy algorithms challenges I thought I’d give it a try just to see how fast the solution would be in JS, note that most of the solutions submitted are in C/C++ or Java, much faster than JS and to make things worst the interpreter was Rhino, anyways we went ahead and recreated the solution in Javascript, so now it was time to test it… a little more tweaking to make it receive inputs via console and we had it running, right away we realized that our output via stdout was slowing us down, printing 10 times in a row all primes until 1 billion in the shell is not really fast but it was required to, I knew we had little or no chances to get approved but anyways we tried… and as I suspected we didn’t get approved :(, but I decided to test locally in different browsers/engines with and without output.

Here are the results, I also built a test runner so you can test on your own:

• Chrome is usually the best, V8 is blazing fast but it chokes when outputting the results through WebKit
• Rhino does a great job specially with a high number of runs because of JVM
• Firefox runs nicely with short ranges but stops the script because of the long time running
• Opera wasn’t fast but it never crashed or stopped

I’ve just finished chapter 7: Writing Efficient JavaScript by Nicholas Zakas on Steve Souders‘ new book, Even Faster Web Sites, where he presents several string optimization techniques to improve JavaScript performance and wondered which algorithm does String.indexOf method implements on JavaScript engines (aka ECMAScript engines).
A few months ago I’ve asked this question to Yahoo! fellow Douglas Crockford and he said the ECMAScript standard does not require a specific algorithm, so it could vary with each browser. You can check that on section 15.5.4.7 of Standard ECMA-262. I decided then to download the most popular open-source JavaScript engines source codes and found mainly 3 algorithms:

• Naïve: simple and least inefficient way to search in strings, it basically checks every position in the haystack then every position of the needle. The advantage of using this algorithm is that it needs no initial overhead such as auxiliary tables creation. It has O(mn) complexity, where m is the needle length and n the haystack length.
• Boyer-Moore: Efficient searching string algorithm that preprocesses the needle and doesn’t check every position in the haystack but rather skips some of them on each unsuccessful attempt. It has O(n) complexity with O(3n) in the worst case.
• Boyer-Moore-Horspool: It’s a simplification of Boyer-Moore’s algorithm with less overhear during initial needle preprocessing. It also has O(n) complexity but O(mn) in the worst case.

Algorithms by engines

The String.indexOf algorithms by JavaScript engines follows:

SpiderMonkey

Implements the String.indexOf in C with some verifications in string lengths prior to run BMH algorithm in order to avoid long searching for relatively small strings.

Source code available at: ftp://ftp.mozilla.org/pub/mozilla.org/firefox/releases/3.0.13/source/firefox-3.0.13-source.tar.bz2

TraceMonkey

It has exactly the same String.indexOf implementation as SpiderMonkey but in C++.

Source code available at: ftp://ftp.mozilla.org/pub/mozilla.org/firefox/releases/3.5.2/source/firefox-3.5.2-source.tar.bz2

KJS

The main part of the naïve implementation of indexOf follows*:

/* ... */
for (const UChar* c = data_ + pos; c <= end; c++)
    if (c->uc == fchar && !memcmp(c + 1, fdata, fsizeminusone))
        return (c - data_);
 
return -1;

* taken from KDE 4.0 API reference

Files related to String.indexOf method:

• string_object.cpp: defines the prototype for String object where indexOf is in a switch case statement and calls find function.
• ustring.cpp: defines the find function where the naïve algorithm is implemented.

Browse the source code online: http://api.kde.org/4.0-api/kdelibs-apidocs/kjs/html/files.html

JavaScriptCore & SquirrelFish

These engines are known as JavaScriptCore in WebKit Project and was originally derived from KJS, hence still shares the same algorithm for String.indexOf.

Files related to String.indexOf method:

• root/trunk/JavaScriptCore/runtime/StringPrototype.cpp: this is where indexOf method is defined and call find function
• root/trunk/JavaScriptCore/runtime/UString.cpp: look for find function

Source code available at: http://webkit.org/building/checkout.html
Browse the source code online: http://trac.webkit.org/browser

V8

A very smart strategy is applied to the string searching in order to choose the best algorithm based on the length of the needle:

• First of all it checks if there is a non-ASCII needle for an ASCII haystack and bail out if there is.
• Checks if the needle length is less than 5 then uses a naïve solution called simpleIndexOf, because the max shift of Boyer-Moore on such needle length doesn’t compensate for the overhead. This simpleIndexOf function never bails out, it means that the needle will be checked for a match in the whole haystack.
• If the needle length is greater than or equals to 5 another simpleIndexOf function is called. This one considers how much work have been done (unsuccessful matches) in order to stop trying and switch for a better algorithm. This is called the “badness count” which once reached the max, stop the search and returns the index in the haystack where the next algorithm should continue from.
• The next algorithm in the strategy chain is Boyer-Moore-Horspool which also consider the badness count prior to jump to the next algorithm.
• The last one is Boyer-Moore which has some initial overhead when creating good and bad shift tables.

Source code available at: http://code.google.com/p/v8/wiki/Source?tm=4

Rhino

Rhino runs on top of Java Virtual Machine and uses the java.lang.String.indexOf from Java language implemented for such JVM. Interestingly there is a comment saying:

“Uses Java String.indexOf(). OPT to add - BMH searching from jsstr.c”.

Where jsstr.c is the file for SpiderMonkey JavaScript String implementation. Implementing such algorithm in Java might degrade the search performance, unless the java.lang.String.indexOf implementation is much worse than that.

Source code available at: http://www.mozilla.org/rhino/download.html

Other engines

What about Internet Explorer, Opera and other browsers JavaScript engines? As they aren’t open-source projects I could not check their codes out. :-(

Benchmark

By running a simple test across some browsers we can have an idea how fast/slow is String.indexOf on some JavaScript engines although this doesn’t necessarily mean an algorithm is better than another because the performance of the engine itself might affect the outcome.
The test consists of the average of a 100 times running a search for the word “foobar” in the middle of a ~1200 length “ipsum lorem” text iterating 1 million times each search. Try it yourself.

The results in the follow table were taken by running this test on the same machine (Pentium 4HT, 3GHz, 1Gb RAM, Windows XP SP3).

* running on the same machine with Ubuntu 9.04 live cd
** running on a VM on a different computer
*** running on Sun JRE 6 - 1.6.0_14

Again, these results don’t prove which algorithm is the best due to different browser performances, however it is worth noting that Firefox 3.0.13 performed better than Firefox 3.5.2 on this benchmark. Internet Explorer had the worst results, it can be either the algorithm or the browser performance itself or even both. :-)