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;
}
?>

I'd guess the javascript code is passing the actual (bigint?) values being computed, and the PHP version is only passing references. — Ira Baxter
– Ira Baxter, Commented Aug 11, 2011 at 13:23
PHP uses BC Math extension which implements arbitrary precision arithmetic in C or C++ while JavaScript code relies on some biginteger.js which I suppose implements arbitrary precision arithmetic in pure JavaScript. Unfortunately I could not find biginteger.js anywhere, so I wrote to Isaac asking for source. — Vyacheslav Egorov
– Vyacheslav Egorov, Commented Aug 11, 2011 at 13:36
See the updated JavaScript program: benchmarksgame.alioth.debian.org/u64q/… — igouy
– igouy, Commented Jun 1, 2016 at 17:31

Matthew Crumley · Accepted Answer · 2011-08-12 17:33:50Z

7

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.

edited Aug 12, 2011 at 17:33

answered Aug 11, 2011 at 13:44

Matthew Crumley

103k24 gold badges105 silver badges131 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

jond3k Over a year ago

Thanks Matthew. Someone has also written gmp bindings for node.js. While it would be interesting to see how optimized versions of PHP and node.js perform, I think this highlights the futility of judging languages by performance benchmarks - it's not impossible to glue different languages together thereby benefiting from the best of both worlds.

igouy Over a year ago

The PHP program that's 52x faster already does use GMP. shootout.alioth.debian.org/u32/…

igouy Over a year ago

@jond3k - What it highlights is that performance measurements measure the performance of programs.

Zach Kelling Over a year ago

@jond3k I decided to see how well the gmp bindings for node would perform, so I rewrote the javascript version using node-bigint. It does as well as you'd expect (see my answer for details).

igouy · Accepted Answer · 2016-05-27 01:49:58Z

3

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);

edited May 27, 2016 at 1:49

igouy

2,70018 silver badges18 bronze badges

answered May 29, 2012 at 19:23

Zach Kelling

54.1k15 gold badges112 silver badges108 bronze badges

4 Comments

Zach Kelling Over a year ago

@igouy Feel free to use my benchmark. Assuming you have Node.js and GMP building the wrapper is as simple as npm install bigint.

igouy Over a year ago

The benchmarks game actually uses Node.js now, so it would be great if you worked through the bureaucracy and contributed your program -- benchmarksgame.alioth.debian.org/play.html

igouy Over a year ago

Sadly lots of errors -- make: Entering directory '/home/dunham/node_modules/bigint/build' CXX(target) Release/obj.target/bigint/bigint.o ../bigint.cc:57:27: error: expected class-name before ‘{’ token class BigInt : ObjectWrap { ^ ../bigint.cc:74:34: error: ‘Arguments’ does not name a type static Handle<Value> New(const Arguments& args);

igouy Over a year ago

See the updated JavaScript program: benchmarksgame.alioth.debian.org/u64q/…

Collectives™ on Stack Overflow

Why does this V8/Javascript code perform so badly?

2 Answers 2

4 Comments

Results

Source

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Results

Source

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related