PHP at the speed of C

For common cases, most dynamic languages are “fast enough”. For most PHP applications, the most overhead is probably hitting network services like the database, and this accounts for far more of the run time than the speed of the language’s function calls. Also, PHP is a fairly thin glue layer on top of a lot of C libraries, which mean that for any significant algorithmic work, you’re probably already calling out to a C library underneath. If this wasn’t the case, basic operations like string searches and regular expressions would be extremely slow.

However, every now and again you do want to do something with PHP that does involve complex algorithms, for which you might not have a C library to hand. Even if you do have a C library or the ability to create one, writing extensions for PHP to expose this functionality has a bit of a learning curve. Wouldn’t it be nice if we could write code in PHP, and have it accelerated somehow to C-like speeds?

The Mandelbrot set

The Mandelbrot set is a set of complex numbers generated using an algorithm that involves a large number of iterations. When plotted with an appropriate colouring scheme, they make fractals which can look very nice. Plotting them is relatively simple, though it’s quite CPU intensive. I have written some fairly na├»ve code to generate these images, which you can find in this gist. The output looks like this:

Mandelbrot set

There’s a fair bit of code there, but the function that takes most of the time is the mandelbrot() one. It’s where all the iteration happens. On the VM I’m testing this in1 it takes around 80 seconds to run, under a release build of PHP 5.6.5:

vagrant@vagrant-ubuntu-trusty-64:~/src$ php colourmandel.php
Data took 78.744249
Render took 0.631219

That’s pretty slow, by any metric. It’s iterating up to 4096 times for every pixel in an 800x512 image, so unlike most PHP apps it’s going to be CPU-bound rather than dependent on the network or other services. I wonder if there’s a way to speed it up, without having to drop down to pure C?

HHVM

Well, one way is to install HHVM:

vagrant@vagrant-ubuntu-trusty-64:~/src$ hhvm mandelbrot.php
Data took 5.852351
Render took 0.236238

HHVM, in its default setup, features a Just-In-Time (JIT) compiler, that traces every code path that is executed. If it finds a path that is “hot” – executed a large number of times – it will jump in and compile that code branch down to straight machine code and execute that instead. As this code is essentially arithmetic taking place in a tight loop, it’s a perfect case for HHVM’s JIT compiler to jump in and optimize.

If you’ve got complete control over your infrastructure and don’t mind changing PHP implementations, HHVM could well be the way to go. It also has a number of other extras which may be of interest. But what if you don’t?

Recki Compiler Toolkit

Recently, Anthony Ferrara (known throughout the Internet and beyond as @ircmaxell) and Joe Watkins (similarly well-known as @krakjoe) have been working on a new set of toys for solving this problem while staying on the “standard” PHP runtime. Recki-CT is a set of tools that implement a PHP compiler, in PHP. While this might you think of things like PyPy, which implements a Python virtual machine in Python, this is not Recki’s goal – it doesn’t provide a VM, so it can’t run PHP by itself. However, it can parse PHP code and generate other code from it.

Recki uses the well-known PHP-Parser library by Nikita Popov to generate a graph-based representation of the code, and convert it to an intermediate representation. To get here involves a few steps, which are described in Recki’s documentation, but essentially:

  • It generates a tree-based representation of the code called an abstract syntax tree
  • From the AST, it generates a control flow graph
  • It then converts this graph into static single assignment form, where every variable is only assigned once, and all are defined before use. This makes it simpler to optimize.
  • Next, it repeatedly runs optimizations on this graph

This intermediate form is pretty low-level, and it is comparatively simple to generate code from it for a variety of targets. One of the targets Recki can use is a second component, JitFu, which is a PHP extension allowing us to generate machine code at run time.

First steps with Recki and JitFu

So, I’ve decided I’m not yet ready to throw out all my existing infrastructure, and that (perhaps) I’m tied to some extensions that currently only work on main-line PHP. Where do I start?

First off, I need to follow the instructions on Recki’s README, which include installing libjit and the JitFu extension. Then, we need to install Recki using Composer, and then add Composer’s autoloader to the top of the PHP file as normal. Once we have these in place, we can start to look at how to use JitFu to speed our code up.

composer require recki-ct/recki-ct

