The AOT Advantage

In my previous blog post I briefly mentioned PHP, HipHop, and AOT. For readers coming late to the party, HipHop is a native code compilation system for PHP, created by Facebook. The idea is that compiling down a relatively large subset of PHP (basically everything besides eval) to C++ code and passing it to an optimizing compiler can produce a much more efficient program than interpretation alone or even compiling to bytecode in advance and executing that.

Let's look at this same idea, but in relation to Parrot's intended LLVM backend system.

We can start off with a basic PHP compiler. The compiler doesn't need to be particularly fast since compilation happens once in advance. Sure, we don't want compilation to take forever because that slows down development, but it doesn't have the same kind of speed mandate we would have in an interpreted environment where we compile the script every single time we run it.

Our basic, feature-light compiler compiles the PHP code down to PAST. From there we kick in a series of optimization stages. Again, if we know we're doing ahead-of-time compilation, we can add more optimization stages up front and take a little more time to compile. For a release build of a high-throughput application, maybe we really want to swing for the fences with this one and enable every optimization in the book. Let's hope it's a long, well-written book.

We compile the PAST down to Parrot bytecode, after all the optimizations have run their course. At this point, we hand off the bytecode to the LLVM backend. LLVM converts the Parrot bytecode into LLVM IR, and passes that through it's own impressive suite of optimizations. At the end, LLVM spits out a native executable which is screaming fast.

The converse side is a case where we want to shorten the turnaround time, such as when we are doing direct interpretation, or even making executables for debugging purposes and don't want our developers sitting around for a long time waiting for the thing to compile. We don't want to completely avoid optimizations, because after compilation the developers have huge and expensive test suites to run which can take much much longer.

What we do in this case is compile the code to PAST, maybe run a handful of "good bang for the buck" (GBFTB) optimizations like constant folding, and compile the PAST down to bytecode. We'll avoid the last step and just execute the bytecode directly, since this is a debug build. When we run it, the JIT engine will kick in to do basic runtime compilation of detected hot spots, giving us nice speedups for programs with tight loops. The JIT compiler will likewise use a few of the GTFTB optimizations, but won't go crazy; we're doing this at runtime now and we have a user waiting.

There are some people in the world of scripting languages who view the complete lack of native executable support as a virtue. After all, they say, the nature of these languages is fast turnaround; We can make changes and run them directly without needing to invoke a separate compiler to produce a separate executable. Plus, the immediate availability of human-readable source code furthers the common goals of open source software and knowledge sharing.

Fast turnaround, from script to execution, certainly is a virtue--in development. Once we're ready to cut that release however, things change pretty dramatically. At my job, I write some applications in C#. During development, I keep things in "Debug" mode, and do lots of tests very quickly. When it's time to cut that release I change the VisualStudio configuration to "Release" and then click "Build All". Where I was doing incremental debug builds, now I'm doing a full release build with optimizations turned on and debugging symbols stripped out. I also build a separate installer project, and to test everything I need to install the software first and run it from it's installed location. This is a lot of extra cost, but I don't do it frequently. I go from about a 10 second compile time turnaround to almost 10 minutes worth of compilation and installation work. The net result is a faster, better executable for my end users.

In the case of Facebook, using HipHop to compile PHP down to native machine code improves throughput performance by 30%, which translates into lower server load, lower wait times for users and, at the end of the day, real money. Say what you want to about obfuscation of the source code, 30% is nothing to ignore.

I like to think that the Parrot infrastructure will support any workflow that our end users want. Having speedy interpretation around for people who want that is a very good thing, and we do it already. But, having the ability to employ tiered libraries of optimizations and create native machine binaries for fast execution is a very very good thing as well. This is why I keep pushing for our eventual JIT system to also support AOT as well. LLVM will already handle all the nitty-gritty, so the amount of scaffolding we'll have to provide in Parrot is minimal in comparison.

Compilers Targetting Parrot

I got to thinking today about Parrot and came to an interesting conclusion: Writing our own parsers for various existing languages is nice, but if we could get the language communities involved it would be even better. There's a symbiotic relationship that could form from such an arrangement and I would like to talk about that here for a little bit.

