DistributedDeque¶
Usage
use DistributedDeque;
or
import 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 module is a work in progress and may change in future releases.
Usage¶
First, the DistDeque
must be initialized before use by calling its initializer.
var deque = new DistDeque(int, cap=maxElem, targetLocales=ourLocales);
The deque can be used as a queue by using the DistributedDequeImpl.enqueue
and DistributedDequeImpl.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 DistributedDequeImpl.push
and DistributedDequeImpl.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 DistributedDequeImpl.pushBack
, DistributedDequeImpl.pushFront
, DistributedDequeImpl.popBack
,
and DistributedDequeImpl.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¶
- 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.
- 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.
- 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.
- The ordered serial iterators currently do not work when the
globalHead
orglobalTail
are negative, which is a result of iteration being an after-thought. This will be improved upon soon, but for now if you useDistributedDequeImpl.pushBack
orDistributedDequeImpl.pushFront
methods, I would advise against using them for now.
Planned Improvements¶
- 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
: unmanaged nilable DistributedDequeImpl(eltType)¶ The implementation of the Deque is forwarded. See
DistributedDequeImpl
for documentation.
-
proc
init
(type eltType, cap = -1, targetLocales = Locales)¶
-
type
-
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)¶
-
override proc
add
(elt: eltType): bool¶ Syntactic sugar for pushBack.
-
override 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.
-
override proc
getSize
(): int¶ Obtains the number of elements held by this queue.
-
override 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)
-
var