Category Archives: Geek Time

Browsing though my Geek times.

WebKit-GTK : JSC v/s V8 performance on ARM

As I mentioned in the other post [1], recently I managed to get WebKit-GTK compiled with V8. My previous post presented the performance data between JSC and V8 taken on a x86-64 bit machine and based on the performance metrics, it turns out that, V8 performs better over JSC, at-least in x86-64 bit machine.

Having said that, it would be interesting to see the performance numbers on a ARM device. This post captures the results of V8 and Sun spider on an ARM target.

Reference device:
The reference ARM target used for the performance measurement is Panda Board [2]. Panda board has OMAP4430, 1GHz, Dual core ARM cortex-A9 processor with 1GB of low power DDR2 RAM. I had ARM version of Ubuntu Natty 11.04 running on this device.

Build Configuration:
WebKit Revision : 91387
V8 Revision : 9014

Benchmarking procedure:
There are 3 popular Javascript performance bench-marking tools , viz, V8 bench-marking tool by Google, Sun spider bench-marking tool by WebKit community and Dromaeo bench-marking tool by Mozilla. Here I captured the bench-marking results with V8 and Sun-spider tools. Each of test suite in each tool is run for 5 times and average of these 5 runs is taken for comparison. Data is shared here. I couldn’t able to get the data with Dromaeo[5], as this suite takes longer time and my Panda board used to get over-heated and display used to get turned off before the completion of the test.

V8 benchmarking :
Below graph shows the performance result taken with V8 benchmarking suite[3],

As the chart shows, with exception to ‘Splay’ test case, V8 performs significantly better than JSC! In-fact, this result is almost same as the results taken on x86-64 bit machine [1]. On an average V8 seems to be 3 times faster than JSC.

Sun-Spider benchmarking :
As with V8 benchmarking suite, even sun-spider benchmarking suite[4] also favors V8 (except in 3d and regex test cases) over JSC. On an average there seems to be ~1.5 times increase in performance with V8.

Conclusion:
Well, based on these results, it seems like, V8 performs better over JSC, not only in x86-64 bit machine, but also on an embedded ARM device.

References:
[1]. https://xc0ffee.wordpress.com/2011/08/27/webkit-gtk-jsc-vs-v8/
[2]. http://pandaboard.org/
[3]. http://v8.googlecode.com/svn/data/benchmarks/v6/run.html
[4]. http://www.webkit.org/perf/sunspider-0.9.1/sunspider-0.9.1/driver.html
[5]. http://dromaeo.com/

WebKit-GTK – JSC v/s V8

Well, its been quite some time since I started to work on porting V8 Java Script Engine [1] to WebKit-GTK and recently I managed to get WebKit-GTK running with V8! This work can be found in my gitorious branch at nayankk-webkit. By default, WebKit-GTK will be built with JSC (Java Script Core) Java Script Engine, use the below command for compiling WebKit-GTK with V8 backend,

sh autogen.sh --with-jsengine=v8

After porting V8 to WebKit-GTK, next curious thing, of-course, is to compare the performance of V8 andJSC . Quite some time back, performance comparison on WebKit-Qt port by webkit.sed.hu [2] seems to favor V8 in x86 machine. This blog post captures the performance of WebKit-GTK with JSC and V8 Javascript engines taken on a x86 machine. Performance data on ARM would be the subject of another blog post.

Machine:
Performance data is taken on a quad-core Intel i5 x86 reference machine with 4GB of RAM running at 2.4GHz. Operating system used is Ubuntu Natty 11.04

Build Configuration:
WebKit Revision : 91387
V8 Revision : 9014

Benchmarking procedure:
There are 3 popular Javascript performance bench-marking tools , viz, V8 bench-marking tool by Google, Sun spider bench-marking tool by WebKit community and Dromaeo bench-marking tool by Mozilla. Here I captured the bench-marking results with all 3 tools. Each of test suite in each tool is run for 5 times and average of these 5 runs is taken for comparison. Data is shared here.

V8 benchmarking :
This tools is developed by Google V8 team. Version 6 of this bench-marking tool[3] is  used here for comparison. Here are the results,

As you can see from the graph, V8 defeats JSC by significant margin in all test suites. Note that, higher the score, better the performance.

Sun-Spider benchmarking :
This Java-script bench-marking tools developed by WebKit Team[4]. Results of these tests are here,

