Standard library · Time and concurrency

pool

Parallel loops, a bounded worker pool, goroutine-style tasks, error groups and futures.

import pool

If each turn of a loop is independent of the others, such as processing each slot of an array on its own, ParallelFor spreads the turns across several worker threads and waits for all of them. The loop body is a function taking an i64, the turn's number.

The package also has a long-lived, bounded worker pool, the Salam answer to goroutines. spawn starts one operating-system thread per call with no limit; a Pool starts its threads once and never more, keeps at most queue tasks waiting, and makes Submit wait when the queue is full, so a fast producer cannot pile up unbounded work. Go runs a task on a shared pool sized to the cores, Group limits how many tasks run at once and keeps the first error, and Async hands back a Future you can Await. To receive from several channels, see Select in chan.

Tasks are threads, not green threads: a task that blocks keeps its worker busy, so a task must not wait for a task queued behind it. Use SubmitOrRun when tasks submit tasks. For shared state, use sync and atomic.

The things people get wrong:

  • Relying on the order of the turns, or changing shared data from them without a lock. Each turn writing to its own slot is safe; anything else needs atomic or a mutex.
  • Making the turns too small. Taking the next turn number costs a lock, and every call starts and joins threads, so a turn should do a fair amount of work (see chunks).
  • Calling ParallelFor in a hot loop. Each call pays for creating threads; parallelize the outer loop instead of the inner one.

One turn per row

The natural fit for ParallelFor is data laid out in rows, such as the pixels of an image or the lines of a table. Make each turn handle one row: the turns touch different memory, so they need no lock, and the result is the same whatever order they ran in.

pool-guide-pixels.salam
import pool
import mem
import str

mut pixels := null as int*
width := 8
height := 6

func brighten row(y: i64):
    repeat width in x:
        i := (y as int) * width + x
        mut v := pixels[i] + 60
        if v > 255:
            v = 255
        end
        pixels[i] = v
    end
end

func main:
    pixels = mem.AllocateZeroed(sizeof(int) * ((width * height) as u64)) as int*
    repeat width * height in i:
        pixels[i] = (i * 37) % 256
    end
    pool.ParallelFor(height, 3, (y: i64): brighten row(y) end)
    repeat height in y:
        mut line := ""
        repeat width in x:
            line = line + str.FromInt(pixels[y * width + x]) + " "
        end
        println line.Trim()
    end
    mem.Free(pixels as void*)
end
Output60 97 134 171 208 245 255 63 100 137 174 211 248 255 66 103 140 177 214 251 255 69 106 143 180 217 254 255 72 109 146 183 220 255 255 75 112 149 186 223 255 255 78 115 152 189 226 255

The loop body here is a short lambda that calls a named function. Keeping the real work in a named function makes it easy to test on its own, without any threads.

Chunks, not single items

Each turn has a small cost of its own, so a million turns that each add one number spend more time on bookkeeping than on adding. Cut the work into a few large chunks instead, let each turn handle one chunk and write its partial result to its own slot, and combine the slots on the main thread at the end.

pool-guide-chunks.salam
import pool
import mem

mut partial := null as i64*
total numbers := 1000000 as i64
chunks := 8

func add chunk(c: i64):
    size := total numbers / (chunks as i64)
    first := c * size + 1
    mut last := first + size - 1
    if c == chunks as i64 - 1:
        last = total numbers
    end
    mut s := 0 as i64
    mut n := first
    until n <= last:
        s += n
        n++
    end
    partial[c] = s
end

func main:
    partial = mem.AllocateZeroed(sizeof(i64) * (chunks as u64)) as i64*
    pool.ParallelForAuto(chunks, (c: i64): add chunk(c) end)
    mut sum := 0 as i64
    repeat chunks in c:
        sum += partial[c]
    end
    println "chunks:", chunks
    println "sum of 1 to", total numbers, "=", sum
    println "check:", sum == total numbers * (total numbers + 1) / 2
    mem.Free(partial as void*)