If you have a look at the mandelbrot() function in the file, we can see it does all the work itself. For each pixel in the image, it iterates over a mathematical function until either the absolute value of the complex number “escapes” (tends towards infinity), or it hits the maximum number of iterations that we’ve previously defined to be 4096.

For each row of pixels in the image it will create an array containing the number of iterations for each pixel. Then, it creates another array representing columns, which contains the list of rows. Finally, the render() function is used to convert the number of iterations into a colour, but we can ignore that for now as it’s fairly quick by comparison.

We’ll change the main() function so that it will attempt to precompile the mandelbrot() function, and then execute that. Also, we’ll need to tell Recki what the expected input and output types are for our function so that it knows what it’s dealing with. We do this using a docblock, in the same way that we would if we were using phpDocumentor or similar. You can see this version of the code here.

 1 /**
 2  * @param double $xMin
 3  * @param double $xMax
 4  * @param double $yMin
 5  * @param double $yMax
 6  * @param int $xPx
 7  * @param int $yPx
 8  * @return array
 9  */
10  function mandelbrot($xMin, $xMax, $yMin, $yMax, $xPx, $yPx)
11  // ...

And now the changes to the main function – these replace lines 100 to 104:

1     $start = microtime(true);
2     $function = ReckiCT\Jit::jitfu('mandelbrot');
3     printf("Compiling took %F\n", $mandelTime);
4 
5     $start = microtime(true);
6     $data = $function($xMin, $xMax, $yMin, $yMax, $xPx, $yPx);
7     $mandelTime = microtime(true) - $start;
8     printf("Data took %F\n", $mandelTime);

Then we try and run it:

vagrant@vagrant-ubuntu-trusty-64:~/src/recki-ct$ php mandelbrotWithRecki.php

Fatal error: Uncaught exception 'LogicException' with message 'Found node without parser rule: Expr_Array' in /home/vagrant/src/recki-ct/lib/ReckiCT/Parser/Parser.php:112
Stack trace:
#0 /home/vagrant/src/recki-ct/lib/ReckiCT/Parser/Rules/Assign.php(41): ReckiCT\Parser\Parser->parseNode(Object(PhpParser\Node\Expr\Array_), Object(ReckiCT\Parser\State))
#1 /home/vagrant/src/recki-ct/lib/ReckiCT/Parser/Parser.php(109): ReckiCT\Parser\Rules\Assign->parse(Object(PhpParser\Node\Expr\Assign), Object(ReckiCT\Parser\State))
#2 /home/vagrant/src/recki-ct/lib/ReckiCT/Parser/Parser.php(96): ReckiCT\Parser\Parser->parseNode(Object(PhpParser\Node\Expr\Assign), Object(ReckiCT\Parser\State))
#3 /home/vagrant/src/recki-ct/lib/ReckiCT/Parser/Parser.php(86): ReckiCT\Parser\Parser->parseStmtList(Array, Object(ReckiCT\Parser\State))
#4 /home/vagrant/src/recki-ct/lib/ReckiCT/Jit.php(222): ReckiCT\Parser\Parser->parseFunction(Object(PhpParser\Node\Stmt\Function_))
#5 /home/vagrant/src/recki-ct/lib/ReckiCT/Jit.php(240): ReckiCT\Jit->getFunctionG in /home/vagrant/src/recki-ct/lib/ReckiCT/Parser/Parser.php on line 112

Oh. The problem here is that Recki is still pretty young (it’s only around 6 months since its first release), and it currently doesn’t handle arrays. That’s OK, we can refactor the code a little, and break out the part of the iteration that returns a number into a separate function, which looks like the one below. Note that Recki doesn’t currently do constant lookups either, so we pass the maximum number of iterations as a parameter.

 1 /**
 2  * @param double $cReal
 3  * @param double $cImag
 4  * @param int $maxIterations
 5  * @return int
 6  */
 7 function mandelbrotIteration($cReal, $cImag, $maxIterations)
 8 {
 9     $originalReal = $cReal;
10     $originalImag = $cImag;
11 
12     $ni = 0;
13     while ($ni < $maxIterations && ($cReal * $cReal * $cImag * $cImag < 4.0)) {
14         $tmp = $cReal * $cReal - $cImag * $cImag + $originalReal;
15         $cImag = $cImag * $cReal * 2 + $originalImag;
16         $cReal = $tmp;
17 
18         $ni++;
19     }
20 
21     if ($ni == $maxIterations) {
22         $ni = 0;
23     }
24 
25     return $ni;
26 }

