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

Read More →

For or Foreach? PHP vs. Javascript, C++, Java, HHVM (update: Go, Zephir)

Lessons learned:

• Foreach is 4-5 times faster than For
• Nested Foreach is 2-3 times faster than nested For
• Foreach with key lookup is 2-3 times slower than Foreach without
• C++ is 5-300 times faster than PHP running For/Foreach on Arrays
• HHVM is 2-3 times faster than PHP
• PHP 7 is 2-4 times faster than PHP 5.5
• HHVM is currently no alternative to C++
• Javascript is 2-20 times slower than C++/Java running For on nested Arrays
• Go is 4-20 times faster than HHVM

Here is a sample script:

<?php
function test(){
// init arrays
$array = array();
for ($i=0; $i<50000; $i++) $array[] = $i*2;

$array2 = array();
for ($i=20000; $i<21000; $i++) $array2[] = $i*2;

// test1: foreach big-array (foreach small-array)
$start = microtime(true);
foreach ($array as $val) {
  foreach ($array2 as $val2) if ($val == $val2) {}
}
echo number_format(microtime(true)-$start, 2)."s\n";

// test1b: foreach big-array (foreach small-array)
$start = microtime(true);
foreach ($array as $val) {
  foreach ($array2 as $val2) if ($val === $val2) {}
}
echo number_format(microtime(true)-$start, 2)."s\n";

// test2: foreach small-array (foreach big-array)
$start = microtime(true);
foreach ($array2 as $val2) {
  foreach ($array as $val) if ($val == $val2) {}
}
echo number_format(microtime(true)-$start, 2)."s\n";

// test3: foreach big-array (foreach small-array) with key lookup
$start = microtime(true);
foreach ($array as $key=>$val) {
  foreach ($array2 as $key2=>$val2) if ($array[$key] == $array2[$key2]) {}
}
echo number_format(microtime(true)-$start, 2)."s\n";

// test4: foreach small-array (foreach big-array) with key lookup
$start = microtime(true);
foreach ($array2 as $key=>$val2) {
  foreach ($array as $val) if ($array[$key] == $array2[$key2]) {}
}
echo number_format(microtime(true)-$start, 2)."s\n";

// test5: for big-array (for small-array)
$start = microtime(true);
$count = count($array);
$count2 = count($array2);
for ($key=0; $key<$count; $key++) {
  for ($key2=0; $key2<$count2; $key2++) if ($array[$key] == $array2[$key2]) {}
}
echo number_format(microtime(true)-$start, 2)."s\n";

// test6: for small-array (for big-array)
$start = microtime(true);
$count = count($array);
$count2 = count($array2);
for ($key2=0; $key2<$count2; $key2++) {
  for ($key=0; $key<$count; $key++) if ($array[$key] == $array2[$key2]) {}
}
echo number_format(microtime(true)-$start, 2)."s\n";

$array = array();
for ($i=0; $i<1000000; $i++) $array[] = $i*2;

// test7: foreach big-array
$start = microtime(true);
foreach ($array as &$val) $val++;
echo number_format(microtime(true)-$start, 2)."s\n";

// test8: for big-array
$start = microtime(true);
for ($key=0; $key<count($array); $key++) $array[$key]++;
echo number_format(microtime(true)-$start, 2)."s\n";

// test8b: for big-array, doing count() outside the loop!
$start = microtime(true);
$count = count($array);
for ($key=0; $key<$count; $key++) $array[$key]++;
echo number_format(microtime(true)-$start, 2)."s\n";
}
test();

Here are some results from PHP 5.4.4 and HHVM (2014-05-04, QEMU 2.3 GHz, 64bit):

php	hhvm
2.78s	0.47s
2.90s	0.44s
2.97s	0.44s
6.90s	1.36s
6.27s	1.33s
5.83s	1.13s
6.24s	1.15s
0.07s	0.04s
0.24s	0.04s
0.11s	0.03s

Using HHVM instead of PHP gives big improvements.