end
Outputchunks: 8 sum of 1 to 1000000 = 500000500000 check: true

ParallelForAuto picks the number of workers from the processor count. A few chunks per worker is a good size: enough for the work to even out when some chunks are slower, few enough that the overhead stays small.

Combine results with an atomic counter

When the turns produce something that has to be added into one place, such as a count of matches, the simplest safe choice is an atomic.I64. Here every number below 100000 is one turn, and each turn that finds a prime adds one to the shared counter.

pool-guide-primes.salam
import pool
import atomic

mut found := atomic.I64 {}

func is prime(n: i64): bool:
    if n < 2:
        ret false
    end
    mut d := 2 as i64
    until d * d <= n:
        if n % d == 0:
            ret false
        end
        d++
    end
    ret true
end

func main:
    found = atomic.NewI64(0)
    pool.ParallelFor(100000, pool.CPUCount(), (n: i64):
        if is prime(n):
            atomic.Add(found, 1)
        end
    end)
    println "primes below 100000:", atomic.Load(found)
    atomic.DestroyI64(found)
end
Outputprimes below 100000: 9592

An atomic add per match is fine when matches are rare compared with the work of each turn. If every turn would update the counter, use partial results per chunk as in the previous section instead.

Rules for the loop body

  • Never rely on the order of the turns. Turn 5 can finish before turn 0.
  • A turn may write to its own slot freely. Anything shared needs a sync.Mutex or an atomic.
  • Do not print from the loop body; the lines come out mixed up. Store the results and print after ParallelFor returns.
  • ParallelFor waits for every turn, so as soon as it returns all results are ready and no join is needed.
  • Small loops are faster without threads. Parallelize only when one run of the loop takes noticeable time.

Types

Group

struct Group
A set of tasks with a limit on how many run at once and a shared first error.
NameTypeDescription
statevoid*The internal state of the group.
pool-Group.salam
import pool

func check(n: int): str:
    if n == 7:
        ret "item 7 is bad"
    end
    ret ""
end

func main:
    g := pool.NewGroup(3 as i64)
    repeat 20 in i:
        pool.GroupGo(g, (): ret check(i) end)
    end
    println pool.GroupWait(g)
    println pool.GroupFailed(g)
    pool.GroupStop(g)
end
Outputitem 7 is bad true

Future

struct Future
The result of a task that is still running.
NameTypeDescription
valuei64*The cell that holds an i64 result.
textstr*The cell that holds a text result.
donei64*The flag that is set when the task has finished.
musync.MutexThe lock around the result.
cvsync.CondVarThe condition that wakes whoever waits for the result.
pool-Future.salam
import pool

func fib(n: i64): i64:
    if n < 2:
        ret n
    end
    ret fib(n - 1) + fib(n - 2)
end

func main:
    p := pool.New(2 as i64, 4 as i64)
    a := pool.Async(p, (): ret fib(25 as i64) end)
    b := pool.AsyncStr(p, (): ret "done" end)
    println pool.Await(a)
    println pool.AwaitStr(b)
    println pool.Ready(a)
    pool.Release(a)
    pool.Release(b)
    pool.Stop(p)
end
Output75025 done true

Pool

struct Pool
A bounded pool of worker threads.
NameTypeDescription
statevoid*The internal state of the pool.
pool-Pool.salam
import mem
import pool
import sync

mut done := null as i64*
mut gate := null as i64*

func work:
    sync.SleepMs(2)
    atomic_add(done, 1 as i64)
end

func hold:
    until atomic_load(gate) != 0:
        sync.SleepMs(1)
    end
end

