/**`std.parallelism` implements high-level primitives for SMP parallelism.These include parallel foreach, parallel reduce, parallel eager map, pipeliningand future/promise parallelism.  `std.parallelism` is recommended when thesame operation is to be executed in parallel on different data, or when afunction is to be executed in a background thread and its result returned to awell-defined main thread.  For communication between arbitrary threads, see`std.concurrency`. `std.parallelism` is based on the concept of a `Task`.  A `Task` is anobject that represents the fundamental unit of work in this library and may beexecuted in parallel with any other `Task`.  Using `Task`directly allows programming with a future/promise paradigm.  All othersupported parallelism paradigms (parallel foreach, map, reduce, pipelining)represent an additional level of abstraction over `Task`.  Theyautomatically create one or more `Task` objects, or closely related typesthat are conceptually identical but not part of the public API. After creation, a `Task` may be executed in a new thread, or submittedto a `TaskPool` for execution.  A `TaskPool` encapsulates a task queueand its worker threads.  Its purpose is to efficiently map a largenumber of `Task`s onto a smaller number of threads.  A task queue is aFIFO queue of `Task` objects that have been submitted to the`TaskPool` and are awaiting execution.  A worker thread is a thread thatis associated with exactly one task queue.  It executes the `Task` at thefront of its queue when the queue has work available, or sleeps whenno work is available.  Each task queue is associated with zero ormore worker threads.  If the result of a `Task` is needed before executionby a worker thread has begun, the `Task` can be removed from the task queueand executed immediately in the thread where the result is needed. Warning:  Unless marked as `@trusted` or `@safe`, artifacts in          this module allow implicit data sharing between threads and cannot          guarantee that client code is free from low level data races. Source:    $(PHOBOSSRC std/parallelism.d)Author:  David SimchaCopyright:  Copyright (c) 2009-2011, David Simcha.License:    $(HTTP boost.org/LICENSE_1_0.txt, Boost License 1.0)*/module std.parallelism; version (OSX)    version = Darwin;else version (iOS)    version = Darwin;else version (TVOS)    version = Darwin;else version (WatchOS)    version = Darwin; ///@system unittest{    import std.algorithm.iteration : map;    import std.math.operations : isClose;    import std.parallelism : taskPool;    import std.range : iota;     // Parallel reduce can be combined with    // std.algorithm.iteration.map to interesting effect.    // The following example (thanks to Russel Winder)    // calculates pi by quadrature  using    // std.algorithm.map and TaskPool.reduce.    // getTerm is evaluated in parallel as needed by    // TaskPool.reduce.    //    // Timings on an Intel i5-3450 quad core machine    // for n = 1_000_000_000:    //    // TaskPool.reduce:       1.067 s    // std.algorithm.reduce:  4.011 s     enum n = 1_000_000;    enum delta = 1.0 / n;     alias getTerm = (int i)    {        immutable x = ( i - 0.5 ) * delta;        return delta / ( 1.0 + x * x ) ;    };     immutable pi = 4.0 * taskPool.reduce!"a + b"(n.iota.map!getTerm);     assert(pi.isClose(3.14159, 1e-5));} import core.atomic;import core.memory;import core.sync.condition;import core.thread; import std.functional;import std.meta;import std.range.primitives;import std.traits; /*(For now public undocumented with reserved name.) A lazily initialized global constant. The underlying value is a shared globalstatically initialized to `outOfBandValue` which must not be a legit value ofthe constant. Upon the first call the situation is detected and the global isinitialized by calling `initializer`. The initializer is assumed to be pure(even if not marked as such), i.e. return the same value upon repeated calls.For that reason, no special precautions are taken so `initializer` may be calledmore than one time leading to benign races on the cached value. In the quiescent state the cost of the function is an atomic load from a global. Params:    T = The type of the pseudo-constant (may be qualified)    outOfBandValue = A value that cannot be valid, it is used for initialization    initializer = The function performing initialization; must be `nothrow` Returns:    The lazily initialized value*/@property pureT __lazilyInitializedConstant(T, alias outOfBandValue, alias initializer)()if (is(Unqual!T : T)    && is(typeof(initializer()) : T)    && is(typeof(outOfBandValue) : T)){    static T impl() nothrow    {        // Thread-local cache        static Unqual!T tls = outOfBandValue;        auto local = tls;        // Shortest path, no atomic operations        if (local != outOfBandValue) return local;        // Process-level cache        static shared Unqual!T result = outOfBandValue;        // Initialize both process-level cache and tls        local = atomicLoad(result);        if (local == outOfBandValue)        {            local = initializer();            atomicStore(result, local);        }        tls = local;        return local;    }     import std.traits : SetFunctionAttributes;    alias Fun = SetFunctionAttributes!(typeof(&impl), "D",        functionAttributes!(typeof(&impl)) | FunctionAttribute.pure_);    auto purified = (() @trusted => cast(Fun) &impl)();    return purified();} // Returns the size of a cache line.alias cacheLineSize =    __lazilyInitializedConstant!(immutable(size_t), size_t.max, cacheLineSizeImpl); private size_t cacheLineSizeImpl() @nogc nothrow @trusted{    size_t result = 0;    import core.cpuid : datacache;    foreach (ref const cachelevel; datacache)    {        if (cachelevel.lineSize > result && cachelevel.lineSize < uint.max)        {            result = cachelevel.lineSize;        }    }    return result;} @nogc @safe nothrow unittest{    assert(cacheLineSize == cacheLineSizeImpl);} /* Atomics code.  These forward to core.atomic, but are written like this   for two reasons:    1.  They used to actually contain ASM code and I don' want to have to change       to directly calling core.atomic in a zillion different places.    2.  core.atomic has some misc. issues that make my use cases difficult       without wrapping it.  If I didn't wrap it, casts would be required       basically everywhere.*/private void atomicSetUbyte(T)(ref T stuff, T newVal)if (__traits(isIntegral, T) && is(T : ubyte)){    //core.atomic.cas(cast(shared) &stuff, stuff, newVal);    atomicStore(*(cast(shared) &stuff), newVal);} private ubyte atomicReadUbyte(T)(ref T val)if (__traits(isIntegral, T) && is(T : ubyte)){    return atomicLoad(*(cast(shared) &val));} // This gets rid of the need for a lot of annoying casts in other parts of the// code, when enums are involved.private bool atomicCasUbyte(T)(ref T stuff, T testVal, T newVal)if (__traits(isIntegral, T) && is(T : ubyte)){    return core.atomic.cas(cast(shared) &stuff, testVal, newVal);} /*--------------------- Generic helper functions, etc.------------------------*/private template MapType(R, functions...){    static assert(functions.length);     ElementType!R e = void;    alias MapType =        typeof(adjoin!(staticMap!(unaryFun, functions))(e));} private template ReduceType(alias fun, R, E){    alias ReduceType = typeof(binaryFun!fun(E.init, ElementType!R.init));} private template noUnsharedAliasing(T){    enum bool noUnsharedAliasing = !hasUnsharedAliasing!T;} // This template tests whether a function may be executed in parallel from// @safe code via Task.executeInNewThread().  There is an additional// requirement for executing it via a TaskPool.  (See isSafeReturn).private template isSafeTask(F){    enum bool isSafeTask =        (functionAttributes!F & (FunctionAttribute.safe | FunctionAttribute.trusted)) != 0 &&        (functionAttributes!F & FunctionAttribute.ref_) == 0 &&        (isFunctionPointer!F || !hasUnsharedAliasing!F) &&        allSatisfy!(noUnsharedAliasing, Parameters!F);} @safe unittest{    alias F1 = void function() @safe;    alias F2 = void function();    alias F3 = void function(uint, string) @trusted;    alias F4 = void function(uint, char[]);     static assert( isSafeTask!F1);    static assert(!isSafeTask!F2);    static assert( isSafeTask!F3);    static assert(!isSafeTask!F4);     alias F5 = uint[] function(uint, string) pure @trusted;    static assert( isSafeTask!F5);} // This function decides whether Tasks that meet all of the other requirements// for being executed from @safe code can be executed on a TaskPool.// When executing via TaskPool, it's theoretically possible// to return a value that is also pointed to by a worker thread's thread local// storage.  When executing from executeInNewThread(), the thread that executed// the Task is terminated by the time the return value is visible in the calling// thread, so this is a non-issue.  It's also a non-issue for pure functions// since they can't read global state.private template isSafeReturn(T){    static if (!hasUnsharedAliasing!(T.ReturnType))    {        enum isSafeReturn = true;    }    else static if (T.isPure)    {        enum isSafeReturn = true;    }    else    {        enum isSafeReturn = false;    }} private template randAssignable(R){    enum randAssignable = isRandomAccessRange!R && hasAssignableElements!R;} private enum TaskStatus : ubyte{    notStarted,    inProgress,    done} private template AliasReturn(alias fun, T...){    alias AliasReturn = typeof({ T args; return fun(args); });} // Should be private, but std.algorithm.reduce is used in the zero-thread case// and won't work w/ private.template reduceAdjoin(functions...){    static if (functions.length == 1)    {        alias reduceAdjoin = binaryFun!(functions[0]);    }    else    {        T reduceAdjoin(T, U)(T lhs, U rhs)        {            alias funs = staticMap!(binaryFun, functions);             foreach (i, Unused; typeof(lhs.expand))            {                lhs.expand[i] = funs[i](lhs.expand[i], rhs);            }             return lhs;        }    }} private template reduceFinish(functions...){    static if (functions.length == 1)    {        alias reduceFinish = binaryFun!(functions[0]);    }    else    {        T reduceFinish(T)(T lhs, T rhs)        {            alias funs = staticMap!(binaryFun, functions);             foreach (i, Unused; typeof(lhs.expand))            {                lhs.expand[i] = funs[i](lhs.expand[i], rhs.expand[i]);            }             return lhs;        }    }} private template isRoundRobin(R : RoundRobinBuffer!(C1, C2), C1, C2){    enum isRoundRobin = true;} private template isRoundRobin(T){    enum isRoundRobin = false;} @safe unittest{    static assert( isRoundRobin!(RoundRobinBuffer!(void delegate(char[]), bool delegate())));    static assert(!isRoundRobin!(uint));} // This is the base "class" for all of the other tasks.  Using C-style// polymorphism to allow more direct control over memory allocation, etc.private struct AbstractTask{    AbstractTask* prev;    AbstractTask* next;     // Pointer to a function that executes this task.    void function(void*) runTask;     Throwable exception;    ubyte taskStatus = TaskStatus.notStarted;     bool done() @property    {        if (atomicReadUbyte(taskStatus) == TaskStatus.done)        {            if (exception)            {                throw exception;            }             return true;        }         return false;    }     void job()    {        runTask(&this);    }} /**`Task` represents the fundamental unit of work.  A `Task` may beexecuted in parallel with any other `Task`.  Using this struct directlyallows future/promise parallelism.  In this paradigm, a function (or delegateor other callable) is executed in a thread other than the one it was calledfrom.  The calling thread does not block while the function is being executed.A call to `workForce`, `yieldForce`, or `spinForce` is used toensure that the `Task` has finished executing and to obtain the returnvalue, if any.  These functions and `done` also act as full memory barriers,meaning that any memory writes made in the thread that executed the `Task`are guaranteed to be visible in the calling thread after one of these functionsreturns. The $(REF task, std,parallelism) and $(REF scopedTask, std,parallelism) functions canbe used to create an instance of this struct.  See `task` for usage examples. Function results are returned from `yieldForce`, `spinForce` and`workForce` by ref.  If `fun` returns by ref, the reference will pointto the returned reference of `fun`.  Otherwise it will point to afield in this struct. Copying of this struct is disabled, since it would provide no useful semantics.If you want to pass this struct around, you should do so by reference orpointer. Bugs:  Changes to `ref` and `out` arguments are not propagated to the       call site, only to `args` in this struct.*/struct Task(alias fun, Args...){    private AbstractTask base = {runTask : &impl};    private alias base this;     private @property AbstractTask* basePtr()    {        return &base;    }     private static void impl(void* myTask)    {        import std.algorithm.internal : addressOf;         Task* myCastedTask = cast(typeof(this)*) myTask;        static if (is(ReturnType == void))        {            fun(myCastedTask._args);        }        else static if (is(typeof(&(fun(myCastedTask._args)))))        {            myCastedTask.returnVal = addressOf(fun(myCastedTask._args));        }        else        {            myCastedTask.returnVal = fun(myCastedTask._args);        }    }     private TaskPool pool;    private bool isScoped;  // True if created with scopedTask.     Args _args;     /**    The arguments the function was called with.  Changes to `out` and    `ref` arguments will be visible here.    */    static if (__traits(isSame, fun, run))    {        alias args = _args[1..$];    }    else    {        alias args = _args;    }      // The purpose of this code is to decide whether functions whose    // return values have unshared aliasing can be executed via    // TaskPool from @safe code.  See isSafeReturn.    static if (__traits(isSame, fun, run))    {        static if (isFunctionPointer!(_args[0]))        {            private enum bool isPure =            (functionAttributes!(Args[0]) & FunctionAttribute.pure_) != 0;        }        else        {            // BUG:  Should check this for delegates too, but std.traits            //       apparently doesn't allow this.  isPure is irrelevant            //       for delegates, at least for now since shared delegates            //       don't work.            private enum bool isPure = false;        }     }    else    {        // We already know that we can't execute aliases in @safe code, so        // just put a dummy value here.        private enum bool isPure = false;    }      /**    The return type of the function called by this `Task`.  This can be    `void`.    */    alias ReturnType = typeof(fun(_args)); 

Lines 1–500 of 4941. Load more