LockFreeStack¶
Usage
use LockFreeStack;
or
import LockFreeStack;
Support for a lock-free Treiber stack.
Warning
This module relies on the AtomicObjects
package module, which
has several platform restrictions in its current state:
It relies on Chapel
extern
code blocks and so requires that the Chapel compiler is built with LLVM enabled.The implementation relies on using either
GCC
style inline assembly (for x86-64) or a GCC/clang builtin, and so is restricted to aCHPL_TARGET_COMPILER
value ofgnu
,clang
, orllvm
.The implementation does not work with
CHPL_ATOMICS=locks
.
An implementation of the Treiber Stack [1], a lock-free stack. Concurrent safe
memory reclamation is handled by an internal EpochManager
. Usage of the
stack can be seen below.
var lfs = new LockFreeStack(int);
forall i in 1..N do lfs.push(i);
var total : int;
coforall tid in 1..here.maxTaskPar with (+ reduce total) {
var (hasElt, elt) = lfs.pop();
while hasElt {
total += elt;
(hasElt, elt) = lfs.pop();
}
}
As an optimization, the user can register to receive a TokenWrapper
, and pass this
to the stack. This can provide significant improvement in performance by up to an order of magnitude
by avoiding the overhead of registering and unregistering for each operation.
var lfs = new LockFreeStack(int);
forall i in 1..N with (var tok = lfs.getToken()) do lfs.push(i,tok);
var total : int;
coforall tid in 1..here.maxTaskPar with (+ reduce total) {
var tok = lfs.getToken();
var (hasElt, elt) = lfs.pop(tok);
while hasElt {
total += elt;
(hasElt, elt) = lfs.pop(tok);
}
}
Lastly, to safely reclaim memory, the user must explicitly invoke tryReclaim
, or else
there will be a memory leak. This must be explicitly invoked so that the user may tune how often
reclamation will be attempted. Reclamation is concurrent-safe, but if called too frequently,
it can add unnecessary overhead. A complete example of what would be considered ‘optimal’
usage of this lock-free stack.
var lfs = new LockFreeStack(int);
forall i in 1..N with (var tok = lfs.getToken()) do lfs.push(i,tok);
var total : int;
coforall tid in 1..here.maxTaskPar with (+ reduce total) {
var tok = lfs.getToken();
var (hasElt, elt) = lfs.pop(tok);
var n : int;
while hasElt {
total += elt;
(hasElt, elt) = lfs.pop(tok);
n += 1;
if n % GC_THRESHOLD == 0 then lfs.tryReclaim();
}
}
Also provided, is a utility method for draining the stack of all elements,
called drain
. This iterator will implicitly call tryReclaim
at the
end and will optimally create one token per task.
var lfs = new LockFreeStack(int);
forall i in 1..N with (var tok = lfs.getToken()) do lfs.push(i,tok);
var total = + reduce lfs.drain();
- class Node¶
- type eltType¶
- var val : toNilableIfClassType(eltType)¶
- var next : unmanaged Node(eltType)?¶
- proc init(val: ?eltType)¶
- proc init(type eltType)
- class LockFreeStack¶
- type objType¶
- var _top : AtomicObject(unmanaged Node(objType)?, hasGlobalSupport = true, hasABASupport = false)¶
- var _manager = new owned LocalEpochManager()¶
- proc objTypeOpt type¶
- proc init(type objType)¶
- proc deinit()¶
- proc getToken() : owned TokenWrapper¶
- proc push(newObj: objType, tok: owned TokenWrapper = getToken())¶
- proc pop(tok: owned TokenWrapper = getToken()) : (bool, objType)¶
- iter drain() : objTypeOpt¶
- iter drain(param tag: iterKind) : objTypeOpt where tag == iterKind.standalone
- proc tryReclaim()¶