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 →

strpos() vs. preg_match() vs. stripos()

Lessons learned:

• strpos() is 3-16 times faster than preg_match()
• stripos() is 2-30 times slower than strpos()
• stripos() is 20-100 percent faster than preg_match() with the caseless modifier "//i"
• using a regular expression in preg_match() is not faster than using a long string
• using the utf8 modifier "//u" in preg_match() makes it 2 times slower

Here is a sample script to compare the functions with different string sizes:

<?php

function loop(){

$str_50 = str_repeat('a', 50).str_repeat('b', 50);
$str_100 = str_repeat('a', 100).str_repeat('b', 100);
$str_500 = str_repeat('a', 250).str_repeat('b', 250);
$str_1k = str_repeat('a', 1024).str_repeat('b', 1024);
$str_10k = str_repeat('a', 10240).str_repeat('b', 1024);
$str_100k = str_repeat('a', 102400).str_repeat('b', 1024);
$str_500k = str_repeat('a', 1024*500).str_repeat('b', 1024);
$str_1m = str_repeat('a', 1024*1024).str_repeat('b', 1024);

$b = 'b';
$b_10 = str_repeat('b', 10);
$b_100 = str_repeat('b', 100);
$b_1k = str_repeat('b', 1024);

echo str_replace(',', "\t", ',strpos,preg,preg U,preg S,preg regex,stripos,preg u,'.
  'preg i,preg u i,preg i regex,stripos uc,preg i uc,preg i uc regex').PHP_EOL;

foreach (array($b, $b_10, $b_100, $b_1k) as $needle) {
  foreach (array($str_50, $str_100, $str_500, $str_1k, $str_10k,
    $str_100k, $str_500k, $str_1m) as $str) {

    echo strlen($needle).'/'.strlen($str);

    $start = mt();
    for ($i=0; $i<25000; $i++) $j = strpos($str, $needle); // strpos
    echo "\t".mt($start);
    
    $regex = '!'.$needle.'!';
    $start = mt();
    for ($i=0; $i<25000; $i++) $j = preg_match($regex, $str); // preg
    echo "\t".mt($start);

    $regex = '!'.$needle.'!U';
    $start = mt();
    for ($i=0; $i<25000; $i++) $j = preg_match($regex, $str); // preg Ungreedy
    echo "\t".mt($start);

    $regex = '!'.$needle.'!S';
    $start = mt();
    for ($i=0; $i<25000; $i++) $j = preg_match($regex, $str); // preg extra analysiS
    echo "\t".mt($start);

    $regex = "!b{".strlen($needle)."}!";
    $start = mt();
    for ($i=0; $i<25000; $i++) $j = preg_match($regex, $str); // preg regex
    echo "\t".mt($start);
    
    $start = mt();
    for ($i=0; $i<25000; $i++) $j = stripos($str, $needle); // stripos
    echo "\t".mt($start);

    $regex = '!'.$needle.'!u';
    $start = mt();
    for ($i=0; $i<25000; $i++) $j = preg_match($regex, $str); // preg utf-8
    echo "\t".mt($start);

    $regex = '!'.$needle.'!i';
    $start = mt();
    for ($i=0; $i<25000; $i++) $j = preg_match($regex, $str); // preg i
    echo "\t".mt($start);

    $regex = '!'.$needle.'!ui';
    $start = mt();
    for ($i=0; $i<25000; $i++) $j = preg_match($regex, $str); // preg i utf-8
    echo "\t".mt($start);

    $regex = "!b{".strlen($needle)."}!i";
    $start = mt();
    for ($i=0; $i<25000; $i++) $j = preg_match($regex, $str); // preg i regex
    echo "\t".mt($start);

    echo PHP_EOL;
  }
  echo PHP_EOL;
}
}

function mt($start=null){
  if ($start === null) return microtime(true);
  return number_format(microtime(true)-$start, 4);
}

loop();

Running with PHP 5.4.4, 64bit, 2.3GHz (QEMU):

	strpos	preg	preg U	preg S	preg regex	stripos	preg u	preg i	preg u i	preg i regex