Let's take PHP as an interesting example. The PHP community has been talking about some kind of rewrite of their core engine to support Unicode from the ground-up. I'm not really involved in those discussions, so I don't know what the current state of the discussion is. I couldn't even tell you if work has started on such a rewrite. However, I do know one thing: If the next version of the PHP compiler targeted Parrot as the backend, it would have built-in Unicode support for free.

There are some reasons why PHP people might not like this option, considering PHP's niche in the web server world and Parrot's current issues with performance and memory consumption. But, as I'll describe here, those are relatively small issues.

Pulling an extremely wrong number out of a hat, let's say that it takes 10,000 man-hours to construct a modern, though bare-bones, dynamic language interpreter from the ground-up. You would have some features like GC, but wouldn't have others like JIT. Unicode support but a small or even non-existant library of built-in optimizations. You build a compiler, you build the interpreter runtime, and then you build a language library runtime so the programs you write don't have to reinvent every wheel from scratch. It's a daunting task, but it's very doable and has been done many times before.

Now, let's say you take that same developer pool of 10,000 man-hours and instead build a compiler on top of Parrot instead of writing a new VM from the ground up. You do get a whole bunch of the really tricky features immediately: GC, Exceptions, IO, JIT (to come), Threads (to come), Unicode, Continuations, Closures, a library of Optimizations (to come), and all sorts of other goodies. You also get a nicer environment to write your parser in than bare lex/yacc (though, I think, you could still use lex/yacc if you really wanted). You get some libraries already, though you would likely need to write wrappers at least to get things into the proper semantics of your language. You really do get a hell of a lot and you could easily have a working compiler, at least the basics of one, up and running within a few weeks.

Let's even be conservative and say that your team can't build the compiler front-end in less than 1,000 man-hours on Parrot. Even then, you still have 9,000 man-hours left. You could spend some of that making a gigantic runtime library, but I like to think you could devote some of that effort back to Parrot too. If you spent even 5,000 hours making Parrot faster, or adding new features, or whatever you need, you'll still be spending less effort overall and getting a comparable result, if not a better one.

Keep in mind, on Parrot, you're going to get all the features that other people add, in addition to the ones you added yourself. Parrot really is a symbiosis: You hack Parrot to add what you need, and in turn Parrot gives you all sorts of other things for free.

Parrot has plenty of stuff around to get you started, even if it's not perfect right now. Remember that Parrot is extremely actively developed. You can do your development now, build your compiler and get your language ready and grow your regression test suite. When you decide that you need things improved, you can make targetted improvements incrementally. If you want a better GC, for instance, you can go in and just add that part. But, you have the benefit of knowing that Parrot already has one and your test suite team doesn't have to wait for your GC team to finish writing their first GC. That's good, because those damned GCs can take a while.

My point, in a nutshell, is this: Parrot has some really cool features, but the coolest is that it provides a standard base level, a standard toolbox, that you and your compiler team can take and use immediately if you want it. You can get started right now with the kinds of high-powered features and tools that it would take you years to get right by yourselves. Yes there are improvements needed and some features yet to be desired, but adding them to Parrot represents smaller, more incremental improvements than trying to write an entire interpreter yourself.

Parrot is adding some really cool features this year too. I fully expect by the 3.0 release we will these new things:

1. A new, fully-featured robust threading system
2. A pluggable optimization library, with optimizations able to be written (likely with some bootstrapping) in the high-level language of your choice
3. A new GC with radically improved performance characteristics
4. An extremely powerful instrumentation and analysis framework (again, with tools able to be written in the language of your choice, possibly with some bootstrapping)
5. A flexible native function call interface for interacting with existing libraries

If you can wait a little later, I fully expect by 3.6 or 3.9 that we will be rolling out a powerful LLVM-based native code compilation core which will support JIT and (I hope!) AOT. You don't have to look much further than Facebook's HipHop project to see that compilation of dynamic languages down to native executables will be a big benefit, especially if we can aggressively optimize all the way down. I'll talk about that particular issue in a later post.

Parrot does have some problems now, like performance. I can certainly understand the criticism on that point. However, for a fraction of the effort it will take you to write a new interpreter or virtual machine from the ground up you can target Parrot instead, get a bunch of free features, and maybe spend some of your free time helping us add the optimizations and improvements that you need. I really and truly believe that it's a win-win proposition for everybody involved.

