Thursday, August 6, 2015

Recursion with PHP 7, HHVM 3.8, Javascript, Java and C/C++ (Update: Go, Zephir)

Lessons learned:
  • HHVM runs recursive function calls 20 times faster than PHP
  • HHVM runs recursive function calls as fast as Javascript
  • HHVM runs recursive function calls 3 times slower than Java
  • HHVM runs recursive function calls 5 times slower than C
  • HHVM runs recursive function calls 2 times slower than Go

Here is a sample script using the Ackermann function:
<?php

function ack($n, $m) {
  if ($n == 0) return $m + 1;
    else if ($m == 0) return ack($n - 1, 1);
    else return ack($n - 1, ack($n, $m - 1));
}

function ack_while($n, $m) {
  while ($n != 0) {
    if ($m == 0) $m = 1;
      else $m = ack_while($n, $m - 1);
    $n--;
  }
  return $m + 1;
}

$start = microtime(true);
ack_while(3, 10);
echo number_format(microtime(true)-$start, 4).'s'.PHP_EOL;

$start = microtime(true);
ack(3, 10);
echo number_format(microtime(true)-$start, 4).'s'.PHP_EOL;

Here is a sample script using the Fibonacci function:
<?php

function fib_it($n) {
  $a = 0;
  $b = 1;
  for ($i = 0; $i < $n; $i++){
    $sum = $a+$b;
    $a = $b;
    $b = $sum;
  }
  return $a;
}

function fib_rec($n) {
  if ($n < 3) return 1;
  return fib_rec($n - 1) + fib_rec($n - 2);
}

$start = microtime(true);
fib_it(40);
echo number_format(microtime(true)-$start, 4).'s'.PHP_EOL;

$start = microtime(true);
fib_rec(40);
echo number_format(microtime(true)-$start, 4).'s'.PHP_EOL;

Results: (AMD Opteron 6128 3Ghz virtualized, 64bit)

fib(40) PHP 5.5.9:
0.0000s
45.0391s

fib(40) PHP 7.0.0:
0.0000s
19.4653s

fib(40) with HHVM 3.8.1:
0.0060s
1.7428s

fib(40) with Go 1.2.1:
0.0000017s
0.9577085s

fib(40) with Java OpenJDK 1.7:
0.0s
0.565s

fib(40) with C (gcc 4.7):
0.358s

fib(40) with Javascript (node.js 0.10.25):
0.007s
1.667s

fib(40) with Zephir (0.7.1b):
0.000s
did not finish.


ack(3,10) PHP 5.5.9:
14.5458s
16.1864s

ack(3,10) PHP 7.0.0:
3.5186s
6.0263s

ack(3,10) with HHVM 3.8.1:
Fatal error: Stack overflow in /ack.php on line 12

ack(3,10) with Go 1.2.1:
0.292307s
0.346981s

ack(3,10) with Java OpenJDK 1.7:
0.121
0.222

ack(3,10) with C (gcc 4.7):
0.090s

ack(3,10) with Javascript (node.js 0.10.25):
0.378s
0.657s

ack(3,10) with Zephir (0.7.1b):
PHP Fatal error: Maximum recursion depth exceeded in Command line code on line 1

ack.c (run: gcc -O3 -o ack.out ack.c && time ./ack.out)
unsigned int ack(unsigned int n, unsigned int m) {
  if (n == 0) return m + 1;
    else if (m == 0) return ack(n - 1, 1);
    else return ack(n - 1, ack(n, m - 1));
}

unsigned int ack_while(unsigned int n, unsigned int m) {
  while (n != 0) {
    if (m == 0) {
      m = 1;
    } else {
      m = ack_while(n, m - 1);
    }
    n--;
  }
  return m + 1;
}

int main(int argc, char* argv[]) {
  ack_while(3, 10);
  ack(3, 10);
}

fib.c (run: gcc -O3 -o fib.out fib.c && time ./fib.out)
unsigned int fib_it(unsigned int n) {
  unsigned int a = 0;
  unsigned int b = 1;
  unsigned int sum;
  unsigned int i;
  for (i = 0; i < n; i++){
    sum = a + b;
    a = b;
    b = sum;
  }
  return a;
}

