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.