jond3k jond3k - 6 months ago 25
Javascript Question

Why does this V8/Javascript code perform so badly?

I've been looking at some interesting programming benchmarks to see how well node.js might perform compared to other languages: http://benchmarksgame.alioth.debian.org/u32/compare.php?lang=node&lang2=php

While the results deal primarily with algorithmic problems that you would normally prefer to solve with a variant of C or Fortran, one test stands out as incredibly bad for V8:

pidigits - 52x slower than PHP

Since v8 performs better across the board than PHP in all the other tests I presume there is either something wrong with the code or some specific to the implementation of V8/Javascript that makes it perform so badly. What is it?

Code 1: V8

// The Computer Language Benchmarks Game
// http://shootout.alioth.debian.org
//
// Contributed by Matthew Wilson
// biginteger derived from Tom Wu's jsbn.js


var compareTo, multiply, divide, addTo, add, intValue, shiftLeft, nbv;

function main($n) {
var $i=1, $s="", $d, neg10=nbv(-10), three=nbv(3), ten=nbv(10), g = 1, $g,
digits=Array(10), $z0=nbv(1), $z1=nbv(0), $z2=nbv(1), negdigits=Array(10),
k = 0, $k, l = 2, $l, a;

for(var i=0; i<10; ++i) { negdigits[i] = multiply(digits[i] = nbv(i),neg10) }

do {
while ( compareTo($z0,$z2) > 0
|| ($d = intValue(divide(add(multiply($z0,three),$z1),$z2))) !=
intValue(divide(add(shiftLeft($z0,2),$z1),$z2))
) {
$z1 = multiply($z1,$g = nbv(g+=2));
$z2 = multiply($z2,$g);
addTo($z1, multiply($z0,$l = nbv(l+=4)), $z1);
$z0 = multiply($z0,$k = nbv(++k));
}
$z0 = multiply($z0,ten);
$z1 = multiply($z1,ten);
addTo($z1, multiply($z2,negdigits[$d]), $z1);
$s += $d;

if ($i % 10 == 0) { print($s+"\t:"+$i); $s="" }
} while (++$i <= $n)

if (($i = $n % 10) != 0) { $s += Array(11-$i).join(' ') }
if ($s.length > 0) { print($s+"\t:"+$n) }
}

var functions;
load('/home/dunham/shootout/bench/Include/javascript/biginteger.js');

compareTo=functions[0];
multiply=functions[1];
divide=functions[2];
addTo=functions[3];
add=functions[4];
nbv=functions[5];
shiftLeft=functions[6];
intValue=functions[7];

main.call(this, 1*arguments[0]*1)


Code 2: PHP

<?php /* The Great Computer Language Shootout
http://shootout.alioth.debian.org/
contributed by Isaac Gouy
php -q pidigits.php 27
*/

class Transformation {
var $q, $r, $s, $t, $k;

function Transformation($q, $r, $s, $t){
$this->q = $q;
$this->r = $r;
$this->s = $s;
$this->t = $t;
}

function Unity(){
return new Transformation("1", "0", "0", "1");
}

function Zero(){
return new Transformation("0", "0", "0", "0");
}

function Compose($a){
$qq = bcmul($this->q, $a->q);
$qrrt = bcadd(bcmul($this->q, $a->r), bcmul($this->r, $a->t));
$sqts = bcadd(bcmul($this->s, $a->q), bcmul($this->t, $a->s));
$srtt = bcadd(bcmul($this->s, $a->r), bcmul($this->t, $a->t));
return new Transformation($qq, $qrrt, $sqts, $srtt);
}

function Extract($j){
$bigj = strval($j);
$qjr = bcadd(bcmul($this->q, $bigj), $this->r);
$sjt = bcadd(bcmul($this->s, $bigj), $this->t);
$d = bcdiv($qjr, $sjt);
return floor($d);
}

function Next(){
$this->k = $this->k + 1;
$this->q = strval($this->k);
$this->r = strval(4*$this->k + 2);
$this->s = "0";
$this->t = strval(2*$this->k + 1);
return $this;
}
}

class PiDigitStream {
var $z, $x, $inverse;

function PiDigitStream(){
$this->z = Transformation::Unity();
$this->x = Transformation::Zero();
$this->inverse = Transformation::Zero();
}

function Produce($j){
$i = $this->inverse;
$i->q = "10";
$i->r = strval(-10*$j);
$i->s = "0";
$i->t = "1";
return $i->Compose($this->z);
}

function Consume($a){
return $this->z ->Compose($a);
}

function Digit(){
return $this->z ->Extract(3);
}

function IsSafe($j){
return $j == ($this->z ->Extract(4));
}

function Next(){
$y = $this->Digit();
if ($this->IsSafe($y)){
$this->z = $this->Produce($y);
return $y;
} else {
$this->z = $this->Consume($this->x ->Next());
return $this->Next();
}
}
}


$n = $argv[1];
$i = 0;
$length = 10;
$pidigit = new PiDigitStream;

while ($n > 0){
if ($n < $length){
for ($j=0; $j<$n; $j++) printf("%d",$pidigit->Next());
for ($j=$n; $j<$length; $j++) print " ";
$i += $n;
} else {
for ($j=0; $j<$length; $j++) printf("%d",$pidigit->Next());
$i += $length;
}
print "\t:$i\n";
$n -= $length;
}
?>

Answer

PHP is using the BC Math library highly optimized GMP library for its calculations, which is written in C (and assembly in some places), where the V8 version uses a big integer class written in JavaScript (it says "based on" Tom Wu's jsbn.js). It's probably more accurate to say that the benchmark is comparing V8 and C big integer performance than V8 and PHP.

The PHP code in the question is a different version of the PHP entry that uses the BC Math library, and is actually slower than V8 (thanks igouy). The BC library is also written in C, but it works with base 10 numbers (it's a PHP wrapper for the library used by the GNU versions of dc and bc) and isn't as heavily optimized as GMP.

Comments