unsigned int fib_rec(unsigned int n) {
  if (n < 3) return 1;
  return fib_rec(n - 1) + fib_rec(n - 2);
}

int main(int argc, char* argv[]) {
  fib_it(40);
  fib_rec(40);
}

ack.js (run: time nodejs ack.js)
function ack(n, m) {
  if (n == 0) return m + 1;
    else if (m == 0) return ack(n - 1, 1);
    else return ack(n - 1, ack(n, m - 1));
}

function ack_while(n, m) {
  while (n != 0) {
    if (m == 0) {
      m = 1;
    } else {
      m = ack_while(n, m - 1);
    }
    n--;
  }
  return m + 1;
}

var start = new Date().getTime();
ack_while(3, 10);
console.log((new Date().getTime() - start) / 1000 + 's');

start = new Date().getTime();
ack(3, 10);
console.log((new Date().getTime() - start) / 1000 + 's');

fib.js (run: time nodejs fib.js)
function fib_it(n) {
  var a = 0;
  var b = 1;
  var sum = 0;
  for (var i = 0; i < n; i++){
    sum = a + b;
    a = b;
    b = sum;
  }
  return a;
}

function fib_rec(n) {
  if (n < 3) return 1;
  return fib_rec(n - 1) + fib_rec(n - 2);
}

var start = new Date().getTime();
fib_it(40);
console.log((new Date().getTime() - start) / 1000 + 's');

start = new Date().getTime();
fib_rec(40);
console.log((new Date().getTime() - start) / 1000 + 's');

ack.java (run: javac -g:none ack.java && java ack)
public class ack {
  public static int ack(int n, int m) {
    if (n == 0) return m + 1;
      else if (m == 0) return ack(n - 1, 1);
      else return ack(n - 1, ack(n, m - 1));
  }

  public static int ack_while(int n, int m) {
    while (n != 0) {
      if (m == 0) {
        m = 1;
      } else {
        m = ack_while(n, m - 1);
      }
      n--;
    }
    return m + 1;
  }

  public static void main(String[] args) throws Exception {
    long start = System.currentTimeMillis();
    ack_while(3, 10);
    System.out.println((float) (System.currentTimeMillis() - start) / 1000);

    start = System.currentTimeMillis();
    ack(3, 10);
    System.out.println((float)(System.currentTimeMillis() - start) / 1000);
  }
}

fib.java (run: javac -g:none fib.java && java fib)
public class fib {
  public static int fib_it(int n) {
    int a = 0;
    int b = 1;
    int sum;
    for (int i = 0; i < n; i++){
      sum = a + b;
      a = b;
      b = sum;
    }
    return a;
  }

  public static int fib_rec(int n) {
    if (n < 3) return 1;
    return fib_rec(n - 1) + fib_rec(n - 2);
  }

  public static void main(String[] args) throws Exception {
    long start = System.currentTimeMillis();
    fib_it(40);
    System.out.println((float) (System.currentTimeMillis() - start) / 1000);

    start = System.currentTimeMillis();
    fib_rec(40);
    System.out.println((float)(System.currentTimeMillis() - start) / 1000);
  }
}

fib.go (run: go run fib.go)
package main

import "fmt"
import "time"

func main() {
    t := time.Now()
    fib_it(40)
    fmt.Println(time.Now().Sub(t))

    t = time.Now()
    fib_rec(40)
    fmt.Println(time.Now().Sub(t))
}

func fib_it(n int) int {
    a := 0
    b := 1
    var sum int
    
    for i := 0; i < n; i++ {
      sum = a + b
      a = b
      b = sum
    }
    return a
}

func fib_rec(n int) int {
    if n < 3 {
        return 1
    }
    return fib_rec(n - 1) + fib_rec(n - 2)
}

ack.go (run: go run ack.go)
package main

import "fmt"
import "time"

func main() {
    t := time.Now()
    ack_while(3, 10)
    fmt.Println(time.Now().Sub(t))

    t = time.Now()
    ack(3, 10)
    fmt.Println(time.Now().Sub(t))
}

