The Parrot-Data-Structures project intends to provide a library of specialized PMC data types for use with the Parrot VM. These types will each be optimized in some way to provide better performance and/or more efficient use of memory than the default array types provided by the core VM for certain usage patterns. These types will be useful to people who need high performance and are willing to exchange some flexibility and functionality to achieve it.
Each type will have a particular optimization focus that will drive it's development. End users can select from among several variants to find one with a focus that meets the needs of the application.
Because there are multiple ways to implement each of the target data structure types, and because different implementations will have different strengths and weaknesses, PDS may provide several implementations of individual types with plenty of tests and benchmarks to show efficacy and comparative merit. As types are benchmarked and tested to be both reliable and have suitably high performance, they will be made into regular, non-experimental versions or they will replace existing non-experimental types.
Here is a general list of data types. Initially we will aim to produce versions of these types that store PMC pointers only. Eventually we will also develop other variants designed to hold other primitive types (INTVAL, STRING, FLOATVAL) as well.
- Stack
-
Stacks are First-In-Last-Out types with an optimization focus on push/pop throughput performance. This type will not provide unshift/shift access and may have sub-optimal performance for other access methods. Stacks absolutely do not have shift/unshift interfaces, and likely will not allow indexed access either.
Currently there are two primary stack types. FixedPMCStack uses fixed-width preallocated storage. Accesses are very fast but the storage must be preallocated. ResizablePMCStack uses dynamically-expanding storage which can be slower but is more flexible.
In addition, there are several other experimental varieties that explore alternate implementation strategies.
- Queue
-
Queues are First-In-First-Out types with an optimization focus on push/shift throughput performance. Queues will not provide pop/shift interfaces and likely will not allow indexed access either.
There are two primary Queue types. FixedPMCQueue uses fixed-width preallocated storage. Accesses are fast at the expense of a lack of flexibility. ResizablePMCQueue expands dynamically but accesses are slower.
Other queue types are in development, including types that use alternate implementations and types that provide additional features (thread safety, for one).
- Fixed-Size Array
-
Parrot provides several fixed-sized array types, but there is a general movement in that project to unify down to a single dynamically-resizable array type for all needs. This move helps to reduce code bloat and maintenance problems, but removes a key type for high-performance access.
If Parrot removes it's fixed-size types they will likely be moved or copied to PDS.
Fixed-size arrays are optimized for fast storage and fast indexed access, and will not provide other interface mechanisms such as push/pop/shift/unshift.
- Dynamically-Resizable Array
-
If Parrot removes the majority of it's array types, some of its dynamically-expandable array types will move or be copied to PDS. Resizable array types will put more of a focus on access performance and economy of memory storage space than a general, type-agnostic array will.
- Sparse Array
-
Sparse arrays are array-like types with a focus on extremely efficient memory use for sparse data sets.
This is only a partial list of possible types. Other data structures which can be subjected to a tight optimization focus will be candidates for addition to PDS.
parrot setup.pir build
parrot setup.pir test
parrot setup.pir installContact the Parrot-Data-Structures team at