Well, these results show that, performance of V8 is slightly less in 3d, bitops and control-flow operations. In rest of all test cases, V8 performs significantly better than JSC.

Dromaeo benchmarking:
Dromaeo[5] has a collection of Java Script performance test suite. Result here are taken for ‘All recommended tests’ of dromaeo.

As with other test suites, Dromaeo also shows significant improvement in performance when V8 engine is used. However, a notable difference is with the test cases using Prototype JS framework, most of which favor JSC over V8.

Conclusion:
As seen with all charts, V8 seems to win against JSC, at-least in x86 machine. However, it would be interesting to see the result on an ARM target, which would be the subject of my next blog post.

References:
[1]. http://code.google.com/p/v8/
[2]. http://webkit.sed.hu/blog/20101216/benchmarking-qtwebkit-v8-linux
[3]. http://v8.googlecode.com/svn/data/benchmarks/v6/run.html
[4]. http://www.webkit.org/perf/sunspider-0.9.1/sunspider-0.9.1/driver.html
[5]. http://dromaeo.com/


Linker “ld: cannot find /lib/libpthread.so.0″

Having frustrated using Scratchbox to compile my module code for ARM device, I decided to switch to cross-compilation in Desktop for ARM target. I feel scratchbox is one of the most stupidest, difficult to use, good-for-nothing software, which serves nothing better than what cross compiler toolchains can do. And the worst part is, if you do not have admin rights at the host system where scratchbox is installed, then it means, you can not install and use your favourate softwares, like emacs, git!! Stealing your freedom?, definately not a good deal!. Right?

Well, next task was to setup the cross-compilation environment, in my host x86 machine, using appropriate toolchains, with the aid of gcc’s –sysroot option. I managed to write a small script to cross-compile my code using scratchbox-toolchain-arm-linux-cs2010q1-202 cross compiler (http://www.scratchbox.org/download/files/sbox-releases/hathor/tarball/). Compilation went through fine, however, while linking my module, linker thowed below error, even though I made sure all paths are properly set,

/opt/compilers/arm-linux-cs2010q1-202/bin/../lib/gcc/arm-none-linux-gnueabi/4.4.1/../../../../arm-none-linux-gnueabi/bin/ld: skipping incompatible /lib/libpthread.so.0 when searching for /lib/libpthread.so.0
/opt/compilers/arm-linux-cs2010q1-202/bin/../lib/gcc/arm-none-linux-gnueabi/4.4.1/../../../../arm-none-linux-gnueabi/bin/ld: cannot find /lib/libpthread.so.0

It seems like linker is searching for “/lib/libpthread.so.0″ instead of plain “libpthread.so.0″. After scratching head for hours and googling, I figured the cause for this error. The linker script at libc/usr/lib/libpthread.so has the following grouping,

GROUP ( /lib/libpthread.so.0 /usr/lib/libpthread_nonshared.a )

And so this is where the /lib/libpthread.so.0 path is coming from. Modifiying the above line and removing the path information, like below,

GROUP ( libpthread.so.0 libpthread_nonshared.a )

linking just happened perfectly fine! Best part is, the compilation happens much faster now. Also I am able to use all my native sotwares freely. I got my “freedom” back. :)

My first real Beagle Board

I always wanted myself to own an embedded device, so that I can play around with it, for fun!. So, I purchased Beagle Board XM, an ARM Cortex A8 based embedded device with 512 MB of DDR RAM. One need to buy few other accessories as well to work with Beagle Board. Below is my shopping list,

a). Beagle Board XM Rev A
b). HDMI DVI-D Male Cable – To connect Beagle Board to monitor.
c). 5V@2.5A Power Adapter – To power on the Beagle Board. Mini USB cable can also be used to power on the device.
d). USB to Serial RS232 cable – To connect to host machine.
e). USB Mini-B Device Cable.

Beagle Board XM comes with 4GB micro SD card, which is supposed to contain Angstrom validation image. Unfortunately, microSD card which I received was empty! Here is how I created validation image. BTW, I used Ubuntu Maverick to create this image.
a). wget http://beagleboard-validation.s3.amazonaws.com/deploy/201008201549/sd/beagleboard-validation-201008201549.img.gz
b). zcat beagleboard-validation-0201008201549.img.gz | dd of=/dev/your/sd/card bs=8225280
More details can be found here.