1/100	0.0052	0.0144	0.0147	0.0172	0.0168	0.0102	0.0180	0.0153	0.0195	0.0143
1/200	0.0058	0.0177	0.0166	0.0159	0.0143	0.0121	0.0229	0.0160	0.0236	0.0159
1/500	0.0061	0.0237	0.0246	0.0236	0.0219	0.0215	0.0394	0.0217	0.0383	0.0212
1/2048	0.0087	0.0589	0.0590	0.0580	0.0359	0.0645	0.1205	0.0499	0.1077	0.0472
1/11264	0.0221	0.2693	0.2672	0.2640	0.2443	0.3115	0.5939	0.3631	0.6803	0.3662
1/103424	0.1867	2.3432	2.3384	2.3575	2.3211	2.9327	5.3040	3.4689	6.4391	3.4750
1/513024	1.0228	11.4006	11.3530	12.0689	11.3858	14.5023	26.0701	17.2658	31.6543	16.9941
1/1049600	2.0988	23.3561	23.3382	23.3811	23.4459	30.2119	52.9937	34.9654	64.4141	35.1033
10/100	0.0055	0.0167	0.0171	0.0166	0.0148	0.0104	0.0199	0.0158	0.0215	0.0150
10/200	0.0053	0.0165	0.0155	0.0180	0.0151	0.0125	0.0222	0.0167	0.0264	0.0175
10/500	0.0065	0.0247	0.0226	0.0219	0.0179	0.0207	0.0391	0.0222	0.0376	0.0236
10/2048	0.0088	0.0590	0.0578	0.0625	0.0371	0.0649	0.1192	0.0503	0.1108	0.0484
10/11264	0.0212	0.2701	0.2652	0.2617	0.2412	0.3068	0.5838	0.3553	0.6652	0.3491
10/103424	0.1542	2.3274	2.2972	2.2938	2.2765	2.7586	5.1789	3.4096	6.3119	3.3939
10/513024	0.7236	11.4388	11.4880	11.4932	11.3312	14.1851	25.7927	17.1388	32.1902	17.5287
10/1049600	1.4951	23.4072	23.2000	23.4175	23.2439	29.6794	53.0526	34.9641	64.9861	35.9626
100/100	0.0063	0.1963	0.1956	0.0186	0.1264	0.0146	0.2922	0.2061	0.2281	0.1397
100/200	0.0060	0.0234	0.0219	0.0219	0.0212	0.0180	0.0296	0.0309	0.0422	0.0235
100/500	0.0071	0.0304	0.0297	0.0291	0.0250	0.0273	0.0452	0.0376	0.0559	0.0310
100/2048	0.0103	0.0671	0.0681	0.0676	0.0428	0.0762	0.1329	0.0665	0.1239	0.0516
100/11264	0.0210	0.2625	0.2623	0.2642	0.2422	0.3067	0.5762	0.3600	0.6774	0.3548
100/103424	0.1474	2.2864	2.2856	2.3114	2.2968	2.7858	5.2261	3.4506	6.3282	3.4003
100/513024	0.7241	11.4054	11.4286	11.3435	11.5313	14.1507	25.6885	17.1702	31.8195	17.1162
100/1049600	1.4736	23.2258	23.4724	23.2595	23.3052	29.4276	53.4051	35.2015	64.3818	34.6691
1024/100	0.0047	0.2033	0.2041	0.0517	0.1042	0.0083	0.2899	0.2092	0.2290	0.1204
1024/200	0.0049	0.0562	0.0554	0.0563	0.2900	0.0109	0.0615	0.5340	0.6496	0.3281
1024/500	0.0049	0.0647	0.0638	0.0637	1.3358	0.0181	0.0761	2.5063	3.2811	1.4076
1024/2048	0.0069	0.0955	0.0954	0.0963	0.0688	0.0887	0.1526	0.1536	0.2367	0.0809
1024/11264	0.0195	0.2974	0.2982	0.3000	0.2817	0.3375	0.6168	0.4718	0.8103	0.3845
1024/103424	0.1524	2.3356	2.3316	2.3477	2.3338	2.8351	5.2727	3.5535	6.4703	3.4583
1024/513024	0.7217	11.4283	11.5377	11.4987	11.4162	14.2862	25.8131	17.1762	33.1633	18.1542
1024/1049600	1.4657	23.3272	23.2205	23.2752	23.6812	29.1804	54.9962	34.9720	64.7529	37.1609

Running with HHVM 3.0/2014.03.27, 64bit, 2.3GHz (QEMU):

	strpos	preg	preg U	preg S	preg regex	stripos	preg u	preg i	preg u i	preg i regex