With Javascript (node.js) you'll get similar values:
example.js (run: node example.js)

var array = [];
for (i=0; i<50000; i++) array.push(i*2);

var array2 = [];
for (i=20000; i<21000; i++) array2.push(i*2);

// js-test1: for big-array (for small array)
var start = new Date().getTime();
var length = array.length;
var length2 = array2.length;
for (key=0; key<length; key++) {
  for (key2=0; key2<length2; key2++) if (array[key] == array2[key2]) {}
}
console.log((new Date().getTime() - start) / 1000); // 1.53s

// js-test2: foreach big-array (foreach small array)
start = new Date().getTime();
for (key in array) {
  for (key2 in array2) if (array[key] == array2[key2]) {}
}
console.log((new Date().getTime() - start) / 1000); // 6.32s

var array3 = [];
for (i=0; i<1000000; i++) array3.push(i*2);

// js-test3: for big-array
start = new Date().getTime();
length3 = array3.length;
for (key=0; key<length3; key++) array3[key]++;
console.log((new Date().getTime() - start) / 1000); // 0.03s

tested with QEMU 2.3 GHz, node.js v0.10

With C++ (gcc 4.6 win32) you'll also get similar values:
example.cpp (run: g++ -o example example.cpp && ./example)

#include <sys/time.h>
#include <stdio.h>
#include <vector>
using namespace std;

main() {
  struct timeval start, end;

  vector<int> array;
  for(int i=0; i < 50000; i++) array.push_back(i*2);

  vector<int> array2;
  for(int i=20000; i < 21000; i++) array2.push_back(i*2);

  gettimeofday(&start, NULL);
  int array_size = array.size();
  int array2_size = array2.size();
  for (int key=0; key<array_size; key++)
    for (int key2=0; key2<array2_size; key2++)
      if (array[key] == array2[key2]) {}

  gettimeofday(&end, NULL);
  printf("%lf\n", (float)(end.tv_sec - start.tv_sec +
    (end.tv_usec - start.tv_usec)/1000000.0)); // 0.61s, 0.00s (-O3)

  vector<int> array3;
  for(int i=0; i < 1000000; i++) array3.push_back(i*2);

  gettimeofday(&start, NULL);
  int array3_size = array3.size();
  for(int i=0; i < array3_size; i++) array3[i]++;
  gettimeofday(&end, NULL);
  printf("%lf\n", (float)(end.tv_sec - start.tv_sec +
    (end.tv_usec - start.tv_usec)/1000000.0)); // 0.009s, 0.001s (-O3)
}

tested with QEMU 2.3 GHz, gcc 4.7

And Java (Java 1.7 win64):

example.java (run: javac -g:none example.java && java example)

import java.util.ArrayList;
import java.util.Vector;

public class example {
  public static void main(String[] args) throws Exception {

    ArrayList<Integer> array = new ArrayList<Integer>();
    for (int i = 0; i < 50000; i++) array.add(i*2);

    ArrayList<Integer> array2 = new ArrayList<Integer>();
    for (int i = 20000; i < 21000; i++) array2.add(i*2);

    long start = System.currentTimeMillis();
    int array_size = array.size();
    int array2_size = array2.size();
    for (int key = 0; key < array_size; key++)
      for (int key2 = 0; key2 < array2_size; key2++)
        if (array.get(key).equals(array2.get(key2))) {}
    System.out.println((float) (System.currentTimeMillis() - start) / 1000);
    // 0.066s

    Vector<Integer> varray = new Vector<Integer>();
    for (int i = 0; i < 50000; i++) varray.add(i*2);

    Vector<Integer> varray2 = new Vector<Integer>();
    for (int i = 20000; i < 21000; i++) varray2.add(i*2);

    start = System.currentTimeMillis();
    int varray_size = varray.size();
    int varray2_size = varray2.size();
    for (int key = 0; key < varray_size; key++)
      for (int key2 = 0; key2 < varray2_size; key2++)
        if (varray.get(key).equals(varray2.get(key2))) {}
    System.out.println((float) (System.currentTimeMillis() - start) / 1000);
    // 1.652s

    ArrayList<Integer> array3 = new ArrayList<Integer>();
    for (int i = 0; i < 1000000; i++) array3.add(i*2);

    start = System.currentTimeMillis();
    int array3_size = array3.size();
    for (int i = 0; i < array3_size; i++) array3.set(i, array3.get(i)+1);
    System.out.println((float)(System.currentTimeMillis() - start) / 1000);
    // 0.164s

    Vector<Integer> varray3 = new Vector<Integer>();
    for (int i = 0; i < 1000000; i++) varray3.add(i*2);

    start = System.currentTimeMillis();
    int varray3_size = varray3.size();
    for (int i = 0; i < varray3_size; i++) varray3.set(i, varray3.get(i)+1);
    System.out.println((float)(System.currentTimeMillis() - start) / 1000);
    // 0.074s
  }
}

