Why does this V8/Javascript code perform so badly?

Question

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 1

Out of curiosity, I wrote an alternate version using node-bigint (which wraps libgmp). I compared the fastest C implementation to my version of the benchmark. Performance is as you'd expect, around that of the other language implementations using libgmp.

Results

C (compiled with gcc -pipe -Wall -O3 -fomit-frame-pointer pidigits.c -o pidigits -lgmp)

./pidigits-c 10000  1.11s user 0.00s system 99% cpu 1.116 total

node (0.6.18)

node pidigits-gmp.js 10000  3.61s user 3.15s system 100% cpu 6.712 total

Source

var bigint = require('bigint');

function calculatePi(N) {
  var i = 0,
      k = 0,
      k1 = 1,
      ns = 0,

      a = bigint(0),
      d = bigint(1),
      m = bigint(0),
      n = bigint(1),
      t = bigint(0),
      u = bigint(0);

  while (1) {
    k += 1;
    k1 += 2;
    t = n.shiftLeft(1);
    n = n.mul(k);
    a = a.add(t).mul(k1);
    d = d.mul(k1);

    if (a.cmp(n) >= 0) {
      m = n.mul(3).add(a);
      t = m.div(d);
      u = m.mod(d).add(n);

      if (d.cmp(u) > 0) {
        ns = ns * 10 + t.toNumber();
        i += 1;

        if (i % 10 === 0) {
          console.log(ns + '\t:' + i);
          ns = 0;
        }

        if (i >= N) break;

        a = a.sub(d.mul(t)).mul(10);
        n = n.mul(10);
      }
    }
  }
}

calculatePi(process.argv[2] || 10);

Answer 2

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.