Next task was to power on the device. Its quite simple,
a). Connect USB to Serial RS232 to host computer. I use ‘gtkterm’ terminal program to connect to device via serial cable. Configure gtkterm for Baud Rate – 115200, DATA – 8 bit, PARITY- none, STOP – 1bit, FLOW CONTROL – none. Following is the output of ‘dmesg’ upon connecting the cable,
[ 1851.984446] usb 2-1.2: pl2303 converter now attached to ttyUSB0
b). Connect the HDMI cable to monitor.
c). Power on the device using 5V power adapter.

Bingo! ‘gtkterm’ started showing the boot-up script logs. After validation image got loaded onto RAM, Beagle Board logo got displayed in my monitor, followed by linux kernel boot logs which ended in login shell. Just enter ‘root’ in the username field and that is all!

Making of “Jai Ganesh – Yeh Jo Desh Hai Tera”.

As mentioned in my other blog, on the occasion of Ganesh Festival, me and my friend Sonam had taken nearly 4750+ photographs with the intention of making a small video. Keeping the efforts to take the photographs apart, we had spent more than a week to make a video from these photographs. We used both Linux and Windows softwares to make this video (Though I wish I should have used only Linux softwares :)). This blog outlines the method we followed.

1. Well, the first task for us to convert all photographs from original 4200×3400 to smaller resolution of 640×480, as it is pointless to have such high resolution for video. Manually selecting each files and converting to lower resolution using some photo editing softwares was painful (rather impossible), given that we had 4750+ photographs. So, we wrote a small shell script to convert all images to lower resolution, this script was run whole night and all photographs were converted in one go. This script uses ‘convert’ utility provided by ImageMagick. Below is the script,


#/bin/sh

for f in *.JPG; do
convert -resize 640x480 $f `basename $f`.jpg;
rm $f
done

2. The one special effect in the video are the clips which of made up of multiple-shot photographs. Nearly 300 photographs were taken to make a multi-shot clip of 30sec at the rate of 10fps. We used ‘mencoder’ provided by mplayer to encode all these photographs as a mpeg clip. Following command will generate an MPEG clip of 10fps using all photographs present in current directory.


mencoder "mf://*.jpg" -mf fps=10 -o 8.mpeg -ovc lavc -lavcopts vcodec=mjpeg

Don’t ask me what other options do in the above command. I really have no idea why they are needed also. It was just a copy paste from one of internet resource, and I am lazy, I didn’t had the patience to look what each options do 🙂

3. Now its the time of making the actual video using multi-shot clips, other images and a music track. We tried various Linux softwares, like Cinelerra, KDEnlive, Kino, Lives etc. None of them proved good for our purpose, or probably we didn’t had the patience to learn them! We switched to Windows and used a software called ‘CyberLink PowerDirector Ultra 8.00’. This software has really cool UI interface which allow easy video editing, music track addition, transition effects etc. I must admit, there are few of things in which Windows out-performs Linux, hopefully this gap gets narrowed quickly.

4. Thats it. Our video is now ready MPEG format! One last step was to convert this video into FLV format, so that we can upload them in Youtube. Linux ffmpeg does it for us. It reduced the original size of 172MB into 32MB FLV file.

ffmpeg -i JaiGanesh.mpeg -b 600k -r 30 -ab 128k -ar 44100 -s 640x480 -ac 2 -y JaiGanesh.flv

Hope you enjoyed the video. Do drop you feedback. Jai Ganesh!. 🙂

I am a saint in the church of emacs!

There’s always a war between the most powerful editors – emacs v/s vi. This rivalry has become a lasting part of hacker culture and the free software community. I was a happy user of vi, until I discovered the power of emacs. And now, trust me, I just love using emacs, its one of my passion. I believe, I can spend entire day with just emacs opened and without switching to any other window. This sweet editor has support for gdb, autocomplete, cscope, compilation, emails and even browser. What more could one wish for? In this post, I will talk about some tips to add wings to emacs and make it fly freely.

When you have a project with thousands of million lines of code, like linux kernel source or webkit source, it necessitates to have some source code navigation tools. Mostly obvious choice is cscope. How about integrating cscope with emacs? Well, you have xcscope!

