dymokomi/luce-canvas
Source of release 0.5.1
#==============================================================================================
#
# pool - One persistent, bounded set of worker threads for the whole engine
#
# DESCRIPTION:
# Decoding bands, packing tiles, rendering shapes and the like each used to start their
# own threads and join them per call. The pool starts its workers once, on first use
# (one fewer than the processors, at most 63), and keeps them for the process. A batch
# is `count` independent items `entry(context, index)`; `run` blocks with the calling
# thread working too, so a batch finishes even when every worker is busy or a batch
# is started from inside another one; `start` and `wait` put a batch out in the
# background and collect it later.
#
#==============================================================================================
import os
import sync
import thread
## The most workers the pool keeps.
let most_workers: usize = 63
## 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.
pub func width() -> usize:
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:
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)
## 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):
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
## 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
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
let wanted = most_workers if spare > most_workers else spare
for _ in 0..<wanted:
let handle = thread.spawn(worker_main, none, 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
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)