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

with No comments:
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);
}
}

0 comments:

Post a Comment