Installation of xcscope is very simple,
a). Download xcscope. Make sure that, this file is saved in some path searchable by emacs.
b). Make sure cscope-indexer is installed.
c). Edit your emacs and this line
    (require 'xcscope)
d). Optionally, have key bindings for some of the common cscope commands,
    (define-key global-map [(ctrl f3)] 'cscope-set-initial-directory)
    (define-key global-map [(ctrl f4)] 'cscope-unset-initial-directory)
    (define-key global-map [(ctrl f5)] 'cscope-find-this-symbol)
    (define-key global-map [(ctrl f6)] 'cscope-find-global-definition-no-prompting)
    (define-key global-map [(ctrl f7)] 'cscope-find-egrep-pattern)
    (define-key global-map [(ctrl f8)] 'cscope-find-this-file)
    (define-key global-map [(ctrl f9)] 'cscope-next-symbol)
    (define-key global-map [(ctrl f10)] 'cscope-next-file)
    (define-key global-map [(ctrl f11)] 'cscope-prev-symbol)
    (define-key global-map [(ctrl f12)] 'cscope-prev-file)
    (define-key global-map [(meta f9)] 'cscope-display-buffer)
    (define-key global-map [(meta f10)] 'cscope-display-buffer-toggle)

Hmmm. My emacs looked better with cscope, but, we, the engineers are lazy typing lots of code. That when I found Emacs Auto Complete. This pretty lisp package has a very neat way of displaying drop-down with list of possible auto completion. Worth having it in your emacs.

Whats more? Want to integrate Git inside emacs? Check GIT emacs. Though I am not really impressed with the features of this packages, it does serve the purpose.

M-x compile allows you to invoke the compilation from within emacs. One issue which I had with compilation buffer is, some characters from compilation output were not getting displayed, instead their ascii codes used to get displayed. It turns out that, we need to tell emacs that compilation output is in UTF-8, so that it can interpret them correctly. To do so, have this line in you .emacs file.
(prefer-coding-system 'utf-8)

Other annoying part of compilation buffer is, its not used to get scrolled as compilation goes. To automatically scroll the compilation buffer and stop scrolling when an error occurs, add these line in .emacs.
(custom-set-variables
'(compilation-scroll-output first-error))

Cool. My emacs looks a lot prettier now, but, there is something that made it to look sad! Yes, the fonts. I really hated the default font of emacs!. I always wished to have ‘monospace’ font to which vim defaults to. Well, you got to do following steps to have monospace font.

echo "Emacs.font: Monospace-10" >> ~/.Xresources
xrdb -merge ~/.Xresources

Now my emacs is the most sexiest editor and I am one of the happy saints in the church of emacs!

Knapsack Problem

I feel, Knapsack problem is one of the most interesting puzzle to solve. Given a set of items, each with a weight and a value, Knapsack puzzle asks us to determine the number of each item to include in a collection so that the total weight is less than a given limit and the total value is as large as possible. Imagine you in a plane, which is about to crash if certain quantity of goods is not trowed away from flight. Certainly, your program needs to be as quick as possible, otherwise, flight might crash before your program gives you the output. I am sure, you would strive to get the very optimal algorithm, after all life matters more than the goods.. 🙂

There are 2 variations of Knapsack’s problem,
1. 0/1 Knapsack problem – Which restricts the number of items to be included in Knapsack to either 0 or 1.
2. Unbounded Knapsack problem – There is no limit on number of items that could be included in Knapsack.

This section, I will discuss about the solving unbounded Knapsack problem with Dynamic programming approach.

In a dynamic programming solution to the knapsack problem, we calculate the best combination for all Knapsack sizes up to M (Knapsack capacity). Also, let us assume we have N items. It turns out that we can perform this calculation very efficiently by doing things in an appropriate order, as in the following program:


for j:=l to N do
begin
for i:=l to M do
if i-size[j]>=O then
if cost[i]<(cost[i-size[j]]+val[j])
begin
cost[i]:=cost[i-size[j]]+val[j];
best[i] :=j
end ;
end ;

In this program, cost[i] is the highest value that can be achieved with a knapsack of capacity i and best [i] is the last item that was added to achieve that maximum (this is used to recover the contents of the knapsack, as described below). First, we calculate the best that we can do for all knapsack sizes when only items of type A are taken, then we calculate the best that we can do when only A’s and B’s are taken, etc. The solution reduces to a simple calculation for cost [i]. Suppose an item j is chosen for the knapsack: then the best value that could be achieved for the total would be val[j] (for the item) plus cost [i-size(j)] (to fill up the rest of the knapsack). If this value exceeds the best value that can be achieved without an item j, then we update cost [i] and best[i]; otherwise we leave them alone.

For instance, consider the items of following sizes and values,

name A B C D E
size 3 4 7 8 9
value 4 5 10 11 13

The following table traces the comptation for our example. The first pair of lines shows the best that can be done (the contents of the cost and best arrays) with only A’s, the second pair of lines shows the best that can be done with only A’s and B’s, etc.:


1 2 3 4 5 6 7 8 9 1011121314151617
0 0 4 4 4 8 8 8 12 12 12 16 16 16 202020
A A A A A A A A A A A A A A A
0 0 4 5 5 8 9 10 12 13 14 16 17 18 20 21 22
A B B A B B A B B A B B A B B
0 0 4 5 5 8 10 10 12 14 15 16 18 20 20 22 24
A B B A C B A C C A C C A C C
0 0 4 5 5 8 10 11 12 14 15 16 18 20 21 22 24
A B B A C D A C C A C C D C C
0 0 4 5 5 8 10 11 13 14 15 17 18 20 21 23 24
A B B A C D E C C E C C D E

Here is a final note on complexity of this algorithm. It is obvious from inspection of the code that the running time of this algorithm is proportional to NM. Thus, it will be fine if M is not large, but could become unacceptable for large capacities.

C++ implementation of Knapsack problem can be found here.

References:
[A] Algorithms – By Robert Sedgewick
[B] http://en.wikipedia.org/wiki/Knapsack_problem.

Mouse cursor not visible in Xoo emulator in Karmic (Ubuntu 9.10).

I am a fan Ubuntu Linux, and usually try every new version of Ubuntu as and when it gets released. Till very recently I had Ubuntu 8.04 (Hardy) installed at my office workstation, but I thought lets give a try to Karmic. (Un)Fortunately, my Hardy got screwed up while doing some experiments with it, and now I had a valid reason to reinstall/upgrade of my OS, and so Karmic got installed. 🙂

Everything went well with Karmic, but mouse cursor wasn’t visible in Xoo emulator with Xnest/Xephyr. Xoo is a GTK2 based graphical wrapper around a ‘Windowed’ X Server. The X server is typically Xnest, the nested X server, or Xephyr. It is intended for embedded developers that want to simulate a target device (with an accurate display size, working hardware buttons, etc) on a desktop machine. Emulator used start with following error message, but mouse wasn’t visible at all!!!.


/usr/share/fonts/X11/cyrillic, removing from list!
unrecognised device identifier!
(EE) config/hal: NewInputDeviceRequest failed
unrecognised device identifier!
(EE) config/hal: NewInputDeviceRequest failed
unrecognised device identifier!

Did lot of circus to resolve this error, searched in net, found some some similar topics (like meamo developers), but none of the posts resolved my error.

Finally, found out though some web sources that, Karmic doesn’t have Xnest support, but instead of Xephyr need to be used in Karmic. By default, Xoo starts Xephyr server, but to get host cursor, one need to start xoo with following argument,


xoo -xo -host-cursor

Basically, I just had to pass -host-cursor as argument to Xserver through Xoo.

Uff.. Kind off wasted a day trying to find this single line solution. Hence, thought of sharing this info with all.

Create your own SVN repository for Free with Google.

  • Do you write lot of code?
  • Do you create a lot of revisions of code which are hard to manage by yourself?
  • Do you wish to host your own project online and ask your friends to contribute it?

    Well, if the answer is ‘Yes’ for above, then you should try online project hosting with Google code. Its simple, easy to use and has got tremendous capabilities built in it. Refer Project hosting with Google code for more details.

    I created a test project called ‘Knapsack‘ in Google code, approach I followed was,
    1. I used to SVN as versioning tool.
    2. Followed the procedure mentioned here to check out the initial empty code.
    3. Did svn add to add KnapSack.cpp file to SVN repository.
    4. Check’ed in the code. Thats it!!

    Other interesting options which Google code includes are allowing many people to contribute to your project, getting email notifications upon check-in etc. Having said, now you could start contributing to my KnapSack project.. 🙂

    Bottom line, Google Rocks!! And so is Open Source!!

  • Hello World!

    Being a computer science engineer and a programmer, first post I could think of is “Hello world!”, and here is my “Hello world!”.

    
    void main()
    {
        printf("Hello World!");
    }
    
    

    I’ll try to write up some useful technical stuffs in this blog. Stay tuned!.