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
ParallelForin 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.
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*)
endThe 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.
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*)
endParallelForAuto 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.
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)
endAn 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.
Mutexor an atomic. - Do not print from the loop body; the lines come out mixed up. Store the results and print after
ParallelForreturns. ParallelForwaits 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| Name | Type | Description |
|---|---|---|
state | void* | The internal state of the group. |
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)
endFuture
struct Future| Name | Type | Description |
|---|---|---|
value | i64* | The cell that holds an i64 result. |
text | str* | The cell that holds a text result. |
done | i64* | The flag that is set when the task has finished. |
mu | sync.Mutex | The lock around the result. |
cv | sync.CondVar | The condition that wakes whoever waits for the result. |
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)
endPool
struct Pool| Name | Type | Description |
|---|---|---|
state | void* | The internal state of the pool. |
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*)
endFunctions
CPUCount
func CPUCount(): i64import 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*)
endParallelFor
func ParallelFor(n: i64, workers: i64, body: func(i64))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))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): Poolworkers 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): PoolNew, 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.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*)
endNewAuto
func NewAuto(): PoolThe example for this item is shown with the ones above: pool-Pool.salam
Submit
func Submit(p: Pool, task: func()): boolThe example for this item is shown with the ones above: pool-Pool.salam
TrySubmit
func TrySubmit(p: Pool, task: func()): boolThe example for this item is shown with the ones above: pool-Pool.salam
Wait
func Wait(p: Pool)The example for this item is shown with the ones above: pool-Pool.salam
Stop
func Stop(p: Pool)The example for this item is shown with the ones above: pool-Pool.salam
Running
func Running(p: Pool): i64The example for this item is shown with the ones above: pool-Pool.salam
Pending
func Pending(p: Pool): i64The example for this item is shown with the ones above: pool-Pool.salam
Workers
func Workers(p: Pool): i64The example for this item is shown with the ones above: pool-Pool.salam
SubmitOrRun
func SubmitOrRun(p: Pool, task: func())The example for this item is shown with the ones above: pool-Pool.salam
Go
func Go(task: func())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*)
endGoWait
func GoWait()Go has finished.The example for this item is shown with the ones above: pool-Go.salam
NewGroup
func NewGroup(limit: i64): Grouplimit 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): boolThe example for this item is shown with the ones above: pool-Group.salam
GroupFailed
func GroupFailed(g: Group): boolThe example for this item is shown with the ones above: pool-Group.salam
GroupWait
func GroupWait(g: Group): strThe example for this item is shown with the ones above: pool-Group.salam
GroupStop
func GroupStop(g: Group)The example for this item is shown with the ones above: pool-Group.salam
Async
func Async(p: Pool, task_fn: func(): i64): Futurei64 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): FutureAsync 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): i64i64 result.The example for this item is shown with the ones above: pool-Future.salam
AwaitStr
func AwaitStr(f: Future): strThe example for this item is shown with the ones above: pool-Future.salam
Ready
func Ready(f: Future): boolThe example for this item is shown with the ones above: pool-Future.salam
Release
func Release(f: Future)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>0 to n - 1 on up to workers threads and returns the results in order.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