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.