DistributedDeque

Usage

use DistributedDeque;

Summary

A parallel-safe scalable distributed deque. A deque is a double-ended queue that supports insertion and removal from both ends of the queue, effectively supporting both FIFO, LIFO, and a Total ordering, where the order in which you add them will be the exact order you remove them in; for emphasis, a Deque can be used as a Queue, a Stack, and a List respectively.

Note

This package module is new in 1.16 and may contain bugs. The interface may change. The documentation is being incrementally revised and improved

Usage

First, the DistDeque must be initialized before use by calling its constructor.

var deque = new DistDeque(int, cap=maxElem, targetLocales=ourLocales);

The deque can be used as a queue by using the enqueue and dequeue convenience methods or inserting from one end to remove from another...

deque.enqueue(1);
var (hasElem, elem) = deque.dequeue();

The deque can be used as a stack by using the push and pop convenience methods, or insertion and removing from the same ends...

deque.push(1);
var (hasElem, elem) = deque.pop();

The deque can be used as a list by using the pushBack, pushFront, popBack, and popFront methods. While the deque is not indexable, the ability to append or prepend is powerful enough to allow a total ordering, allowing the user to define the order by letting them insert and remove at whichever ends they so choose.

var deque = new DistDeque(int);
forall i in 1 .. N {
  if i % 2 == 0 then deque.pushFront(i);
  else deque.pushBack(i);
}

The deque supports both serial and parallel iteration, and a means to iterate in a particular order (currently only FIFO and LIFO) using the Ordering enumerator.

for elt in deque.these(Ordering.FIFO) {
  // ...
}

for elt in deque.these(Ordering.LIFO) {
  // ...
}

The deque can also be used in a reduction, although currently reduction only used parallel-iteration, hence reduction will be performed in an unordered fashion. In the future, a specific function may be created to allow reduction in a certain ordering...

deque.addBulk(1..100);
var result = + reduce deque;

Bugs and Known Issues

  1. It is not safe to call other methods while iterating, as it will lead to deadlock. It is an open question whether using a snapshot approach is better to allow concurrent operations at the expense of elevated memory consumption, and iterating directly over elements while holding locks, which strangles potential concurrency.
  2. Reduction cannot be performed in any ordered way. This may be fixed in the near future, either by adding pseudo-parallel iterators that merely yield sequentially in order, or by creating a method to perform reduction for the user in a specified ordering.
  3. This data structure requires network atomic support for scalability, and without it will result in degrading performance. It is another open question whether a specific implementation that is more friendly for remote-execution atomic operations should be provided.
  4. The ordered serial iterators currently do not work when the globalHead or globalTail are negative, which is a result of iteration being an after-thought. This will be improved upon soon, but for now if you use pushBack or pushFront methods, I would advise against using them for now.

Planned Improvements

  1. Double the size of each successor up to some maximum, similar to DistributedBag for unroll blocks. Currently they are fixed-sized, but it can benefit from improved locality if a lot of elements are added at once.

Methods

config param distributedDequeBlockSize = 8

Size of each unroll block for each local deque node.

enum Ordering { NONE, FIFO, LIFO }

The ordering used for serial iteration. NONE, the default, is the most performant and is algorithmically similar to parallel iteration.

record DistDeque

A parallel-safe scalable distributed double-ended queue that supports both insertion and removal from either end of the queue. Can be used as a Queue, Stack, or even a List.

type eltType
var _impl: DistributedDequeImpl(eltType)

The implementation of the Deque is forwarded. See DistributedDequeImpl for documentation.

proc init(type eltType, cap = -1, targetLocales = Locales)
proc forwarding_expr4__value()
class DistributedDequeImpl: CollectionImpl
var cap: int

Capacity, the maximum number of elements a Deque can hold. A cap of -1 is considered unbounded.

var targetLocales: [targetLocDom] locale

Locales to distribute the Deque across.

proc init(type eltType, cap: int = -1, targetLocales: [?locDom] locale = Locales)
proc add(elt: eltType): bool

Syntactic sugar for pushBack.

proc remove(): (bool, eltType)

Syntactic sugar for popFront.

proc enqueue(elt: eltType): bool

Syntactic sugar for pushBack.

proc dequeue(): (bool, eltType)

Syntactic sugar for popFront.

proc push(elt: eltType): bool

Syntactic sugar for pushBack.

proc pop(): (bool, eltType)

Syntactic sugar for popBack.

proc pushBack(elt: eltType): bool

Appends the element to the tail.

proc popBack(): (bool, eltType)

Removes the element at the tail.

proc pushFront(elt: eltType): bool

Appends the element to the head.

proc popFront(): (bool, eltType)

Removes the element at the head.

proc getSize(): int

Obtains the number of elements held by this queue.

proc contains(elt: eltType): bool

Performs a lookup for the element in the data structure.

iter these(param order: Ordering = Ordering.NONE): eltType

Iterate over all elements in the deque in the order specified.

iter these(param order: Ordering = Ordering.NONE): eltType
iter these(param order: Ordering = Ordering.NONE): eltType
iter these(param order: Ordering = Ordering.NONE, param tag: iterKind)
iter these(param order: Ordering = Ordering.NONE, param tag: iterKind, followThis)