1/100	0.0028	0.0081	0.0085	0.0079	0.0079	0.0039	0.0124	0.0084	0.0125	0.0085
1/200	0.0021	0.0093	0.0094	0.0092	0.0094	0.0045	0.0167	0.0091	0.0162	0.0088
1/500	0.0021	0.0160	0.0183	0.0168	0.0121	0.0102	0.0341	0.0154	0.0309	0.0138
1/2048	0.0051	0.0541	0.0531	0.0523	0.0302	0.0374	0.1118	0.0396	0.0980	0.0394
1/11264	0.0176	0.2531	0.2537	0.2541	0.2373	0.3415	0.5682	0.3451	0.6602	0.3436
1/103424	0.1781	2.2955	2.2846	2.2814	2.2535	3.3880	5.2139	3.3744	6.2748	3.4123
1/513024	1.0425	11.3477	11.6653	11.4149	11.3018	16.9227	26.7142	17.2595	31.6541	17.2308
1/1049600	2.1241	23.2635	23.2525	23.3054	23.2256	34.9508	52.7012	34.9024	64.5221	34.9430
10/100	0.0013	0.0084	0.0084	0.0086	0.0076	0.0040	0.0126	0.0086	0.0119	0.0077
10/200	0.0014	0.0089	0.0091	0.0091	0.0088	0.0063	0.0158	0.0108	0.0167	0.0095
10/500	0.0020	0.0155	0.0158	0.0157	0.0120	0.0129	0.0308	0.0156	0.0308	0.0147
10/2048	0.0073	0.0500	0.0496	0.0505	0.0295	0.0477	0.1088	0.0410	0.1032	0.0397
10/11264	0.0169	0.2536	0.2522	0.2519	0.2312	0.4572	0.5668	0.3498	0.6614	0.3443
10/103424	0.1829	2.3130	2.2926	2.3003	2.2826	4.5526	5.2329	3.4511	6.4243	3.4623
10/513024	1.0610	11.5358	11.5248	11.4948	11.4198	22.9372	25.9165	17.0674	31.4214	16.9746
10/1049600	2.0783	23.8131	23.7319	23.1988	23.2098	46.5398	53.5480	35.4728	65.4561	35.6284
100/100	0.0012	0.0065	0.0062	0.0066	0.0058	0.0017	0.0112	0.0066	0.0101	0.0059
100/200	0.0013	0.0102	0.0101	0.0103	0.0118	0.0106	0.0172	0.0173	0.0250	0.0126
100/500	0.0018	0.0165	0.0163	0.0166	0.0149	0.0170	0.0320	0.0219	0.0383	0.0176
100/2048	0.0042	0.0505	0.0503	0.0508	0.0318	0.0510	0.1090	0.0473	0.1085	0.0432
100/11264	0.0178	0.2556	0.2535	0.2552	0.2356	0.4605	0.5690	0.3537	0.6825	0.3559
100/103424	0.1764	2.2992	2.3004	2.2966	2.2881	4.5522	5.1924	3.4346	6.2967	3.4354
100/513024	1.0296	11.3657	11.3776	11.3046	11.4125	22.5889	26.0071	16.9886	32.3710	16.9588
100/1049600	2.1064	23.4239	23.3236	23.2174	23.1929	46.4756	53.4129	34.8542	65.2457	35.4284
1024/100	0.0013	0.0116	0.0117	0.0121	0.0060	0.0009	0.0216	0.0122	0.0154	0.0058
1024/200	0.0009	0.0151	0.0151	0.0154	0.0071	0.0009	0.0279	0.0139	0.0201	0.0074
1024/500	0.0009	0.0216	0.0216	0.0219	0.0104	0.0009	0.0426	0.0190	0.0331	0.0132
1024/2048	0.0030	0.0557	0.0556	0.0562	0.0632	0.0939	0.1197	0.1173	0.1947	0.0742
1024/11264	0.0161	0.2624	0.2590	0.2588	0.2659	0.4981	0.5789	0.4164	0.7576	0.3794
1024/103424	0.1467	2.2902	2.3172	2.2994	2.2857	4.5648	5.2119	3.4726	6.3626	3.4485
1024/513024	0.7160	11.3871	11.4345	11.3034	11.4561	22.7561	25.8564	17.0333	31.4014	16.9700
1024/1049600	1.4864	23.1771	23.1033	23.4143	23.3364	47.5513	55.7561	36.7900	64.7846	35.1457