ParrotTheory: Microprocessor Design

Long before I was involved in helping with the Parrot virtual machine, I was in school learning about and even designing actual microprocessor hardware. In my posts I nonchalantly talk about things like caches, pipelines, and hazards. Now I'm going to explain a little bit about what these things are and why they matter to Parrot (and all code, for that matter).

A typical production-grade microcontroller, not a toy or a colorful explanatory diagram in a book, is broken up into several stages. Each stage represents a portion of work or computation that can be done in a single clock cycle. I'll call these "clock cycles" for simplicity, but it's worth mentioning that there is not necessarily a strict relationship between the clock frequency and the instruction frequency. It's also worth mentioning here that the smaller your cycles are, the faster your clock can operate. Your clock's frequency is limited by the length of time it takes to execute your longest stage.

If we look at a simple and classic design, like the original MIPS microcontroller, it is broken up into 5 distinct stages: Instruction Fetch (IF), Instruction Decode (ID), Register Lookup (REG), Execute (EX) and Write Back (WB). In the IF stage, the instruction is retrieved from memory. ID breaks that instruction up to a series of individual components like control sequences, register names, etc. REG retrieves the values of the operand registers based on the information in the instruction word from the register file (an array of register values). EX performs the desired operation and produces a result. WB takes that result and stores it back into the register file. Wash, rinse, repeat.

A given instruction is only being executed in one stage at a time, so in this example it takes 5 clock cycles for the instruction to execute fully, and 1 instruction is executed every 5 cycles. This may sound redundant, but I'll explain later that it might not be. This would be a bit of a waste because at any given time 4 of the 5 stages can be empty and unused. To prevent this, microprocessors use a technique called pipelining, where we stagger execution to keep all the stages full. At any given time, each stage can be processing a different instruction. In this case, it would take 5 cycles to complete 1 instruction, but we can now complete 1 instruction every cycle. This is a 5x speedup!

