Lean and Mean Parrot.

I got a comment from old-time Parrot contributor Melvin the other day in response to my criticisms of the PDD23 Exceptions system. He had a few things to say that really echo points that I've been trying to make in the past few months. I would like to reprint his comment here, in full (with some minor copyedits), and address it directly.

If IMCC needs to look into the op lib during lexical analysis, there is probably a design flaw. The opcode should probably only be checked during the parse / semantic check phase. If you want to tweak that much more performance out of IMCC you'd probably be better autogenerating the short op-list into imcc.l before calling lex so the token list is built directly into the scanner. As to your die vs. exit, I agree. This is where there is too much Perl influence in the VM. Things like 'die' semantics are better implemented in high level. Give the VM a simple opcode for termination, let all other things (printing messages, etc.) be implemented on top of the core op. I was arguing this in 2001/2002. If I had it my way, the core ops would be lean, and all the PMC grunge would have been implemented on top of those lean ops, not in the wacky .pmc/VTABLE mechanism that exists now. 99% of the Parrot lib would be written in a single, consistent HLL, and the JIT would be manageable. Right now, even as an original Parrot developer, I cannot wade in. Parrot requires a mix of Perl, PIR, C and custom build macros. PMCs are not Objects and Objects are not PMCs. There are still multiple cores for the fun of it. etc. etc. If Parrot is to ever really be done, seriously, someone needs to take a scalpel to about 50% of the "sacred" parts of the codebase and cut the amount of busy work and maintenance that has to be done, and remove some of the "multiple options" for accomplishing the same thing. Examples of projects that succeeded much faster than us are Mono. They built a canonical compiler (C#) and then proceeded in implementing the platform using the C# compiler. I was arguing that this would have been Cola at the time, and was my intent when I wrote PIR and the simple Cola compiler. But 8 years later, there is no JIT and Parrot is looking at using projects that started well after itself. I cringe when I look at all the hand-written .pir files in the distro. This was not the intent of PIR. Anyway, good luck. Don't take my comments the wrong way, hopefully they'll spark some debate. I'll check in in 2012. :)

I don't know how actively Melvin has been following IRC discussion, the mailing list, or this blog. I assume that he hasn't been following too closely, and we really can't expect a person to be following discussion for a project he's not really involved in actively. One of the big points we've been pushing for in recent months is Lorito, the lean set of low-level ops that we are going to use to rewrite large swaths of the codebase. In fact, seeing Melvin discuss this very idea is encouraging and validating: If other people come to the same conclusions that we come to internally, that means they are at least common ideas and maybe even good ones.

Lorito gives us the opportunity to move the abstraction layer down, and reduce context switches that occur by moving from one side of the line to the other. You don't have to look far in the PCC system, for instance, to see the machinations we have to go through to manage method calls from C. There are complicated structures of function pointers to access parameters from variadic argument lists. There are all sorts of complicated serialization paths to marshal arguments into the CallContext PMC, make the call, and then marshal the arguments back out of it again.

If we didn't have to worry about making calls from C, or if we at least didn't have to worry about making them regularly, we could avoid all this nonsense and delete several hundred lines of code, and the code we had left would be faster.

Another fact that comes up regularly is that the VTABLE interface is lousy. We've optimized for VTABLE access even though it's an extremely limited interface. There are simultaneously too many functions in the list, too few to support certain PMC types, and not nearly enough flexibility to support the kinds of interoperation mechanisms that we need. Ask this: How many mathematics-related VTABLEs exist? Now ask how many of them are even remotely useful outside the handful of numerical PMC types? Why does every single PMC type need to carry around pointers to all these functions that never get used? Why don't VTABLEs support proper MMD? Why don't all VTABLEs do any kind of MMD, even if it's wrong? Why do we have so much trouble inheriting VTABLEs between core PMC types and user-defined objects?