Read More →

The power of column stores

• using column stores instead of row based stores can reduce access logs from 10 GB to 130 MB of disk space
• reading compressed log files is 4 times faster than reading uncompressed files from hard disk
• column stores can speed up analytical queries by a factor of 18-58

Normally, log files from a web server are stored in a single file. For archiving, log files get compressed with gzip. A typical line in a log file represents one request and looks like this:

173.15.3.XXX - - [30/May/2012:00:37:35 +0200] "GET /cms/ext/files/Sgs01Thumbs/sgs_pmwiki2.jpg HTTP/1.1" 200 14241 "http://www.simple-groupware.de/cms/ManualPrint" "Mozilla/5.0 (Windows NT 5.1; rv:12.0) Gecko/20100101 Firefox/12.0"

Compression speeds up reading the log file:

$start = microtime(true);
$fp = gzopen("httpd.log.gz", "r");
while (!gzeof($fp)) gzread($fp, 8192);
gzclose($fp);
echo (microtime(true)-$start)."s\n"; // 26s

$start = microtime(true);
$fp = fopen("httpd.log", "r");
while (!feof($fp)) fread($fp, 8192);
fclose($fp);
echo (microtime(true)-$start)."s\n"; // 105s

(PHP 5.4.5, 2.5 GHz, hard disk with 7200rpm)

Having a log file of 10 GB gives a compressed file with 600 MB using gzip. This is already quite good, but can we make it better?

In the example line, we have different attributes (=columns) separated by " " and []. For example:

ip=173.15.3.XXX
date=30/May/2012:00:37:35 +0200
status=200
length=14241
url=http://www.simple-groupware.de/cms/ManualPrint
agent=Mozilla/5.0 (Windows NT 5.1; rv:12.0) Gecko/20100101 Firefox/12.0
etc.

When we save each column in a separate file, we will get smaller files after the compression. Using a file for the HTTP status code column contains many similar values (mostly 200), which allows better compression.

Coming from 600 MB, we can reduce the total size to 280 MB by saving each column to a different file.

Analyzing files containing only one column is also much easier. For example, we can do a group by over all status codes on the shell with:

time zcat status.log.gz | sort | uniq -c
36689940 200
  11880 206
 124560 301
1142820 302
 968040 304
   3600 401
  37080 403
 784260 404
    180 405
   6480 408

real    0m31.600s
user    0m27.038s
sys     0m1.436s

Note: instead of sorting, it will be faster to fill a small hash table with the counts.

Counting is also very fast:

# get number of requests with status code equal to 200
time zcat status.log.gz | grep -E "^200$" | wc -l
36689940

real    0m3.078s
user    0m2.944s
sys     0m0.128s

# get number of requests with status code not equal to 200
time zcat status.log.gz | grep -Ev ^200$ | wc -l
3078900

real    0m1.799s
user    0m1.736s
sys     0m0.060s

Summing:

# sum up all transferred bytes (5.5951e+11 ~ 521 GB)
time zcat length.log.gz | awk '{s+=$1}END{print s}'
5.5951e+11

real    0m5.708s
user    0m5.556s
sys     0m0.144s

The biggest column is normally the one containing URLs (118 MB in our example). We can reduce the size by assigning a unique ID to each URL and save the list of URLs in a separate file.

Coming from 280 MB, we can reduce the total size to 130 MB by splitting URLs, referers and user agents into 2 files.

Here is the code for splitting a log file into column based files:

$urls = [];
$agents = [];
$split_urls = true;
$split_agents = true;

$fp_ip = gzopen("ip.log.gz", "w");
$fp_user = gzopen("user.log.gz", "w");
$fp_client = gzopen("client.log.gz", "w");
$fp_date = gzopen("date.log.gz", "w");
$fp_url = gzopen("urls.log.gz", "w");
$fp_url_list = gzopen("urls_list.log.gz", "w");
$fp_status = gzopen("status.log.gz", "w");
$fp_length = gzopen("length.log.gz", "w");
$fp_referer = gzopen("referer.log.gz", "w");
$fp_agent = gzopen("agent.log.gz", "w");
$fp_agent_list = gzopen("agent_list.log.gz", "w");

