dymokomi/luce-geocore
Source of release 0.7.1
0.7.1 / src / core / parallel.lucb
## One persistent pool of worker threads for geometry kernels, the pattern of
## luce-canvas's engine pool: workers start once, on first use (one fewer than
## the processors, at most 63), and stay for the process, so kernels never
## spawn threads per call. `run` hands out `count` items and works on them too,
## so a batch finishes even when every worker is busy or it is started from
## inside another batch. `parallel_for` splits a range into chunks of about
## `grain` elements. Items are Base functions with a context pointer.
##
## On a worker each item runs in its own runtime context (entered before,
## finished after), so it may create ARC temporaries but must release all it
## creates and touch none of the caller's objects: only raw data crosses back.
## Items the caller runs share its context. A batch started inside an item on
## a worker runs inline there, in that item's context (an item's objects never
## reach another thread's context, and nesting never waits on a busy pool).
## Workers have deep stacks: B-rep tessellation runs whole faces as items.
import c
import os
import sync
import thread
import ownership
extern func getenv(name: c.str) -> c.str?
## The most workers the pool keeps.
let most_workers: usize = 63
let worker_stack: usize = 8 * 1024 * 1024
## Set on pool workers: items there enter their own runtime context.
local var on_worker: bool = false
## A batch of work: `count` items, each `entry(context, index)` once, on at
## most `limit` threads at a time. Owned by its caller, who must keep it
## until `wait` (or `run`) returns.
pub struct Job:
var entry: func(void*?, usize) -> unit = skip_item
var context: void*? = none
var count: usize = 0
## The next item to hand out, and how many have finished.
var next: @usize
var finished: @usize
## Pool workers on this batch now (under the lock), and the most allowed.
var working: usize = 0
var helpers: usize = 0
## Its place in the queue while it has items to hand out.
var queued: bool = false
var after: Job*? = none
func skip_item(context: void*?, index: usize):
_ = context
_ = index
## Batches with items still to hand out, oldest first; guarded by `lock`.
var lock: sync.Mutex
var work_ready: sync.Condition
var job_done: sync.Condition
var first_job: Job*? = none
var last_job: Job*? = none
var started: bool = false
var worker_count: usize = 0
## How many threads a batch can have at once: the pool's workers and the
## caller (1 inside an item on a worker, where batches run inline).
pub func width() -> usize:
if on_worker: return 1
lock.lock()
ensure_workers()
let count = worker_count
lock.unlock()
return count + 1
## Run `entry(context, index)` for every index in `0..<count` across the pool,
## this thread included, on at most `limit` threads (0: as many as there are),
## and return once all are done.
pub func run(count: usize, entry: func(void*?, usize) -> unit, context: void*?, limit: usize = 0):
if count == 0:
return
if count == 1 or limit == 1 or on_worker:
for index in 0..<count:
entry(context, index)
return
var job = Job()
# The caller is one of the `limit` threads.
enqueue(&job, count, entry, context, 0 if limit == 0 else limit - 1)
wait(&job)
## Start the workers now and return once every one is running. Allocation
## trackers (tests, benchmarks) install after this: a starting thread frees
## its start block in whatever memory.heap is current then.
pub func warm():
var barrier = Barrier(threads = width())
run(barrier.threads, meet, (void*)&barrier)
## Every thread of a batch holds one item until all of them do.
struct Barrier:
let threads: usize
var arrived: @usize
func meet(context: void*?, index: usize):
_ = index
let barrier = (Barrier*)(context else return)
_ = barrier.arrived.add(1, .acq_rel)
while barrier.arrived.load(.acquire) < barrier.threads: thread.yield()
## Put a batch out on the pool's workers alone (at most `limit`, 0: all of
## them) and return at once; `finished` tells when it is done and `wait`
## collects it. With no worker to be had it runs here before returning.
pub func start(job: Job*, count: usize, entry: func(void*?, usize) -> unit, context: void*?, limit: usize = 0):
if on_worker:
enqueue(job, 0, entry, context, limit)
job.count = count
job.next.store(count, .relaxed)
for index in 0..<count:
entry(context, index)
_ = job.finished.add(1, .acq_rel)
return
enqueue(job, count, entry, context, limit)
lock.lock()
let alone = worker_count == 0
lock.unlock()
if alone:
work_on(job)
## Whether every item of `job` has finished.
pub func finished(job: const Job*) -> bool:
return job.finished.load(.acquire) >= job.count
## How many of `job`'s items have finished (progress reports).
pub func completed(job: const Job*) -> usize:
return job.finished.load(.acquire)
## Work on `job`'s remaining items here, then wait until no worker holds it;
## after this the caller may free it.
pub func wait(job: Job*):
work_on(job)
lock.lock()
while job.finished.load(.acquire) < job.count or job.working > 0:
job_done.wait(&lock)
unlink(job)
lock.unlock()
func enqueue(job: Job*, count: usize, entry: func(void*?, usize) -> unit, context: void*?, helpers: usize):
job.entry = entry
job.context = context
job.count = count
job.next.store(0, .relaxed)
job.finished.store(0, .relaxed)
job.working = 0
job.after = none
lock.lock()
ensure_workers()
job.helpers = worker_count if helpers == 0 or helpers > worker_count else helpers
job.queued = count > 0 and job.helpers > 0
if job.queued:
if let last = last_job:
last.after = job
else:
first_job = job
last_job = job
work_ready.broadcast()
lock.unlock()
## Take `job`'s items until none are left to hand out.
func work_on(job: Job*):
while true:
let index = job.next.add(1, .relaxed)
if index >= job.count:
return
let entry = job.entry
if on_worker:
ownership.enter()
entry(job.context, index)
ownership.finish_task()
else:
entry(job.context, index)
_ = job.finished.add(1, .acq_rel)
## Drop `job` from the queue if it is there; under `lock`.
func unlink(job: Job*):
if not job.queued:
return
job.queued = false
var previous: Job*? = none
var cursor = first_job
while let current = cursor:
if current == job:
if let before = previous:
before.after = current.after
else:
first_job = current.after
if last_job == job:
last_job = previous
return
previous = cursor
cursor = current.after
## Start the workers the first time the pool is used; under `lock`.
func ensure_workers():
if started:
return
started = true
let processors = (usize)os.cpus()
let spare = processors - 1 if processors > 1 else 0
var wanted = most_workers if spare > most_workers else spare
# LUCE_POOL_WORKERS caps the pool (tests of small machines).
if let found = getenv("LUCE_POOL_WORKERS"):
let text = (u8*)found
var cap: usize = 0
var at: usize = 0
while text[at] >= 48 and text[at] <= 57 and at < 4:
cap = cap * 10 + (usize)(text[at] - 48)
at += 1
if at > 0 and cap < wanted: wanted = cap
for _ in 0..<wanted:
let handle = thread.spawn(worker_main, none, stack = worker_stack, name = "luce-pool") catch failure:
# Fewer workers only means less help: callers do the rest.
_ = failure
break
handle.detach()
worker_count += 1
## A queued batch with items left and room for one more worker; batches
## with nothing left to hand out leave the queue. Under `lock`.
func next_job() -> Job*?:
var cursor = first_job
while let job = cursor:
cursor = job.after
if job.next.load(.relaxed) >= job.count:
unlink(job)
continue
if job.working < job.helpers:
return job
return none
func worker_main(context: void*?):
_ = context
on_worker = true
lock.lock()
while true:
if let job = next_job():
job.working += 1
lock.unlock()
work_on(job)
lock.lock()
job.working -= 1
if job.working == 0:
job_done.broadcast()
else:
work_ready.wait(&lock)
struct Tally:
var hits: @usize
var seen: @u64
func count_item(context: void*?, index: usize):
let tally = (Tally*)(context else return)
_ = tally.hits.add(1, .relaxed)
_ = tally.seen.add((u64)1 << (u64)(index % 64), .relaxed)
func nested_item(context: void*?, index: usize):
_ = index
# Each item runs a batch of its own: every worker may be busy in the outer
# one, so the inner caller must be able to finish it alone.
run(8, count_item, context)
test "a batch runs every item once, across the pool and the caller":
var tally = Tally()
run(64, count_item, (void*)&tally)
assert(tally.hits.load(.acquire) == 64)
assert(tally.seen.load(.acquire) == 0xFFFFFFFFFFFFFFFF)
run(3, count_item, (void*)&tally, limit = 1)
assert(tally.hits.load(.acquire) == 67)
run(0, count_item, (void*)&tally)
assert(tally.hits.load(.acquire) == 67)
assert(width() >= 1)
test "batches started inside batches finish":
var tally = Tally()
run(32, nested_item, (void*)&tally, limit = 4)
assert(tally.hits.load(.acquire) == 256)
test "a background batch finishes and waits cleanly":
var tally = Tally()
var job = Job()
start(&job, 100, count_item, (void*)&tally, limit = 2)
wait(&job)
assert(finished(&job))
assert(tally.hits.load(.acquire) == 100)
# A job can be reused once collected.
start(&job, 5, count_item, (void*)&tally)
wait(&job)
assert(tally.hits.load(.acquire) == 105)
## A range split into chunks for `parallel_for`.
struct Chunks:
var body: func(void*?, usize, usize) -> unit = skip_range
var context: void*? = none
var count: usize = 0
var grain: usize = 1
func skip_range(context: void*?, first: usize, end: usize):
_ = context
_ = first
_ = end
func run_chunk(context: void*?, index: usize):
let chunks = (Chunks*)(context else return)
let first = index * chunks.grain
let end = first + chunks.grain if chunks.count - first > chunks.grain else chunks.count
let body = chunks.body
body(chunks.context, first, end)
## Call `body(context, first, end)` over `0..<count` in chunks of `grain`
## elements (at least one), across the pool and this thread, and return once
## every chunk is done. A range of one chunk runs here, with no handoff.
pub func parallel_for(count: usize, grain: usize, body: func(void*?, usize, usize) -> unit, context: void*?):
if count == 0:
return
let size = grain if grain > 0 else 1
if count <= size:
body(context, 0, count)
return
var chunks = Chunks(body = body, context = context, count = count, grain = size)
run((count + size - 1) // size, run_chunk, (void*)&chunks)
struct Sum:
var total: @usize
func add_range(context: void*?, first: usize, end: usize):
let sum = (Sum*)(context else return)
var part: usize = 0
for index in first..<end: part += index
_ = sum.total.add(part, .relaxed)
test "parallel_for covers the range once in chunks":
var sum = Sum()
parallel_for(100001, 1000, add_range, (void*)&sum)
assert(sum.total.load(.acquire) == 100001 * 100000 // 2)
parallel_for(0, 10, add_range, (void*)&sum)