Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-std

Source of release 0.7.2

0.7.2 / 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)