My programming escapades: C

Sunday, October 21, 2012

Javascript faster than light! (well C actually)

157/365. Acorn - Oak Nut - The Scrat Problem. (Photo credit: Anant N S (www.thelensor.tumblr.com))

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.

Scrat

Here's the source

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

Neat huh?

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

andraz@andraz-desktop:/tmp/temp$ time scrat fib.scrat 
1346269.0

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

andraz@andraz-desktop:/tmp/temp$ time scrat empty 

real 0m0.420s
user 0m0.448s
sys 0m0.032s

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

Javascript

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

function fib(n){
    return (function(){
        if(n<2.0){
           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){
    if(n<2){
        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)

C

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)

#include <stdio.h> 

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, and I wouldn't even know hoe to measure it. 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)

UPDATE:

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.

Thursday, October 18, 2012

Virtual machine in C(++)

This is not a tutorial. This post is a flashback I had today. It might be a bit fiction as my memory about events tends to be fuzzy at times. But I promise it at least resembles the real story.
I was in elementary school and just found out about programming and was learning about c++. After reading "C++ na kolenih" by Goran Bervar I was empowered by knowledge and tried to do all sorts of projects. Mostly in console. Stuff like subtitle format converter - NIH syndrome. I was a bit frustrated because I couldn't find any books about windows programming in the library. Yes, library was may primary source of information, because my English was not nearly good enough for technical stuff.
I might add here I worked on Windows 98(and later XP) with DevC++. I found out about Visual Studio in a few years and did some Windows development.
I digressed a bit. Then came the most optimistic idea. A virtual machine. Something quite high level(instruction to print) an eventually an assembler. I now realize I was always into language stuff. So a designed a machine language with just enough instructions to do Hello World, that is PRINT and END.

Implementation

At first I thought about doing a monolithic structure - switch case(in fact what I've done with scrat recently). But I had some considerations. What if number of of instruction rises a lot? I'll be left maintaining spaghetti code. Or at least I thought that's what spaghetti code looks like, but in retrospective I believe I had a good taste anyway.

But I tried that anyway. Just for kicks. Did whole machine as one class that had an array for memory and a single point of entry - boot. It run a loop a while loop with PC<-PC+1, fetched instruction from memory, switched on them, called appropriate method to implement that instruction and looped. Even had registers. I think my current professor of Computer Architecture(this course brought back the memory) might actually be proud if he heard what I did back then.

Pointers

I was always quite comfortable with pointers. I don't now, they're mathematicky concept. I like such stuff. Or perhaps it was because I was young when I was introduced into the matter and wasn't spoiled with automatic memory management(which I quite like nowadays).

So I tried with function pointers. C is cool enough to let you have pointers to functions! And that means higher order functions. But I didn't know about math enough to appreciate the concept as I do now. But still - I thought it's extremely cool. So I did a function that halted execution and printed out "no such instruction". Why you ask? Well I did a 256-cell table(8-bit instruction) of pointers to functions. Now I didn't have to switch - just a look-up and invocation. Great. Apart from the fact it doesn't work.

Compiler said something along the lines of "You cannot make a table of pointers to functions!". I was puzzled. Skip 10 years into the future. Today I was rethinking this and thought about casting the pointer. All the functions would be void->void so I can cast back no problem. A table of void pointers and casting. Yay!

Now 10 years back. I didn't think about casting the pointer. Type info was sacred to me!

So I "invented" function objects.

Objects

I swear to god I have not heard about function objects back then. It wasn't until this year reading Bloch's Efficient Java where he talks about strategy objects. I immediately recognized my idea. So now I had many classes, every one implementing execute method. And I had an array of these objects. Now I did a look-up and invocation on an object. Sweet. And it even worked. But sadly I dropped the project and went on to graphics. Learnt SDL and did Tic-Tac-Toe. And dreamed about doing a vector 3D engine(curves baby!). Which until this day I didn't try to implement. Maybe I'll try in near future.