dymokomi/luce-std
Source of release 0.7.4
0.7.4 / tests / parallel / parallel.lucb
## The `parallel` module: every index runs once on a worker number below `workers()`, call
## after call; per-worker scratch needs no lock; the first error comes back; calls nest and
## run from several threads at once.
let test_failure: ErrorCode = ErrorCode.package(1)
## What the tests' items record: how often each index ran, and on which worker.
struct Tally:
var runs: (@u32)[4096]
var worker_limit: usize
var bad_worker: @bool
var fail_at: usize
func tally_item(context: void*, index: usize, worker: usize) -> !:
let tally = (Tally*)context
if worker >= tally.worker_limit:
tally.bad_worker.store(true)
if index == tally.fail_at:
error(test_failure, "item failed on purpose")
_ = tally.runs[index].add(1, .relaxed)
func tally_range(context: void*, first: usize, end: usize, worker: usize) -> !:
for index in first..<end:
try tally_item(context, index, worker)
func reset(tally: Tally*, worker_limit: usize):
for at: usize in 0..<4096:
tally.runs[at] = 0
tally.worker_limit = worker_limit
tally.bad_worker = false
tally.fail_at = 4096
func check_once(tally: Tally*, count: usize):
assert(not tally.bad_worker.load())
for at: usize in 0..<4096:
assert(tally.runs[at] == (1 if at < count else 0))
test "every index runs once, on a worker below workers()":
let tally = try new Tally in memory.heap
defer free(tally) in memory.heap
for threads in [(usize)0, 1, 3, 64]:
for count in [(usize)0, 1, 2, 7, 4096]:
reset(tally, workers(count, threads))
try for_each(count, (void*)tally, tally_item, threads = threads)
check_once(tally, count)
let processors = (usize)os.cpus()
let most = processors if processors < most_threads else most_threads
assert(workers(0) == 1 and workers(1000) == (most if most < 1000 else 1000))
assert(workers(5, 3) == (3 if most > 3 else most) and workers(2, 8) == (2 if most > 2 else most))
assert(workers(1, 0) == 1 and workers(1000, 1) == 1)
test "many calls in a row all run every index once":
warm()
let tally = try new Tally in memory.heap
defer free(tally) in memory.heap
for call: usize in 0..<2000:
let count = call % 67
reset(tally, workers(count))
try for_each(count, (void*)tally, tally_item)
check_once(tally, count)
test "ranges cover the count exactly":
let tally = try new Tally in memory.heap
defer free(tally) in memory.heap
for chunk in [(usize)1, 3, 64, 5000]:
for count in [(usize)0, 1, 63, 64, 65, 4096]:
reset(tally, workers(count // chunk + 1))
try for_each_range(count, chunk, (void*)tally, tally_range)
check_once(tally, count)
test "an item's error is returned and later items may be skipped":
let tally = try new Tally in memory.heap
defer free(tally) in memory.heap
for threads in [(usize)1, 4, 0]:
for fail_at in [(usize)0, 10, 4095]:
for _ in 0..<20:
reset(tally, workers(4096, threads))
tally.fail_at = fail_at
var caught = false
for_each(4096, (void*)tally, tally_item, threads = threads) catch failure:
assert(failure.code == test_failure and failure.message == "item failed on purpose")
caught = true
assert(caught and tally.runs[fail_at] == 0 and not tally.bad_worker.load())
if threads == 1:
# one thread takes the indices in order and stops at the failure
for at: usize in 0..<4096:
assert(tally.runs[at] == (1 if at < fail_at else 0))
## Per-worker scratch: plain sums no other thread touches, and a flag that catches two
## threads holding one worker number at once.
struct Scratch:
var sums: u64[256]
var busy: (@bool)[256]
var shared: @bool
func scratch_item(context: void*, index: usize, worker: usize) -> !:
let scratch = (Scratch*)context
if scratch.busy[worker].swap(true, .acquire):
scratch.shared.store(true)
scratch.sums[worker] += (u64)index
# long enough for other threads to be inside items too
var spin: u64 = 0
for step: u64 in 0..<(u64)(index % 200):
spin += step
scratch.sums[worker] += spin - spin
scratch.busy[worker].store(false, .release)
test "each worker number belongs to one thread for the whole call":
let scratch = try new Scratch in memory.heap
defer free(scratch) in memory.heap
for round: usize in 0..<200:
let count = 1 + round * 37 % 5000
for at: usize in 0..<256:
scratch.sums[at] = 0
try for_each(count, (void*)scratch, scratch_item)
assert(not scratch.shared.load())
var total: u64 = 0
for at: usize in 0..<256:
assert(at < workers(count) or scratch.sums[at] == 0)
total += scratch.sums[at]
assert(total == (u64)count * (u64)(count - 1) // 2)
## A call inside each item: every inner index of every outer item runs once.
struct Nest:
var depth: usize
var hits: @usize
var bad_worker: @bool
func nested_item(context: void*, index: usize, worker: usize) -> !:
_ = index
let nest = (Nest*)context
if worker >= workers(24):
nest.bad_worker.store(true)
if nest.depth == 0:
_ = nest.hits.add(1, .relaxed)
return
var inner = Nest(depth = nest.depth - 1)
try for_each(24, (void*)&inner, nested_item)
_ = nest.hits.add(inner.hits.load(.acquire), .relaxed)
if inner.bad_worker.load():
nest.bad_worker.store(true)
test "calls made inside items finish":
for _ in 0..<20:
var nest = Nest(depth = 2)
try for_each(24, (void*)&nest, nested_item)
assert(nest.hits.load(.acquire) == 24 * 24 * 24 and not nest.bad_worker.load())
## A thread making calls of its own while others do the same.
struct Caller:
var calls: usize
var failed: @bool
func calling_thread(raw: void*?):
let caller = (Caller*)(raw else return)
let tally = new Tally in memory.heap catch failure:
caller.failed.store(true)
return
defer free(tally) in memory.heap
for call: usize in 0..<caller.calls:
let count = (call * 131) % 4097
reset(tally, workers(count))
for_each(count, (void*)tally, tally_item) catch failure:
caller.failed.store(true)
return
if tally.bad_worker.load():
caller.failed.store(true)
for at: usize in 0..<4096:
if tally.runs[at] != (1 if at < count else 0):
caller.failed.store(true)
test "several threads call at once":
var callers: Caller[6]
var handles: thread.Handle[6]
for at: usize in 0..<6:
callers[at] = Caller(calls = 300)
handles[at] = try thread.spawn(calling_thread, (void*)&callers[at])
for at: usize in 0..<6:
try handles[at].join()
assert(not callers[at].failed.load())
## Jobs: `start` returns at once, `wait` collects every index once and the first error,
## and jobs run beside calls, nest them, and start jobs of their own.
test "a started job runs every index once, under worker numbers below workers()":
let tally = try new Tally in memory.heap
defer free(tally) in memory.heap
for threads in [(usize)0, 1, 3]:
for count in [(usize)0, 1, 2, 7, 4096]:
reset(tally, workers(count, threads))
var job = try start(count, (void*)tally, tally_item, threads = threads)
try job.wait()
check_once(tally, count)
assert(job.completed() and job.progress() == count)
# a second wait does nothing
try job.wait()
test "a polled job completes, and its progress reaches its count":
let tally = try new Tally in memory.heap
defer free(tally) in memory.heap
for _ in 0..<50:
reset(tally, workers(4096))
var job = try start(4096, (void*)tally, tally_item)
var seen: usize = 0
while not job.completed():
let now = job.progress()
assert(now >= seen and now <= 4096)
seen = now
thread.yield()
assert(job.progress() == 4096)
try job.wait()
check_once(tally, 4096)
test "a job's first error comes back from wait":
let tally = try new Tally in memory.heap
defer free(tally) in memory.heap
for threads in [(usize)1, 4, 0]:
for fail_at in [(usize)0, 10, 4095]:
for poll in [false, true]:
reset(tally, workers(4096, threads))
tally.fail_at = fail_at
var job = try start(4096, (void*)tally, tally_item, threads = threads)
if poll:
while not job.completed():
thread.yield()
var caught = false
job.wait() catch failure:
assert(failure.code == test_failure and failure.message == "item failed on purpose")
caught = true
assert(caught and tally.runs[fail_at] == 0 and not tally.bad_worker.load())
test "many jobs run at once and are waited in any order":
let tallies = try new Tally[24] --- in memory.heap
defer free(tallies) in memory.heap
var jobs: Job[24]
for round: usize in 0..<10:
for at: usize in 0..<24:
let count = 1 + (at * 977 + round * 31) % 4096
reset(&tallies[at], workers(count))
jobs[at] = try start(count, (void*)&tallies[at], tally_item)
for back: usize in 0..<24:
let at = 23 - back if round % 2 == 0 else back
try jobs[at].wait()
check_once(&tallies[at], 1 + (at * 977 + round * 31) % 4096)
## Items slow enough that a job is still running while the caller makes calls of its own.
struct Slow:
var tally: Tally
var sums: (@u64)[256]
func slow_item(context: void*, index: usize, worker: usize) -> !:
let slow = (Slow*)context
var x: u64 = (u64)index + 1
for _ in 0..<20000:
x = (x * 31 + 7) % 1000003
_ = slow.sums[worker].add(x, .relaxed)
try tally_item((void*)&slow.tally, index, worker)
test "a job runs beside calls made while it runs":
let slow = try new Slow in memory.heap
defer free(slow) in memory.heap
let tally = try new Tally in memory.heap
defer free(tally) in memory.heap
for _ in 0..<3:
reset(&slow.tally, workers(2048))
var job = try start(2048, (void*)slow, slow_item)
var calls: usize = 0
while not job.completed() or calls < 20:
let count = 1 + calls * 131 % 4096
reset(tally, workers(count))
try for_each(count, (void*)tally, tally_item)
check_once(tally, count)
calls += 1
try job.wait()
check_once(&slow.tally, 2048)
test "calls made inside a job's items finish":
for _ in 0..<10:
var nest = Nest(depth = 2)
var job = try start(24, (void*)&nest, nested_item)
try job.wait()
assert(nest.hits.load(.acquire) == 24 * 24 * 24 and not nest.bad_worker.load())
## A job whose items start jobs of their own: half wait for theirs at once, half poll it
## first, which must not hang even when every pool thread is on the outer job.
struct Starter:
var hits: @usize
func inner_item(context: void*, index: usize, worker: usize) -> !:
_ = index
_ = worker
_ = ((Starter*)context).hits.add(1, .relaxed)
func starting_item(context: void*, index: usize, worker: usize) -> !:
_ = worker
var inner = try start(64, context, inner_item)
if index % 2 == 1:
while not inner.completed():
thread.yield()
try inner.wait()
test "a job's items start and wait for jobs of their own":
for threads in [(usize)0, 2]:
for _ in 0..<20:
var starter = Starter()
var job = try start(48, (void*)&starter, starting_item, threads = threads)
try job.wait()
assert(starter.hits.load(.acquire) == 48 * 64)