If we re-write the whole PMC system in Lorito, we can improve VTABLE dispatch semantics, maybe unify VTABLEs and METHODs, and expand the list of VTABLEs to hold any operations that we need. If we make the distinction that a VTABLE is like a method but only has a fixed number of positional arguments and can only be called from Lorito code, we could use a separate streamlined dispatch path that would be far faster than VTABLE overrides in PIR are now, only marginally slower than C-level VTABLES are, with the flexibility to plug into Parrot's MMD system for proper dispatch, and significantly more powerful and flexible than what we currently have. Plus, using hashes and named lookups, types could define a Sub of any arbitrary name to be a VTABLE, look up by any name we want to use with any arity we need for that operation, and we would only need one "VTABLE not found" handler to fall back to if a suitable one hasn't been found.

Runcores that don't build on every platform and are not well-tested by default should disappear. Sure, there is some benefit to having them as an academic exercise. Sure, it's cool to say we have an obscure and complicated dispatch mechanism with fun properties. But the reality is this: We're not using them. When we create a fakecutable binary for HLL projects like Rakudo, it generally hard-codes in the name of the runcore to use. So if our primary users can't select their own runcore, and if the primary way to use Parrot should be through HLLs (because I'll be damned if we want people in general to be writing PIR directly forever), then having multiple runcores is a huge waste.

Slow core? It does do bounds checking, but those bounds checks have never been seen to fail in my tenure as a Parrot coder. Drop it.

Computed-Goto and Predereferenced-Computed-Goto cores? Not all compilers even support these, and they require much more than their fair share of support code to operate at all.

Switch core? It's available everywhere and it's pretty speedy, but performance decreases pretty dramatically when used with dynops.

There has been some effort to make runcores pluggable using libraries, so a migration effort to move some of the uncommon ones out of core would be beneficial. I don't think we need them in core, but if other people would like to maintain them elsewhere, I won't complain about it at all.

Let's get one thing straight: including unused or rarely-used code in your program is not free. There are costs associated with having that code in memory. There are costs associated with the branches and decisions that choose to avoid it. There are costs associated in loading and dynamically linking exported symbols. There are costs associated with compiling all this code These things may not be super-expensive, but they are not free. And keeping code that has no practical benefit for developers or end users without a good reason to have it is not good practice.

Unnecessary opcodes need to disappear as well. We have well over 1300 opcodes now, probably closer to 1400 at this point. All of these add overhead in terms of memory footprint and lookup effort. It's a huge waste, and I suspect that if we did some actual profiling work we would find only about 200 of them were used with any regularity and about half would be almost completely unused except for one or two calls in obscure tests in the Parrot repo. If PGE and NQP don't use particular ops, and if there is no compelling need to keep them for particular HLLs, or if those HLLs can reasonably turn them into dynops, they should be removed.

Adding more ops is not a case of "it's a small added convenience with no downside". There are very real downsides.

Having too many core PMCs is a problem too. Parrot currently has 86 core PMC types by my count. I think we can drop this number to 60 without having to make any cuts that are too painful. If we wanted to be aggressive I think we could go even lower, but we do hit a point where we need to start weighing proportionally-smaller performance gains against the lost utility of removing PMC types that we're dependent on. In any case, I think we can definitely stand to move the following PMC types into dynpmc libraries or even delete them entirely: AddrRegistry, BigInt, BigNum, Boolean, Capture, CPointer, File, 9 of the array types, Key (to be replaced with an array type), Opcode, OpLib, OrderedHash, Pointer, Scalar, and Timer. This would bring us down to 63 PMC types, and several of these that I've listed are already either deprecated or are listed as experimental.

We as a community have definitely been moving in this direction. Allison especially has been helping to spread a "less is more" philosophy to the design of Parrot and I do appreciate that effort on her part. Making a switch over to Lorito, and then using Lorito to implement Ops, PMCs, and a few other core systems would be a major benefit. chromatic has been a major pusher for the Lorito effort as well, and having somebody of his stature behind the effort lends major credence to it. The effort to slim down the number of ops and PMCs doesn't have as much momentum but there is real evidence that we could be moving in that direction in the near future. I welcome all these changes and hope to see them come to fruition.

Parrot-Data-Structures Benchmarks

When I first conceived of the Parrot-Data-Structures project, I envisioned a place where we could develop performance-optimized PMC types. A part of proving that we've improved performance is to provide benchmarks. So, this morning I went through and wrote up some naive benchmarks to compare several of my new PMC types against the venerable ResizablePMCArray. I didn't compare against the FixedPMCArray because the latter doesn't support push/pop/shift operations and I wouldn't be able to make direct algorithmic comparisons.

I've only put together one benchmark so far for stacks: We push 1,000,000 items onto the stack and them pop them all back off again in tight loops. This forces the stack to resize up to 1,000,000 items worth of storage. The times were small and I could have upped it to ten million items or more, but then we start to see more effects from caching pages to disk and lose insight into the application we are testing.

(FixedPMCStack) Time to push       1000000: 0.0456011295318604
(FixedPMCStack) Time to pop        1000000: 0.0357608795166016
(FixedPMCStack) Time to total      1000000: 0.0813620090484619

(ResizablePMCStack) Time to push   1000000: 0.0498058795928955
(ResizablePMCStack) Time to pop    1000000: 0.0467569828033447
(ResizablePMCStack) Time to total  1000000: 0.0965628623962402

(ResizablePMCStack2) Time to push  1000000: 0.0470800399780273
(ResizablePMCStack2) Time to pop   1000000: 0.0364069938659668
(ResizablePMCStack2) Time to total 1000000: 0.0834870338439941

(ResizablePMCArray) Time to push   1000000: 0.0531971454620361
(ResizablePMCArray) Time to pop    1000000: 0.0347628593444824
(ResizablePMCArray) Time to total  1000000: 0.0879600048065186

I've shown three of my types as they compare to Parrot's ResizablePMCArray type. FixedPMCStack is fixed-size, so it's allocated up-front and does not need to be resized on each push. ResizablePMCStack is a linked-list of mini-array chunks. Each chunk holds 16 pointers, so we can push 16 objects before a new allocation. ResizablePMCStack2 is an alternate stack implementation that I put together today. It uses a flat memory buffer but does geometric reallocations. Starting at 16 objects, every time we run out of space we allocate twice as much (16, 32, 64, etc). Finally is the ResizablePMCArray, which resizes the buffer on each push. This start size and the growth factor can be tuned, though I haven't made any efforts to do that.

FixedPMCStack obviously wins the competion since it only needs to malloc once and never needs to reallocate or free the memory. At this sample size the benefits are not huge over the other types. ResizablePMCArray2 eeks out a win over ResizablePMCArray for this sample size. However, at smaller samples such as 10,000 objects to push, ResizablePMCArray wins instead. I suspect we could tune the size of allocated chunks in ResizablePMCStack or the starting allocations and grow factors of ResizablePMCStack2 to alter these results and the threshold where the first type becomes less efficient than the latter type. As the data set gets larger, the geometric growth of RPS2 takes over and severely decreases the number of allocations that need to be made, while for the basic RPS type, the size and frequency of allocations is constant.

ResizablePMCArray performs well enough in these benchmarks. It does more allocations than any of my types, but uses a relatively efficient flat memory buffer to hold data, so it's not blown out of the runnings entirely.

Now for the FIFO Queue types. For these types, I used 100,000 items in a similar loop (push 100,000 items, pop them all). I didn't use 1,000,000 like I did in the stack tests above for a reason I will discuss below.

(FixedPMCQueue) Time to push      100000: 0.00739598274230957
(FixedPMCQueue) Time to shift     100000: 0.00774002075195312
(FixedPMCQueue) Time to total     100000: 0.0151360034942627

(ResizablePMCQueue) Time to push  100000: 0.0121519565582275
(ResizablePMCQueue) Time to shift 100000: 0.00611591339111328
(ResizablePMCQueue) Time to total 100000: 0.0182678699493408

(ResizablePMCArray) Time to push  100000: 0.00558805465698242
(ResizablePMCArray) Time to shift 100000: 5.47745704650879
(ResizablePMCArray) Time to total 100000: 5.48304510116577

FixedPMCQueue uses a pre-allocated memory buffer, which is a big saver and makes it the obvious winner in the category. However, since it's setup as a ring buffer each push/pop operation requires a few extra pointer checks that the other types don't need to go through. This is why the ResizablePMCArray wins among all types in push performance.

Shift performance is a different issue entirely. FixedPMCQueue again isn't the winner here but it is close. ResizablePMCQueue does just a little bit better here using it's efficient linked-list implementation. Even though each linked-list node needs to be free()'d, the implementation of free() in libc is pretty lightweight compared to the cost for malloc(). In fact, all things considered, it looks from the numbers above that free() is about twice as fast as malloc(), all other things being equal.

Shift is where the ResizablePMCArray type loses it's composure completely. FixedPMCQueue and ResizablePMCQueue both took about 1.5 one-hundredths of a second to complete the benchmark. ResizablePMCArray took about 360 times as much to perform the same operation. And the reason is that it took almost 5.5 seconds just to do 100,000 shift operations. And that's not even the worst of it. RPA.shift() is O(n²) complexity. When I tried to bump this benchmark up to one million items, the benchmark ran for over 10 minutes before I had to kill it with no end in sight. Both my queue types are time-linear, and bumping up to one million items took only 10 times longer for them. Why is ResizablePMCArray O(n²)? Because each shift operation requires a memmove, which loops over each item in the array and moves it to a new buffer. This is terrible and one of the reasons why I started the parrot-data-structures project in the first place.

I plan on adding a few more benchmarks. For instance, rapid-fire push/pop benchmarks that don't cause resizes might be interesting to isolate the per-primative operation cost without considering memory allocation costs. Your average program doesn't need to push one million items onto a stack or queue, of course. And with these benchmarks I'll be able to focus some optimization effort on these types to make them better.

The overall lesson to be learned from this post is this: For stack-like operations the ResizablePMCArray is a decent—though not perfect—tool. For queue-like operations on the other hand, ResizablePMCArray is lousy and should be avoided. At least, it should be avoided until we do some optimization effort to make it better.

Introducing Parrot-Data-Structures

This week at #parrotsketch the question was raised as to why we had differentiated array-like PMC types at all. Why do we have separate ResizablePMCArrays from ResizableStringArrays and the like? For symmetry, why don't we also have separate PMCHash and IntegerHash types?

After the Array PMC was removed last week, plobsing mentioned that RPA had a complexity of O(n²) for shift/unshift operations while the Array PMC had a much better O(n) complexity for those same operations. I had a few ideas about it, but looking through the code I didn't see any easy ways to really fix the performance problems in RPA. At least, I couldn't think of a way to fix the performance of shift/unshift that wouldn't hurt some other metric. There's a certain trade-off in terms of performance we make when a data type becomes more flexible. Maybe it's good enough to just advertise the fact that certain operations, though available, are known to be sub-optimal.

These two points combined to inspire me to create a new project: Parrot-Data-Structures. Parrot-Data-Structures (PDS for short) will contain a collection of specialized datatypes that are less flexible than the standard ResizablePMCArray is, but which are designed to have particular beneficial properties in return. These beneficial properties may be optimized hot-paths for specific operations or high memory-efficiency for certain types of data sets.

I asked whether these types of PMCs belonged in core or whether I should create a new project. The consensus was that I should start a new project and if the structures were great enough we could consider merging them into trunk.

At the time of this writing I have prototyped three new PMC types:

1. ResizablePMCStack. This type is a dynamically-sizable stack type that is optimized for push/pop performance. I've implemented the prototype as a linked list of mini-arrays, so we don't need to allocate storage on every push, and don't need to deallocate it on every pop. Because of it's architecture, RPS doesn't offer indexed element access, but it does provide a method to convert it to a normal ResizablePMCArray if indexed access is needed.
2. FixedPMCStack: This is a stack PMC type that uses fixed-size preallocated storage. Push and pop are going to be faster than even RPS, and because it uses a flat memory buffer indexed element access should be possible at good speeds (though this is not currently implemented).
   
3. FixedPMCQueue: This is a standard fixed-size first-in-first-out queue structure. It is optimized for push/shift performance. I've implemented the prototype as a ring buffer, so we can avoid costly memcpy and memmove operations while allowing the storage to slowly snake it's way around in memory. Because it's always moving around in memory, indexed element access is not possible at a reasonable speed, so I probably won't implement it. I have provided a to_array() method to convert it to a FixedPMCArray if random access is necessary.
   

Next on my immediate TODO list are:

1. ResizablePMCQueue: I'm not sure how I will implement this one, it certainly can't be a ring buffer like the FPQ type is. It will be optimized for push/shift access like FPQ is, but might take a small hit when reallocations are necessary.
   
2. SparsePMCArray: The sparse array works best on datasets where most elements in the set are some default value. Instead of allocating storage for all items, we only allocate storage for the interesting ones. This type is optimized for low memory use in sparse data sets. It's worth mentioning that the Array PMC, which has recently been deleted from trunk, was a sparse array type. However, it was a sufficiently bad implementation that I think it's good to just start over and try again.
   

Less concretely, I've also considered the benefits of providing some additional types, though I'm not sure how far I want to stretch the scope of this project:

1. PMCHeap: This would be a binary-tree type of structure internally, keeping PMCs sorted according to a provided sort routine. I'm not sure whether I would want this to be more like a "max heap" or a binary search tree.
   
2. ThreadSafePMCQueue: This would be a message queue variant that could be used safely across threads.
3. PriorityPMCQueue: This is a queue type where each element has an assigned priority. Pulling an item off the queue grabs the highest-priority items first. Items of the same priority are retrieved in FIFO order.
   
4. PMCGapBuffer: This type is optimized for fast insertions/deletions around a point of focus. Think about a text editor where most text changes happen right near the cursor. In the gap buffer, we would first set a "cursor point", and then we would be able to push/pop from the left side of that cursor, and shift/unshift from the right side of that cursor.

In addition to these potential types I mentioned, there are any number of searchable/sortable data structures we could implement to facilitate fast searching in a collection of elements that aren't keyed. Things like skip lists, jump lists, or Splay trees each have interesting properties that would allow searching for items in a collection in O(log n) time. If people express an interest to me about these kinds of types I might look into writing out prototypes.

These prototypes are all designed for PMC storage currently, though I plan to add similar types for INTVAL, STRING, and FLOATVAL too. This is a lot of PMC types, to be sure, but the specialization could be a huge benefit for applications that need a particular type to perform better in some metric than the Parrot core types can handle. I haven't looked into building or testing these types quite yet, but I have an idea that the build will produce several library files with different combinations of types in them. This way projects can only load the few types they need.

An ultimate goal of this project is to help out Parrot's core. There are two ways this could happen: First, the Parrot team could decide that we don't want a ton of performance-specialized or type-specialized array types in Core, in which case add-on projects like this will be necessary to provide that functionality with good performance. Second, the Parrot team might decide that these types have value and they could be added to Core later.

I actually like the second development path in general: It's a way we can prototype cool new features. Also in the second case, I don't need to worry about the scope of this project expanding too far, because it could always be considered an incubator for interesting, new PMC implementations.

If anybody reading this blog is interested in participating, I've got commit bits aplenty to hand out. If you want to participate in the fun, please let me know.

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.