func main:
    done = mem.AllocateZeroed(8 as u64) as i64*
    gate = mem.AllocateZeroed(8 as u64) as i64*

    p := pool.New(4 as i64, 8 as i64)
    println "workers: ", pool.Workers(p)
    repeat 100:
        pool.Submit(p, (): work() end)
    end
    pool.Wait(p)
    println "finished: ", atomic_load(done)
    pool.Stop(p)

    q := pool.New(1 as i64, 1 as i64)
    atomic_store(gate, 1 as i64)
    pool.Submit(q, (): hold() end)
    until pool.Running(q) == 0:
        sync.SleepMs(1)
    end
    println "queued: ", pool.TrySubmit(q, (): work() end)
    println "full: ", pool.TrySubmit(q, (): work() end)
    println "pending: ", pool.Pending(q)
    atomic_store(gate, 0 as i64)
    pool.Stop(q)
    println "drained: ", atomic_load(done)

    mem.Free(done as void*)
    mem.Free(gate as void*)
end
Outputworkers: 4 finished: 100 queued: true full: false pending: 1 drained: 101

Functions

CPUCount

func CPUCount(): i64
The number of processor cores that are online, at least one.
pool-ParallelFor.salam
import pool
import mem

mut squares := null as i64*

func main:
    println pool.CPUCount() >= 1
    squares = mem.AllocateZeroed(80 as u64) as i64*
    pool.ParallelFor(10, 4, (i: i64): squares[i] = i * i end)
    mut total := 0 as i64
    repeat 10 in i:
        total += squares[i]
    end
    println total
    pool.ParallelForAuto(10, (i: i64): squares[i] = -i end)
    println squares[9]
    mem.Free(squares as void*)
end
Outputtrue 285 -9

ParallelFor

func ParallelFor(n: i64, workers: i64, body: func(i64))
Runs the body for the numbers zero to n - 1 on workers new threads, at most n of them, and returns when every turn is done. Nothing happens when n is zero or less.

The example for this item is shown with the ones above: pool-ParallelFor.salam

ParallelForAuto

func ParallelForAuto(n: i64, body: func(i64))
Like ParallelFor, with one thread per core from CPUCount.

The example for this item is shown with the ones above: pool-ParallelFor.salam

New

func New(workers: i64, queue: i64): Pool
Starts a pool with workers threads and room for queue waiting tasks. Both are raised to at least one. The thread count never grows.

The example for this item is shown with the ones above: pool-Pool.salam

NewElastic

func NewElastic(min: i64, max: i64, queue: i64): Pool
Like New, but starts with min workers and adds one, up to max, whenever tasks are waiting and every worker is busy. It never exceeds max and never shrinks. Use it when tasks may block on each other.
pool-Elastic.salam
import chan
import mem
import pool

mut box := chan.Chan {} as chan.Chan<i64>
mut got := null as i64*

func waiter():
    mut ok := false
    v := box.recv(ok)
    atomic_store(got, v)
end

func sender():
    box.send(7 as i64)
end

func main:
    box.init(1 as i64)
    got = mem.AllocateZeroed(8 as u64) as i64*
    p := pool.NewElastic(1 as i64, 4 as i64, 8 as i64)
    println "start: ", pool.Workers(p)
    pool.Submit(p, (): waiter() end)
    pool.Submit(p, (): sender() end)
    pool.Wait(p)
    println "received: ", atomic_load(got)
    println "grew: ", pool.Workers(p) > 1
    println "capped: ", pool.Workers(p) <= 4
    pool.Stop(p)
    box.Free()
    mem.Free(got as void*)
end
Outputstart: 1 received: 7 grew: true capped: true

NewAuto

func NewAuto(): Pool
A pool with one worker per core and a queue four times that size.

The example for this item is shown with the ones above: pool-Pool.salam

Submit

func Submit(p: Pool, task: func()): bool
Queues a task. It waits while the queue is full, which is the backpressure that bounds the pool. Returns false only if the pool is stopped.

The example for this item is shown with the ones above: pool-Pool.salam

TrySubmit

func TrySubmit(p: Pool, task: func()): bool
Queues a task without waiting. Returns false when the queue is full or the pool is stopped.

The example for this item is shown with the ones above: pool-Pool.salam

Wait

func Wait(p: Pool)
Waits until the queue is empty and no task is running. The pool can be used again afterwards.

