My Programming Escapades
Andraz Bajt
Javascript faster than light! (well C actually)

157/365. Acorn - Oak Nut - The Scrat Problem.

Disclaimer: I never was a fan of js, but I've come to think it's quite AWESOME!

Anyway I invented my own toy language scrat recently. And I now I want it to go fast and do cool stuff. So I went on to compile it. Well more appropriate term would be “translate"(as zidarsk8 pointed out) since my target is JavaScript. And then I use node.js to run it - browser test sometime in the future. Enough about that, I'll be doing a post when I get everything to run under js.

My original purpuse for translation was speed as node uses V8 and that's quite speedy. So I did a quick test. I wrote a simple recursive Fibonacci sequence generator. The cool thing about this is that it takes fib(n) steps to calculate fib(n) but call-stack depth is just n - I don't have loops and I haven't implemented tail call optimization yet. And then I wrote same thing in js an noticed it's quite a bit faster. Great. Now halfway through implementation(more like 80%) I decided to do a real benchmark.


Here's the source

func fib(n) if n<2 then 1 else fib(n-1) + fib(n-2)

Neat huh?

And then I timed this repeatedly and all results were about the same:

time scrat fib.scrat
real 0m3.254s
user 0m3.652s
sys 0m0.096s

Of course there is some startup overhead that must be taken into account so I ran an empty file

time scrat empty
real 0m0.420s
user 0m0.448s
sys 0m0.032s

To obtain total running time of 3254 - 420 = 2830ms


Then I translated my source into js. Below is the untouched(apart from whitespace) result

function fib(n){
  return (function(){
      return 1.0;
    } else {
      return (fib((n)-(1.0)))+(fib((n)-(2.0)));

In scrat ifs are expressions too, so the if is wrapped in an anonymous function. In spite of additional invocations, running time decreased dramaticaly: 128ms.

Real reason for this test was my wory of if overhead so I did a by-hand implementation

function fib(n){
    return 1;
  } else {
    return fib(n-1)+fib(n-2);

Running time: 35ms. Auch! Wrapping the if statement into an if expression multiplies running time by almost 4!! But it's still 22 times faster than my interpreter. (My code sucks I guess)


At this point you should be wondering what does this has to do with C. Not much. I tried to do an implementation in C just for kicks. To see how much overhead my by-head function still has. I was assuming C program will go in something like 10ms.

My best attempt(in the same style: recursion, if expression)


int fib(int n){
  return (n<2)?1:fib(n-1)+fib(n-2);

int main(){
  printf("%d", fib(39));
  return 0;

Startup time is neglectible here, since it doesn't load an interpreter or a framework. So here's the full running time..ready? 634 fricking miliseconds! That's only 4 times faster than my interpreted code. And 18 times slower than javascript. I'm not sure how is this even possible. It's probably just my bad implementation. But rules were: keep the style. So I hereby declare: js is faster than C. (in this microbenchmark)


I did something terribly wrong. Look at the C code closely. Its fib(39) where in scrat and js I called fib(30). I just compared apples and oranges. 

Fixing the C code I got average 20ms. A bit faster than node. So it turns out javascript isn't faster than light(c) but it's pretty damn close. 

I guess this whole post is now wrong, but it was fun to do nonetheless. 

Last modified on 2012-10-21