func ack_while(n int, m int) int {
    for i := n; i > 0; i-- {
        if m == 0 {
            m = 1
        } else {
            m = ack_while(i, m - 1)
        }
    }
    return m + 1
}

func ack(n int, m int) int {
    if n == 0 {
        return m + 1
    } else if m == 0 {
        return ack(n - 1, 1)
    }
    return ack(n - 1, ack(n, m - 1));
}

example.zep (run: zephir init utils && vi utils/example.zep && zephir build && php -d extension=utils.so -r 'echo Utils\Example::run();')
namespace Utils;

class Example {

public static function run() {
    var start;
    let start = microtime(true);
    self::ack(3, 8);
    echo (microtime(true) - start) . PHP_EOL;

    let start = microtime(true);
    self::ack_while(3, 8);
    echo (microtime(true) - start) . PHP_EOL;
}
    
public static function ack(int n, int m) {
    if (n == 0) {
        return m + 1;
    } elseif (m == 0) {
        return self::ack(n - 1, 1);
    } else {
        return self::ack(n - 1, self::ack(n, m - 1));
    }
}

public static function ack_while(int n, var m) {
    while (n != 0) {
        if (m == 0) {
            let m = 1;
        } else {
            let m = self::ack_while(n, m - 1);
        }
        let n--;
    }
    return m + 1;
}
}

example.zep (run: zephir init utils && vi utils/example.zep && zephir build && php -d extension=utils.so -r 'echo Utils\Example::run();')
namespace Utils;

class Example {

public static function run() {
    var start;
    let start = microtime(true);
    self::fib_it(40);
    echo (microtime(true) - start) . PHP_EOL;

    let start = microtime(true);
    self::fib_rec(40);
    echo (microtime(true) - start) . PHP_EOL;
}
    
public static function fib_it(int n) {
    int a = 0;
    int b = 1;
    int sum;
    
    int i = 0;
    while (i < n) {
      let sum = a + b;
      let a = b;
      let b = sum;
      let i++;
    }
    return a;
}

public static function fib_rec(int n) {
    if (n < 3) {
        return 1;
    }
    return self::fib_rec(n - 1) + self::fib_rec(n - 2);
}
}

1 comment:

Labels

performance (23) benchmark (6) MySQL (5) architecture (5) coding style (5) memory usage (5) HHVM (4) C++ (3) Java (3) Javascript (3) MVC (3) SQL (3) abstraction layer (3) framework (3) maintenance (3) Go (2) Golang (2) HTML5 (2) ORM (2) PDF (2) Slim (2) Symfony (2) Zend Framework (2) Zephir (2) firewall (2) log files (2) loops (2) quality (2) real-time (2) scrum (2) streaming (2) AOP (1) Apache (1) Arrays (1) C (1) DDoS (1) Deployment (1) DoS (1) Dropbox (1) HTML to PDF (1) HipHop (1) OCR (1) OOP (1) Objects (1) PDO (1) PHP extension (1) PhantomJS (1) SPL (1) SQLite (1) Server-Sent Events (1) Silex (1) Smarty (1) SplFixedArray (1) Unicode (1) V8 (1) analytics (1) annotations (1) apc (1) archiving (1) autoloading (1) awk (1) caching (1) code quality (1) column store (1) common mistakes (1) configuration (1) controller (1) decisions (1) design patterns (1) disk space (1) dynamic routing (1) file cache (1) garbage collector (1) good developer (1) html2pdf (1) internationalization (1) invoice (1) just-in-time compiler (1) kiss (1) knockd (1) legacy code (1) legacy systems (1) logtop (1) memcache (1) memcached (1) micro framework (1) ncat (1) node.js (1) openssh (1) pfff (1) php7 (1) phpng (1) procedure models (1) ramdisk (1) recursion (1) refactoring (1) references (1) regular expressions (1) search (1) security (1) sgrep (1) shm (1) sorting (1) spatch (1) ssh (1) strange behavior (1) swig (1) template engine (1) threads (1) translation (1) ubuntu (1) ufw (1) web server (1) whois (1)