[Note: some readers will realize that I'm talking about a multicycle processor here, not the more simple single cycle design. This is on purpose.]

The original MIPS design is a very simple example, modern processors from SPARC, AMD, or Intel might have more then 20 stages.

We run into problems called pipeline hazards if we do things like try to read a value from a register that is being calculated concurrently by another instruction in the processor. In this case, the processor bubbles, or delays for a few cycles until all the necessary data is ready. A smart optimizing compiler can automatically rearrange instructions to help reduce bubbling. To see how, take a look at this sequence:

a = b + c
d = a + 2
e = f + g

In this sequence, the value a is used immediately after it is calculated. This will cause the processor to bubble for a few cycles until the value of a is ready. Remember, it takes 5 cycles to compute a single instruction, so the first instruction must complete fully before the second instruction can begin. This means that for 4 cycles, new instructions cannot enter the pipeline, being instead replaced with empty "bubbles". By simply reordering things a little bit, we can speed things up:

a = b + c
e = f + g
d = a + 2

Same exact code, but now executes a little bit faster. This is because the instruction "e = f + g" is not dependent on the value of a, so it can enter the pipeline before the value of a is calculated. Now, we're down from a total of 7 cycles to 6 to perform the exact same work

[Note: I'm definitely simplifying. Don't shoot me!]

The EX stage, which is the actual workhorse of the processor, is relatively complicated in itself. It consists of two separate components, the arithmetic-logic unit (ALU) and the Memory Unit (MEM). Instead of being a series of stages in a row, the ALU is a set of parallel execution cores. Each core performs a different operation, so one may add/subtract, one may multiply, one may bitshift, etc. Data comes in and is copied to every core, every operation is performed on it, and a multiplexer is used at the end to select which value we want to keep. The MEM component can write or read data in memory at a given address. It's the MEM component that is usually one of the slowest parts of the processor, and serves as a huge bottleneck for the rest of the hardware. This is because MEM needs to interface with the cache and the RAM, which both may be running at a significantly slower clock frequency.

The ALU can be remarkably fast, because there are often very straight-forward tradeoffs to be made between numbers of transistors and speed. When you hear statistics about modern CPUs having billions of transistors, you'll know that they're trading more transistors for improved performance. I can talk about this more later if people are interested.

What we can do to make things even faster is to start doubling up on parts of the pipeline. We can be fetching and decoding instructions in large batches and passing them to multiple parallel EX cores. So long as we have the necessary hardware to detect hazards, we can be essentially executing multiple instructions together at each stage, with multiple stages in process. Some modern Intel CPUs, for instance, may contain two ALUs and two specialized MEM units (one to read and one to write). This means it can execute two mathematical instructions and two memory instructions at the same time. A smart compiler will know to order instructions like this to maximize parallelism. This design which uses parallel pipelines in a single processor core is called superscalar. When a compiler rearranges instructions to take advantage of parallelism or even to avoid hazards, it is called instruction pairing.

Consider a modern processor executing at 2GHz with 20 pipeline stages and can complete 1 instruction per cycle. That's 40 billion instructions per second that can be executed if everything is running at it's maximum efficiency. Not too bad. However, keeping things maximally efficient is a difficult task. Reducing hazards is a great thing, but the processor can only run fast if it can keep it's pipeline full, and can only keep the pipeline full if it knows what instructions to execute ahead of time. When we look at a conditional in C, we may not know what instructions to execute next until we've already calculated the value of the conditional:

if(a == 0) {
a = 1
} else {
a = 2
}

If the comparison a == 0 is in the pipeline now, we don't know which instruction to load next: a = 1, or a = 2. Without knowing we would have to wait 20 cycles until the comparison completed before we could load the next instruction into the pipeline. When you consider the case of more stages and more parallel pipelines, if we have to stall and wait for a result to be computed we can lose a lot of processor time. You can start to see huge performance decreases from these kinds of situations. To help resolve these situations we have branch predictors.

Branch predictors are specialized pieces of hardware that attempt to predict where control flow will be going, and use that information to speculatively load the pipeline with instructions. If the branch predictor is correct, things chug along like normal and everything is fast and wonderful. If the branch predictor is incorrect we need to flush the incorrect instructions out of the pipeline and start fetching the correct instructions. This can be expensive for a number of reasons: We need to completely refill the pipeline, which means we need to fetch more instructions from slow-moving memory.

I haven't made much mention of it so far, but memory caching is a huge deal. Memory runs at a much slower speed then the processor does. To keep the processor moving quickly we bring small blocks of memory into a small bit of fast-access storage inside the processor called the cache. The cache is small but very fast, and information in the processor cache can be accessed very quickly. If we try to access memory that isn't in the cache, we need to stop everything and load that data from memory into the cache before we can continue. This is called a cache miss and can be very expensive. If we look for memory that is not in memory either but is located on disk, we have what's called a page fault, which is more expensive still, but discussing tha is well beyond the scope of this post.

If the branch predictor is wrong, we need to flush the pipeline and maybe flush the cache too. This can become prohibitively expensive, with slowdowns around 100x or more. This is why sometimes your 3GHz quad-core processor grinds along like an old 486: poorly written code is causing all sorts of hazards and misses, and drives efficiency down to the floor. It's not the processor that's slow, it's the processor needing to wait for the pipeline to refill, or the cache to refill, or even the virtual memory manager to load the correct page from disk. It's the waiting that's a huge performance killer.

In a lot of cases, doing more can actually be better for performance. Consider this code, for instance:

if(a != NULL) a = NULL;

This is very straight forward, and only does the work of setting a to NULL if it isn't already. What you don't see is that this is probably a net performance loss: the branch gives us a 50% chance of missing in the branch predictor, and the comparison instruction is already moving the value of a into the cache and then it's an extra instruction to compare before we set the value. In this case, it is likely much faster to just write

a = NULL;

But then again, that's not the whole story. It's not just a matter of keeping the pipeline full, it's also a matter of how much effort it takes to read from and write to the cache. If we need to write through cache to main memory, we'll waste a lot more time then we would have if we did the conditional. There are always tradeoffs to make, some of them painful.

In other cases, it's better to write more code to be faster. Here's an example:

int i;
void *a[8];
for(i = 0; i < 8; i++) a[i] = NULL;

We could make this faster by telling C that i can avoid memory entirely by defining it as "register int i", but that's a small optimization. The loop is going to cause at least one branch predictor failure, either entering the loop (and not knowing the first time to jump back to the top) or exiting the loop (and not knowing when not to jump back to the top). By unrolling the loop we can make things much faster:

a[0] = NULL;
a[1] = NULL;
a[2] = NULL;
a[3] = NULL;
a[4] = NULL;
a[5] = NULL;
a[6] = NULL;
a[7] = NULL;

I don't want to talk about all potential optimizations here, that would be a huge list. But by being conscious of the types of factors involved in performance I hope that other developers are able to spot other situations where code may be far less efficient then it could be.

Optimizing Parrot

Let's all face reality here: All the recent refactors of Parrot, including the ongoing PCC refactors, have either a neutral effect or a negative effect on Parrot performance. dukeleto showed me an eye-opening comparison between several versions of Parrot and the most recent rev of pcc_reapply that showed a stunning 400% execution time increase for some benchmarks between the 0.9.0 release and the current branch revision. That's terrible.

The Context refactors added about a 200% execution time increase. The PCC refactors are currently adding about another 200%. The fact that these two systems overlap so closely is certainly only exacerbating the problems. So why are these two refactors responsible for so much slowdown? Let's look at each in detail.

The Context refactor converted the Parrot_Context structure, which was manually memory-managed using bit twiddling reference counts, into a garbage Collectible PMC type. Had the changes stopped there, I have the strong belief that this would have been a neutral change in terms of performance. If anything I would suspect that this change would have been a small win overall. No matter how lousy and inefficient our Garbage Collector is, I have to believe that the tight loops and spacial locality of keeping PMCs together would be a good thing. Also things like the memory allocator in the collector are pretty efficient (although could definitely be improved). However, the refactors did not stop there. bacek also went through and properly encapsulated the Context PMC type so that there were fewer direct accesses of it's internal members. All accesses happen now through API calls, which are significantly more expensive. Plus, every field access adds an additional pointer dereference now too. Together I don't really know how these things could have added a 200% performance penalty, but it's pretty well documented that they did.

The PCC refactor is adding in a new abstraction step in the calling process. This makes the code prettier, along with much more maintainable. The cost is in making some of the operations a lot less efficient. Some of this is the fault of the new CallSignature PMC, which naively integrates several array and hash PMCs, inheriting from the oddly-named Capture PMC in the process. All strings, integers, and numbers are autoboxed into PMCs during the creation of the signature, and all return values get a CPointer PMC to hold the pointer. This is not to mention that several of these values are only accessible through named lookups, and you start to see a major performance problem. We're creating a shittonne of new PMCs for every call, and then using relatively expensive VTABLE accesses to recursively access the data in them.

chromatic has been doing some great work in the past few days rewriting the naive CallSignature implementation into a much more efficient form. Many of the operations can be more specialized for the task at hand, and the number of created PMCs can be reduced dramatically. bacek has also been doing some good work in this area, mostly small bits and pieces around as he finds them. So the situation isn't hopeless, but we are going to have to tighten several things up if we want Parrot to be as screaming fast as it was in 0.9.0 (if not faster).

Now that we have a very well-designed system, there are plenty of places where we will probably want to break encapsulation for a performance win. A few places where we will want to write some ugly code instead of the current prettier code, also for a win. We'll just make sure to mark these places with lots of documentation.

I've been focusing my attentions on fixing bugs. This weekend chromatic and bacek have been looking into them also, and together we're down to 1 remaining failure at the time that I write this. The last few tests were all very tricky, but this last one is turning out to be the worst of the bunch. I think we'll be able to beat it this weekend, however. After that, we're focusing on optimization until we're ready to merge the branch, probably soon after the 1.7 release.

So that's where things stand in terms of performance. Parrot has a lot of ground to recover since 0.9.0, but I am convinced that there are plenty of opportunities to do just that. Some of it will be algorithmic improvements, some will be small intelligent tweaks to individual functions and datastructures, and some will be real low-level bit-twiddly nonsense. However it happens, we really need to make Parrot faster, and I have very high confidence that we will be able to do just that.