The example for this item is shown with the ones above: pool-Pool.salam

Stop

func Stop(p: Pool)
Finishes the queued tasks, joins the workers and frees the pool. Do not use the pool after this.

The example for this item is shown with the ones above: pool-Pool.salam

Running

func Running(p: Pool): i64
The number of tasks running now.

The example for this item is shown with the ones above: pool-Pool.salam

Pending

func Pending(p: Pool): i64
The number of tasks waiting in the queue.

The example for this item is shown with the ones above: pool-Pool.salam

Workers

func Workers(p: Pool): i64
The number of worker threads of the pool.

The example for this item is shown with the ones above: pool-Pool.salam

SubmitOrRun

func SubmitOrRun(p: Pool, task: func())
Queues a task, or runs it on the calling thread when the queue is full. Safe for tasks that submit tasks.

The example for this item is shown with the ones above: pool-Pool.salam

Go

func Go(task: func())
Runs a task on a shared pool with one worker per core, created on first use.
pool-Go.salam
import mem
import pool

mut hits := null as i64*

func main:
    hits = mem.AllocateZeroed(8 as u64) as i64*
    repeat 100:
        pool.Go((): atomic_add(hits, 1 as i64) end)
    end
    pool.GoWait()
    println atomic_load(hits)
    mem.Free(hits as void*)
end
Output100

GoWait

func GoWait()
Waits until every task started with Go has finished.

The example for this item is shown with the ones above: pool-Go.salam

NewGroup

func NewGroup(limit: i64): Group
Creates a group that runs at most limit tasks at a time.

The example for this item is shown with the ones above: pool-Group.salam

GroupGo

func GroupGo(g: Group, task_fn: func(): str): bool
Adds a task that returns an error text, empty for success. Once any task fails, tasks not yet started are skipped.

The example for this item is shown with the ones above: pool-Group.salam

GroupFailed

func GroupFailed(g: Group): bool
True once any task of the group has returned an error.

The example for this item is shown with the ones above: pool-Group.salam

GroupWait

func GroupWait(g: Group): str
Waits for the group and returns the first error text, or an empty text.

The example for this item is shown with the ones above: pool-Group.salam

GroupStop

func GroupStop(g: Group)
Frees the group and its threads.

The example for this item is shown with the ones above: pool-Group.salam

Async

func Async(p: Pool, task_fn: func(): i64): Future
Runs a task that returns an i64 and gives back a future for it.

The example for this item is shown with the ones above: pool-Future.salam

AsyncStr

func AsyncStr(p: Pool, task_fn: func(): str): Future
Like Async for a task that returns a text.

The example for this item is shown with the ones above: pool-Future.salam

Await

func Await(f: Future): i64
Waits for the task and returns its i64 result.

The example for this item is shown with the ones above: pool-Future.salam

AwaitStr

func AwaitStr(f: Future): str
Waits for the task and returns its text result.

The example for this item is shown with the ones above: pool-Future.salam

Ready

func Ready(f: Future): bool
True when the task has finished, without waiting.

The example for this item is shown with the ones above: pool-Future.salam

Release

func Release(f: Future)
Frees a future after its result has been taken.

The example for this item is shown with the ones above: pool-Future.salam

Map

func Map(n: i64, workers: i64, task_fn: func(i64): i64): Vector<i64>
Calls the function for 0 to n - 1 on up to workers threads and returns the results in order.
pool-Map.salam
import pool

func main:
    squares := pool.Map(10 as i64, 4 as i64, (i: i64): ret i * i end)
    println "count: ", squares.Len()
    mut total := 0 as i64
    repeat squares.Len() in i:
        total += squares.Get(i)
    end
    println "sum: ", total
    println "first and last: ", squares.Get(0), squares.Get(9)
    println "empty: ", pool.Map(0 as i64, 4 as i64, (i: i64): ret i end).Len()
end
Outputcount: 10 sum: 285 first and last: 0 81 empty: 0