The new version of the file is here. Now, let’s try it:

vagrant@vagrant-ubuntu-trusty-64:~/src/recki-ct$ php mandelbrotAfterRefactor.php
Compiling took 1.537641
Data took 3.724597
Render took 0.595848

Not bad! It took about 1.5 seconds to compile, and then ran in 3.7 - somewhere around a 2100% improvement! We can do a little better too, as we can grab the intermediate representation that JitFu has made, and cache it.

 1     if (file_exists('mandelbrotIteration.ir')) {
 2         $start = microtime(true);
 3         $ir = file_get_contents('mandelbrotIteration.ir');
 4         $iterationFunc = ReckiCT\Jit::getInstance()->compileIrJitFu($ir, 'fibo');
 5         $loadTime = microtime(true) - $start;
 6         printf("Loading took %F\n", $loadTime);
 7     } else {
 8         $start = microtime(true);
 9         $iterationFunc = ReckiCT\Jit::jitfu('mandelbrotIteration');
10         $compileTime = microtime(true) - $start;
11         printf("Compiling took %F\n", $compileTime);
12         file_put_contents('mandelbrotIteration.ir', 
13             ReckiCT\Jit::getInstance()->getFunctionIr('mandelbrotIteration'));
14     }

Follow along with the code here. Now let’s see how that looks:

vagrant@vagrant-ubuntu-trusty-64:~/src/recki-ct$ php mandelbrotWithCachedIR.php
Loading took 0.177504
Data took 3.636709
Render took 0.653733

Nice.

The next step with Recki

Recki has another trick up its sleeve that we’ve not seen yet. Earlier, I hinted that it can generate code for multiple targets. One of these targets happens to be C code, wrapped in a PHP extension. This might be an interesting option for people who are a little wary of running code like JitFu on their production servers. Also, it means we can throw all of the knowledge and tricks contained within our C compiler at the code as well, to get as much speed as possible.

To demonstrate this, let’s lift the mandelbrotIteration() function right out of the code, and put it in its own file. I’ll call it iteration.php, and you can see it here. I can then run this command, assuming I’m in the Recki-CT root directory:

php bin/compile_pecl compile -O mandelbrot iteration.php

I’m passing the -O option, which passes -O3 to the C compiler to dial up its own optimizations. You should see some familiar text scrolling past as Recki generates, configures, and compiles a PECL extension for us. Next, we can return to our Mandelbrot code rip out all the additions we put in for our JitFu experiments, and indeed remove the mandelbrotIteration() function entirely. I’ve chosen to wrap it inside a function_exists() check instead, so that I can test with or without the extension loaded to prove I get the same output. You can get that version here.

vagrant@vagrant-ubuntu-trusty-64:~/src/recki-ct$ php -dextension=./mandelbrot.so mandelbrotWithExtension.php
Data took 2.411557
Render took 0.637504

Now we’re down to 2.4 seconds. Not bad at all. Remember, we’re only optimizing the innermost loop here – once Recki is able to optimize functions using arrays, we could potentially speed it up even further.

Summary

Recki-CT is a very young project, so this is not the kind of thing I’d be looking to use in production quite yet, but it’s certainly something to keep an eye on. Particularly where we have certain functions within our applications that are very CPU-heavy, we might well be able to take a considerable amount of load off by optimizing just those functions and leaving the rest of our app stack as standard. As mentioned before, PHP has been talked about in the past as being a glue layer between C libraries and application code. If we can write PHP and generate optimized C code from that, then the barrier to entry for taking advantage of this is considerably lower.

Update

For comparison, I translated the code to straight C reasonably directly, which you can see here. It’s a standalone C program, not a PHP extension. It runs in around 2.1 seconds on the same VM:

vagrant@vagrant-ubuntu-trusty-64:~/src/Mandelbrot-browser$ ./basic-mandelbrot
Data took 2.107163
Render took 0.000840

1. I realise that VMs don't give a terribly accurate benchmark, but these tests deal with orders of magnitude, so they'll reflect the speed difference enough to be getting on with.