Friday, August 29, 2014

Introducing Recki-CT

Over 1.5 years ago, I introduced PHPPHP to the world. It was the first implementation of the PHP language written in PHP itself. But PHPPHP suffered from a few problems which relegated it to toy status (such as performance). Today, I get to introduce you to another implementation of PHP, written in PHP. But this one is no toy. This one... This one is fun...

Recki-CT

I'd like to introduce you to The Recki Compiler Toolkit (Recki-CT).

What Is It?

It's a Compiler written in PHP that targets a subset of the PHP language (a less dynamic subset). This means that it does not support things like references or variable-variables. It also does not support global variables (at all, not even super-globals). What's the point of that you ask?

Well, if you're able to write code that's static enough, then we can reason about it. We can analyze it. We can optimize it. And we can statically compile it to machine code.

Yes, that's right. Recki-CT compiles PHP down to machine code.

But it's fundamentally different from other approaches at doing so. HHVM and HippyVM both use Just In Time Compilation to compile PHP. That means that the compilation happens at run-time. Which means that the compilation process must be fast.

Recki-CT on the other hand uses Ahead-of-Time Compilation (or more precisely, lets you cache an intermediary which can be compiled at run-time). This means that more aggressive optimizations can be applied. And it means that more efficient code can be generated. And it means that code produced by Recki-CT can be run along side (inside technically) another engine.

Right now, the only engine that's supported is PHP. However there's nothing stopping porting the JitFu extension to HHVM, which would then enable running compiled code inside of HHVM. And that's what's different about this approach. It isn't all-or-nothing. It's incremental. You can port individual functions to Recki-CT, while the rest of the application still works 100% on the engine that it's currently running on!!!

How Fast Is It?

Well, that's a very difficult question to answer. Based on trivial benchmarks, it's blindingly fast. It can execute a recursive Fibonacci generator in about the same amount of time as C code can (without GCC's optimizations turned on that is). But this is something that HHVM can already do well. Can Recki-CT outperform HHVM?

Let's find out. Using a simple test script, based off of PHP's own bench.php, we can compare the relative performance differences of a number of PHP implementations. The numbers are normalized to the fastest implementation (which becomes 1.0). So a result of 45 means it's 45 times slower than the fastest implementation. And note that parsing (and any compilation that happens prior to calling the function) is not included in the numbers.

The Actual Test Script Used (which is based off of PHP's internal bench.php). It runs each test 5 times, and throws away the slowest two runs. Then averages the fastest three to get the final answer. So this should remove the overhead of JIT compilers, and just focus on the last bits of performance that we can squeeze out.

The results:

php 5.5 Recki-CT hhvm 3.2 hippy-c qb
simple() 139.63357 1.00000 8.30447 7.65693 8.35018
simplecall() 38.99476 FAIL 1.32552 1.00000 FAIL
simpleucall() 54.02041 1.00000 3.52439 1.51072 47.91090
simpleudcall() 52.14534 1.00000 3.75936 1.41614 47.55259
mandel() 21.26249 1.00000 2.03372 2.11208 FAIL
mandel_typed() 23.16553 1.00000 2.11128 2.09212 3.00061
mandel2() 24.43275 1.00000 2.57704 1.87802 FAIL
mandel2_typed() 23.79989 1.00000 2.90105 1.57193 7.11054
ackermann(7) 35.04870 1.00000 2.27557 103.45436 621.72526
ary(50000) 1.39338 FAIL 1.00000 4.47888 FAIL
ary2(50000) 1.26952 FAIL 1.00000 2.28231 FAIL
ary3(2000) 5.96015 FAIL 1.70997 1.00000 FAIL
fibo(30) 39.48440 1.00000 1.60647 16.40883 FAIL
hash1(50000) 1.70014 FAIL 1.00000 3.27314 FAIL
hash2(500) 2.23648 FAIL 1.00000 1.30044 FAIL
heapsort(20000) 3.67800 FAIL 1.00000 4.96699 FAIL
matrix(20) 4.38364 FAIL 1.00000 37.72782 FAIL
nestedloop(12) 29.24924 1.00000 2.91459 3.07568 FAIL
sieve(30) 10.95413 FAIL 1.00000 4.95152 FAIL
strcat(200000) 1.48186 FAIL 2.06003 1.00000 FAIL
jumpapaluza(50, 50) 11.67746 1.09240 1.48192 1.00000 FAIL
bitapaluza1(21) 63.33357 1.00000 21.39655 1.46851 FAIL
bitapaluza2(18) 21.83346 1.00000 6.19715 2.59416 FAIL

Winner, Within Factor Of 2, Within Factor Of 10, > 10 times slower

Note that the Fail indications for Recki-CT are not true failures, but instead compile errors due to using not-implemented features (in this case, arrays).

But these benchmarks aren't real. They show off best-case use-cases. They don't show off how well it'll work for your application. Only testing your application directly can determine that.

How does it work?

Well, there's documentation to answer exactly that question!

Who's behind this project?

I wrote the initial release myself. However, I relied heavily upon (and worked closely with) Joe Watkins. His work on JIT-Fu both was an inspiration and the prime reason for this project existing.

I also would like to thank Igor Wielder and Benjamin Gruenbaum for guidance and pointing me in the right direction on numerous occasions.

I also relied very heavily upon a few other open source projects, without which I wouldn't have been able to do this. I'd like to thank:

Other projects were used, and there are too many individuals to thank each one. Many helped without knowing what they were helping with (in fact, most). So to everyone else, thank you!!! :-D

How can you contribute?

You can always open bugs, and help document! And if you're feeling really adventurous, then you could try submitting some code (due note that all code contributions are subject to signing a CLA). Take on a bug! Take on a new optimization! Add a new compiler back-end! Have fun!

I have more questions!

Check out the Introduction and FAQ. And if you still have one, reach out to me!

Have fun, and let me know what you think of the project!!!