kurahaupo edited this page Sep 14, 2010 · 3 revisions
Clone this wiki locally

Welcome to the parrot-data-structures wiki!


  • Threadsafety
  • Specialize to handle common cases (much) faster


Arrays are first on our hit-list because they’re most subject to changing “shape”, in ways that reflect various idioms:

  • Fixed shape
    • Vectors and Matrices
    • Map and Sort output lists
  • Ordered-in-ordered-out
    • Strict Queue
    • Stack
  • Random-in-ordered-out
    • Indexed
    • Partial Queue
  • Ordered-in-random-out

If you have an array that changes in some other way, then either this list needs updating, or you probably want some other datatype.

There is about arrays on Trac


Most of the array types listed above interact with only one process thread at a time, however queues (both strict and partial) can be used to feed information ’’between’’ threads, and therefore must be able to work correctly with concurrent updates.

All implementations should be “thread safe” in the sense of not causing corruption when multiple threads interact, however it is acceptable for a given implementation to throw something like “not owned by this thread”. (For queues there could be separate owners for the “head” and “tail”.)

In the general case any datatype can be manipulated by more than one thread. But such cases should be handled by a more general-purpose types than the specialised versions we’re considering here.