$fp = gzopen("httpd.log.gz", "r");
while (!gzeof($fp)) {
  $line = gzgets($fp, 8192);
  preg_match("!^([0-9\.]+) ([^ ]+) ([^ ]+) \[([^\]]+)\] \"(?:GET )?([^\"]*)".
    " HTTP/1\.[01]\" ([^ ]+) ([^ ]+) \"([^\"]*)\" \"([^\"]*)\"\$!", $line, $m);
  if (empty($m)) {
    echo $line." ###"; // output broken lines
    continue;
  }
  gzwrite($fp_ip, $m[1]."\n");
  gzwrite($fp_user, ($m[2]=="-" ? "" : $m[2])."\n");
  gzwrite($fp_client, ($m[3]=="-" ? "" : $m[3])."\n");
  gzwrite($fp_date, $m[4]."\n");

  if ($split_urls) {
    if (!isset($urls[$m[5]])) $urls[$m[5]] = count($urls)-1;
    gzwrite($fp_url, $urls[$m[5]]."\n");
  } else {
    gzwrite($fp_url, $m[5]."\n");
  }
  gzwrite($fp_status, $m[6]."\n");
  gzwrite($fp_length, ($m[7]=="-" ? "0" : $m[7])."\n");
  
  if ($m[8]=="-") {
    gzwrite($fp_referer, "\n");
  } else if ($split_urls) {
    if (!isset($urls[$m[8]])) $urls[$m[8]] = count($urls)-1;
    gzwrite($fp_referer, $urls[$m[8]]."\n");
  } else {
    gzwrite($fp_referer, $m[8]."\n");
  }
  if ($m[9]=="-") {
    gzwrite($fp_agent, "\n");
  } else if ($split_agents) {
    if (!isset($agents[$m[9]])) $agents[$m[9]] = count($agents)-1;
    gzwrite($fp_agent, $agents[$m[9]]."\n");
  } else {
    gzwrite($fp_agent, $m[9]."\n");
  }
}
gzwrite($fp_url_list, implode("\n", array_keys($urls)));
gzwrite($fp_agent_list, implode("\n", array_keys($agents)));

gzclose($fp);
gzclose($fp_ip);
gzclose($fp_user);
gzclose($fp_client);
gzclose($fp_date);
gzclose($fp_url);
gzclose($fp_url_list);
gzclose($fp_status);
gzclose($fp_length);
gzclose($fp_referer);
gzclose($fp_agent);
gzclose($fp_agent_list);

Note: Reading data from disk is always slower than analyzing data in real-time when the data is in memory.

Read More →

How to implement a real life benchmark with PHP

To determine the maximum capacity of a web page, Apache ab is often used in the first step. Fetching one URL very often is optimal for caching and gives a best case. To get the worst case for caching, it is necessary to fetch different URLs in a random order.

Here is a PHP script to walk randomly on a web page:

To get the average case concerning caching and response times, we need to choose the most relevant links. For example, we skip links from headers and footers. This can be done by using a different xpath expression in the code:

// fetch all links under <div id="content">...</div>
$xpath = '//div[@id="content"]//a';

// fetch all links under <div id="content"> and <div id="menu">
$xpath = '//div[@id="content" or @id="menu"]//a';

To make the benchmark more realistic, you can define a waiting period between two requests: Uncomment "// sleep(1)" at the end of the script.
To get the right values for $limit (number of pages per user) and $processes (number of users), you can consult your favorite analytics tool.

Example output:

php random_crawler.php >details.log

Testing http://www.spiegel.de/, 100 requests, 10 processes
#2393 start 10 requests
#2395 start 10 requests
#2396 start 10 requests
#2394 start 10 requests
#2399 start 10 requests
#2397 start 10 requests
#2398 start 10 requests
#2402 start 10 requests
#2401 start 10 requests
#2400 start 10 requests
#2398 end 188/815 KB 3.54s 0.35s/req
#2393 end 176/751 KB 3.78s 0.38s/req
#2396 end 153/562 KB 3.90s 0.39s/req
#2401 end 137/628 KB 4.19s 0.42s/req
#2397 end 149/456 KB 4.89s 0.49s/req
#2399 end 156/525 KB 4.90s 0.49s/req
#2402 end 171/619 KB 5.95s 0.60s/req
#2400 end 127/349 KB 7.40s 0.74s/req
#2394 end 157/465 KB 8.36s 0.84s/req
#2395 end 167/662 KB 10.62s 1.06s/req

(sizes shown as compressed/uncompressed)

Read More →