dymokomi/luce-std
Source of release 0.7.2
0.7.2 / src / parallel / pool.lucb
#==============================================================================================
#
# pool - The process-wide threads that run calls' and jobs' items
#
# DESCRIPTION:
# Batches of items wait in two queues, `for_each` calls first and started jobs after,
# and the pool's threads join whichever has items left and room for one more thread.
# A thread out of work watches for a new batch for a few microseconds, when no more
# than one other thread does, pausing the processor and reading the clock only every
# few pauses, and then sleeps on a condition; a new batch wakes the sleepers it needs
# beyond the threads already watching, one directly and the rest through each other.
#
#==============================================================================================
## How long an idle pool thread watches for new work before it sleeps, and a caller for
## its call's last items before it sleeps, in nanoseconds. Both spins pause the processor
## `pauses` times between readings of the clock: a pause takes from a cycle on some
## processors to over a hundred on others, so counting them alone gives no fixed time.
let watch_time: u64 = 4000
let finish_time: u64 = 8000
let pauses: usize = 16
## The most idle threads watching at once; the others sleep as soon as they run out of
## work, so a quiet moment costs a couple of short spins however many processors there are.
let most_watching: usize = 2
## One call's items, or one started job's: a `for_each` call's on its caller's stack, a
## job's on the heap. It is in a queue while it has items to hand out, and kept until no
## pool thread is on it.
struct Batch:
var context: void*
var work: func(void*, usize, usize) -> unit!
var count: usize
var next: @usize
var failed: @bool
## A job's: it waits in the job queue, and counts the items that have returned.
var background: bool
var finished: @usize
## The first failure: its code, and its message copied into `room`, since the handler
## that caught it gives the original back when it finishes (base.md ยง11.3).
var code: ErrorCode?
var room: u8[512]
var message: str
## Under `lock`: the worker numbers it hands out, below `slots`, and how many it has
## (the next thread to join takes number `taken`); whether its owner sleeps until the
## pool threads leave; its place in a queue. `working` counts the pool threads on it
## now; it changes under `lock`, and the owner watches it.
var slots: usize
var taken: usize
var waiting: bool
var working: @usize
var queued: bool
var after: Batch*?
## The pool's lock, the condition idle threads sleep on, and the one owners sleep on until
## the pool threads leave their batch, each 64 bytes from the others and from whatever lies
## around them. On Windows a thread in WaitOnAddress often returns when a thread waiting on
## an address less than 32 bytes from its own is woken; `sync` sleeps again then, so no
## wait returns early, but each such return is a context switch. Side by side, contended
## unlocks of the lock cost the sleeping pool threads those: a call over 20 tiny items took
## 10.5 us instead of 6.2 there (on Linux and macOS the gaps make no difference).
struct Waits:
var before: u8[64]
var lock: sync.Mutex
var after_lock: u8[60]
var work_ready: sync.Condition
var after_work: u8[60]
var job_done: sync.Condition
var after_done: u8[60]
## Batches with items to hand out, oldest first.
struct Queue:
var first: Batch*?
var last: Batch*?
## The pool, guarded by `lock`: the queues and the threads. `places` counts the worker
## numbers the queued batches still hand out, for idle threads watching for work without
## the lock; it changes under the lock. `spinning` counts the threads watching it, and
## `relay` the sleeping threads the batches still want woken, each woken thread waking up
## to two more, so a caller pays for one wake however many threads it wants.
var waits: Waits
var call_queue: Queue
var job_queue: Queue
var started: bool = false
var pool_threads: usize = 0
var sleeping: usize = 0
var spinning: usize = 0
var relay: usize = 0
var places: @usize
var running: @usize
## Set on pool threads, where a started job runs at once on the starting thread.
local var on_pool: bool = false
## Take `batch`'s indices until none are left or one has failed, as worker `worker`.
func work_on(batch: Batch*, worker: usize):
while not batch.failed.load(.acquire):
let index = batch.next.add(1, .relaxed)
if index >= batch.count:
return
batch.work(batch.context, index, worker) catch failure:
# the first thread to fail keeps its error; the others' are dropped
if not batch.failed.swap(true, .acq_rel):
batch.code = failure.code
batch.message = strings.copy_into(batch.room, failure.message)
if batch.background:
_ = batch.finished.add(1, .release)
return
if batch.background:
_ = batch.finished.add(1, .release)
## Queue `batch` for pool threads to take its numbers from `taken` up to `slots`, no more
## of them than the pool has: whether it was queued, which it is not when the pool has no
## thread to give. Threads watching for work see it at once; of those asleep, wake as many
## as the queued places need beyond the watchers: one now, after letting go of the lock it
## will want, and that one wakes the rest, since waking many at once costs the waker tens
## of microseconds on macOS.
func post(batch: Batch*) -> bool:
waits.lock.lock()
start_pool()
if batch.slots - batch.taken > pool_threads:
batch.slots = batch.taken + pool_threads
let open = batch.slots - batch.taken
var wake = false
if open > 0:
batch.queued = true
let queue = &job_queue if batch.background else &call_queue
if let last = queue.last:
last.after = batch
else:
queue.first = batch
queue.last = batch
let total = places.add(open, .release) + open
let uncovered = total - spinning if total > spinning else 0
var wanted = open if open < uncovered else uncovered
if wanted > sleeping:
wanted = sleeping
if wanted > 0:
relay += wanted - 1
wake = true
waits.lock.unlock()
if wake:
waits.work_ready.signal()
return open > 0
## Wait until no pool thread is on `batch` and take it off its queue; after this its owner
## may let it go. The owner has taken every index it could, so the threads still on it are
## finishing their last items: watch them for a moment, then sleep.
func finish(batch: Batch*):
let begun = time.now()
while batch.working.load(.acquire) > 0 and time.since(begun) < finish_time:
for _ in 0..<pauses:
thread.pause()
waits.lock.lock()
unlink(batch)
while batch.working.load(.acquire) > 0:
batch.waiting = true
waits.job_done.wait(&waits.lock)
waits.lock.unlock()
## Drop `batch` from its queue if it is there; under `lock`.
func unlink(batch: Batch*):
if not batch.queued:
return
batch.queued = false
_ = places.sub(batch.slots - batch.taken, .relaxed)
let queue = &job_queue if batch.background else &call_queue
var previous: Batch*? = none
var cursor = queue.first
while let current = cursor:
if current == batch:
if let before = previous:
before.after = current.after
else:
queue.first = current.after
if queue.last == batch:
queue.last = previous
return
previous = cursor
cursor = current.after
## A queued batch with items left and room for one more pool thread, calls before jobs;
## batches with nothing left to hand out leave their queue. Under `lock`.
func next_batch() -> Batch*?:
if let batch = open_in(&call_queue):
return batch
return open_in(&job_queue)
func open_in(queue: Queue*) -> Batch*?:
var cursor = queue.first
while let batch = cursor:
cursor = batch.after
if batch.next.load(.relaxed) >= batch.count or batch.failed.load(.relaxed):
unlink(batch)
continue
if batch.taken < batch.slots:
return batch
return none
## Start the pool's threads the first time it is used; under `lock`.
func start_pool():
if started:
return
started = true
if not platform.windows:
_ = pthread_atfork(none, none, forget_pool)
let threads = workers(most_threads) - 1
for _ in 0..<threads:
let handle = thread.spawn(pool_thread, none, name = "luce-parallel") catch failure:
# fewer threads only means less help: callers do the rest
break
handle.detach()
pool_threads += 1
## In a child made by `fork`, which has the parent's memory but none of its threads: no
## pool, and a lock some other thread of the parent may have held.
func forget_pool():
waits = Waits()
call_queue = Queue()
job_queue = Queue()
started = false
pool_threads = 0
sleeping = 0
spinning = 0
relay = 0
places.store(0, .relaxed)
running.store(0, .relaxed)
## A pool thread: join batches with items left, and when there are none, watch briefly for
## the next one if fewer than `most_watching` threads already do, and then sleep until one
## is posted.
func pool_thread(raw: void*?):
_ = raw
on_pool = true
_ = running.add(1, .release)
waits.lock.lock()
while true:
if let batch = next_batch():
let worker = batch.taken
batch.taken += 1
_ = places.sub(1, .relaxed)
_ = batch.working.add(1, .relaxed)
waits.lock.unlock()
ownership.enter()
work_on(batch, worker)
ownership.finish_task()
waits.lock.lock()
if batch.working.sub(1, .release) == 1 and batch.waiting:
waits.job_done.broadcast()
continue
if spinning < most_watching:
spinning += 1
waits.lock.unlock()
let found = watch()
if not found:
waits.lock.lock()
spinning -= 1
if found or places.load(.acquire) > 0:
continue
sleeping += 1
waits.work_ready.wait(&waits.lock)
sleeping -= 1
# wake up to two more sleepers while a batch still has room; once none has, stop
var wake: usize = 0
if relay > 0 and sleeping > 0 and next_batch() != none:
wake = 2 if relay >= 2 and sleeping >= 2 else 1
relay -= wake
else:
relay = 0
if wake > 0:
waits.lock.unlock()
for _ in 0..<wake:
waits.work_ready.signal()
waits.lock.lock()
## Watch `places` for `watch_time`, and when a batch has room take the lock if it is free:
## whether it was taken. Only threads that see room try, so a call wanting one thread does
## not have every idle one queue on the lock.
func watch() -> bool:
let begun = time.now()
while true:
for _ in 0..<pauses:
if places.load(.acquire) > 0 and waits.lock.try_lock():
return true
thread.pause()
if time.since(begun) >= watch_time:
return false