tested with QEMU 2.3 GHz, OpenJDK 1.6, 64bit

Go (1.4.2):

example.go (run: go build example.go && ./example)

package main

import "fmt"
import "time"

func main() {
    var array [50000]int
    for i := 0; i < 50000; i++ { array[i] = i*2 }

    var array2 [1000]int
    for i := 20000; i < 21000; i++ { array2[i-20000] = i*2 }

    t := time.Now()
    length := len(array)
    length2 := len(array2)
    for key := 0; key < length; key++ {
      for key2 := 0; key2 < length2; key2++ {
        if (array[key] == array2[key2]) {}
      }
    }
    fmt.Println(time.Now().Sub(t)) // 157.855682ms

    var array3 [1000000]int
    for i := 0; i < 1000000; i++ { array3[i] = i*2 }

    t2 := time.Now()
    length3 := len(array3)
    for key := 0; key < length3; key++ { array3[key]++ }
    fmt.Println(time.Now().Sub(t2)) // 4.363528ms
}

Zephir (0.7.1b):

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() {
    int i, i2;
    array array1 = [];
    let i = 0;
    while (i < 50000) {
        let array1[] = i*2;
        let i++;
    }

    array array2 = [];
    let i = 20000;
    while (i < 21000) {
        let array2[] = i*2;
        let i++;
    }

    var start;
    let start = microtime(true);
    int length, length2;
    let length = count(array1);
    let length2 = count(array2);
    let i = 0, i2 = 0;
    while (i < length) {
        while (i2 < length2) {
            if (array1[i] == array2[i2]) {}
            let i2++;
        }
        let i++;
    }    
    echo (microtime(true) - start) . PHP_EOL;
    
    array array3 = [];
    let i = 0;
    while (i < 1000000) {
        let array3[] = i*2;
        let i++;
    }

    let start = microtime(true);
    int length3;
    let length3 = count(array3);
    let i = 0;
    while (i < length3) {
        let array3[i] += 1;
        let i++;
    }
    echo (microtime(true) - start) . PHP_EOL;
}
}

New results (AMD Opteron 6128 2GHz virtualized):

php 5.5.9 4.71 4.77 6.43 9.20 10.81 8.76 11.09 0.15 0.37 0.20

php 7.0 2015-8-1 1.34 1.69 1.39 3.79 3.36 3.51 3.69 0.11 0.12 0.08

hhvm 3.8.1 0.65 0.61 0.68 1.34 1.44 1.06 1.14 0.09 0.07 0.05

node.js 0.10.25 1.953 9.218 0.051

c++ gcc 4.8.4 0.91601 0.01149

c++ -O3 gcc 4.8.4 0.00000 0.00101

go 1.4.2 0.15866 0.00427

OpenJDK 1.7.0_79 0.114 3.732 0.124 0.253

Zephir 0.7.1b 0.0001 0.1510

Note:

int len = array.size(); for (int key=0; key < len; key++)

instead of

for (int key=0; key < array.size(); key++)

makes the code 30 percent faster!

Read More →