std/shard

A Shard is an owned window over part of a Vec. Splitting a buffer into disjoint shards lets several threads transform it in place, with no copies and no shared references.

A shard holds a pointer into the original buffer and a length, which is the same representation a mutable slice has in any other language. Milo gives it the type of an owned value, so the move checker decides who may touch each range and no lifetime has to be written down. The buffer is allocated once and is never copied and never split. What moves is the right to write a range.

parallelMap runs that whole cycle in one call and is what most uses want. shatter, windows and weld are the same cycle by hand, for when the workers must differ from each other.

Why this module exists

Milo has no stored references. A &T or &mut T exists only as a function parameter, never in a struct field, a Vec element, or a return value. That restriction is what keeps lifetimes out of the language: a reference that cannot outlive the call it was passed to needs no annotation to prove it, so there is nothing to name and nothing to thread through a signature.

Parallel transforms are where that restriction costs something. The standard move is to split a buffer into mutable slices and give one to each worker, which Rust spells split_at_mut. It works because the type system can state that the slices borrow one buffer over disjoint regions, and can check that claim. Milo cannot state it, and adding lifetimes so that it could would give back exactly what the restriction bought. That leaves copying a chunk per worker and stitching the copies together, and on a 20M-element buffer the copy costs more than the parallelism saves.

So this module divides the ownership instead of the borrow. shatter consumes the Vec and hands out windows, each an ordinary owned value that a worker receives by move like anything else. No reference crosses a thread because no reference exists, and the aliasing argument is the move checker that already shipped rather than a new rule to trust.

from "std/shard" import { Shard, shatter, parallelMap }

Quick start

from "std/shard" import { Shard, parallelMap }

fn double(w: Shard<f64>): Shard<f64> {
    for i in 0..w.len() {
        w.set(i, w.get(i) * 2.0)
    }
    return w
}

pub fn main(): i32 {
    let n = 16
    var data: Vec<f64> = Vec.withCapacity(n)
    for i in 0..n {
        data.push(1.0)
    }

    let out = parallelMap(data, 4, double)!    // divide, run on 4 threads, reassemble
    print(out[0].toString())
    return 0
}

data is moved into parallelMap and comes back transformed, in the same allocation. No element was copied and no reference crossed a thread.

f is a plain function rather than a closure because every worker needs its own copy: a capturing closure is moved into the first task and gone for the rest. Everything the work depends on therefore travels in the window, which is also what stops workers sharing anything. The ergonomics and the safety property are the same choice.

Why this is safe

The three things that make it safe are all rules Milo already had:

• shatter consumes the Vec. After it there is no binding through which the buffer can be reached except the windows. Touching the original is error: use of moved variable.
• The windows are disjoint by construction. Window i covers exactly [i*chunk, (i+1)*chunk), computed inside windows(), never supplied by you.
• Shard is @noCopy. Handing the same window to two workers is a compile error, not a race. A struct of a pointer and three integers would otherwise be Copy, and a copyable window would make the race representable again.

So the aliasing argument is the move checker that already shipped. Nothing new had to be proven.

The escape hatch

shatter / windows / weld are public and supported, but they are not the path you should be on by default, and the compiler will say so:

warning: this shatters and welds by hand
  hint: 'parallelMap(v, workers, f)' is the same cycle in one call, and the form in
        which weld cannot fail — nothing between making the windows and welding them
        is your code.

Reach for them when the workers need to differ from each other, or when you want the windows for something other than one task each:

from "std/shard" import { Shard, shatter }

pub fn main(): i32 {
    var data: Vec<i64> = Vec.withCapacity(4)
    data.push(1)
    data.push(2)

    var owner = shatter(data, 2)
    var windows = owner.windows()
    // ... hand each window to a worker by move, collect them back ...
    let out = owner.weld(windows)!
    print(out.len.toString())
    return 0
}

The one obligation (on the manual path only)

Keep the owner alive until weld. A window is a pointer into the owner's buffer, so dropping the owner while a worker still holds one is a use-after-free that nothing here catches.

weld checks what it can: every window must carry this shatter's identity and the set must cover the buffer exactly. A missing window means some worker may still be holding a pointer, so weld refuses rather than handing the Vec back.

windows() hands its set out once, and a second call aborts naming the double call. A second set would be a second batch of pointers into the same storage, which is the alias this design exists to prevent; and since windows() only borrows the owner, a refusal would have nothing to give back and the caller nothing to do with it.

A refusal does not cost you the buffer. weld consumes both the owner and the windows, so an error that was only a message would destroy the very thing this module exists to avoid copying. Instead it returns a WeldRejected<T> holding the owner (shards), the windows exactly as you handed them in (returned), a reason you can branch on and the index of the offending window. Fix the set and weld again.

var data: Vec<i64> = Vec.withCapacity(4)
data.push(1)
data.push(2)
var owner = shatter(data, 2)
var windows = owner.windows()
let held = windows.pop()!

match owner.weld(windows) {
    Result.Ok(v) => {
        print("welded " + v.len.toString())
    }
    Result.Err(rej) => {
        // Deterministic: a window is missing, or came from another shatter.
        print(rej.message())
        // Nothing was lost. Put the missing window back and weld again.
        var again = rej.shards
        var back = rej.returned
        back.push(held)
        print("welded " + again.weld(back)!.len.toString())
    }
}

That is a runtime check, not a proof, and it is the honest residue of the manual path.

reason is a WeldReason: Foreign, NotCovered, CountMismatch, or NoWorkers. An owner that never handed a window out has no windows to weld, so it gets the buffer back with reclaim() instead. That is how parallelMapWith refuses an empty states without eating the Vec it was already given:

from "std/shard" import { Shard, parallelMapWith }

pub struct Tally { n: i64 }

fn shade(w: Shard<f64>, t: &mut Tally): Shard<f64> {
    t.n = t.n + 1
    return w
}

pub fn main(): i32 {
    var pixels: Vec<f64> = Vec.filled(64, 0.5)
    var noStates: Vec<Tally> = Vec.new()
    match parallelMapWith(pixels, 16, noStates, shade) {
        Result.Ok(m) => {
            print(m.data.len.toString())
        }
        Result.Err(rej) => {
            var idle = rej.shards
            let recovered = idle.reclaim()!
            print("no workers, and the buffer came home: " + recovered.len.toString())
        }
    }
    return 0
}

The reading side refuses the same way, with a StrWeldRejected that carries the string home.

parallelMap does not have that residue. It creates every window, hands out every window, awaits all of them and welds them itself, so no caller code can drop one or let the owner die first: the completeness weld checks is guaranteed by the shape of the call rather than verified after the fact. That is the same guarantee Rust's scoped threads get from lifetimes, reached here by closing the cycle inside one function. Use parallelMap unless you have a reason not to. See how Milo compares to Rust.

What it costs

Measured on a 10-core machine, 20M f64, a[i] = a[i] * 1.0000001 + 0.5, 4 workers, --release:

	time	peak memory
sequential, in place	6 ms	153.9 MiB
shatter/weld, 4 workers	3 ms	163.0 MiB
C, pthreads over one shared buffer	3 ms	154.0 MiB

Reproduce with sh benchmarks/shard/run.sh.

Read the time column loosely: this loop is memory-bandwidth-bound, so at 20M elements every row lands somewhere in 3-7 ms run to run and four workers buy less than four times anything. The memory column is the stable number and it is the one being claimed here.

What it actually buys on more cores

The table above measures the absence of a copy, not speedup. For speedup you need work per element high enough that the memory bus is not the limit. sh benchmarks/shard/scale.sh, 2M f64 with 200 rounds of arithmetic each, on a 10-core M-series:

workers	time	speedup
1	292 ms	1.00x
2	146 ms	2.00x
4	82 ms	3.56x
8	60 ms	4.87x
10	58 ms	5.03x

Linear to 2, close to it at 4, then flattening as the efficiency cores take a share.

Equal-sized windows are not equal-work windows. examples/graphics/mandelbrotParallel.milo renders the Mandelbrot set, where a pixel inside the set costs the full iteration budget and one outside escapes almost at once. With one window per core the worker holding the black interior is still grinding while the rest sit idle:

windows	time
1	108 ms
4	57 ms
8	36 ms
16	26 ms
64	19 ms

It keeps improving well past the core count, because smaller units even out the finishing times. The caveat is that parallelMap spawns one OS thread per window, so 64 windows is 64 threads on a ten-core machine. parallelMapWith below fixes the worker count and queues the windows instead.

The point is the memory column. The copying approach this replaces roughly doubles peak memory; shatter/weld adds a flat 9.1 MiB, which is the worker stacks and is the same fixed cost at 40M elements. As a percentage that is 5.9% at 20M and 3.0% at 40M.

Build the Vec with Vec.withCapacity if you know the size. Growing one by pushing peaks at roughly 2.7x the final size during the doubling reallocs, which dwarfs anything this module does.

Uneven work and per-worker state

parallelMap cannot express two things: more windows than workers, and state that belongs to one worker. parallelMapWith adds both:

from "std/shard" import { Shard, parallelMapWith }

pub struct Env { scale: f64, sum: f64 }

fn scale(w: Shard<f64>, e: &mut Env): Shard<f64> {
    for i in 0..w.len() {
        let x = w.get(i) * e.scale
        w.set(i, x)
        e.sum = e.sum + x
    }
    return w
}

pub fn main(): i32 {
    var data: Vec<f64> = Vec.filled(1000, 1.0)
    var envs: Vec<Env> = Vec.new()
    for k in 0..4 {
        envs.push(Env { scale: 2.0, sum: 0.0 })
    }
    let r = parallelMapWith(data, 16, envs, scale)!   // 16 windows, 4 workers
    var total: f64 = 0.0
    for e in r.states { total = total + e.sum }
    print(total.toString())                           // 2000
    return 0
}

states.len is the worker count and the windows go into a queue the workers pull from, so a worker that drew a cheap window pulls another while one that drew the expensive window keeps grinding. On 2M elements where the first quarter costs 40x the rest, 10 workers: parallelMap 34 ms, 40 pooled windows 19 ms. Reproduce with benchmarks/shard/shard_balance.milo.

The environments are the answer to "why must f be a plain function". A closure cannot be copied to N workers, so whatever it would have captured travels as an explicit owned value instead: each worker moves one S in, threads it through every window it processes, and hands it back through r.states, in the order the environments were given. Configuration rides in, accumulators ride out, and an S is on exactly one thread at a time, which is the same move-checker argument the windows use.

That makes reduction a recipe rather than a primitive: put the accumulator in S, leave the window unchanged, and merge r.states sequentially when they come home.

One rule: pooling makes the worker/window assignment scheduling-dependent, so state you read back must not encode which worker got which window. Per-worker tallies that merge into totals are deterministic; "worker 0 saw window 5" is not.

Scanning a string

parallelMap is map-shaped: a Vec<T> goes in and a Vec<T> comes back. A scan is a different shape — it reads and returns counts, offsets, or whatever you accumulate — so there is no one-call form for it, and shatterStr is the supported way to divide a string across workers rather than an escape hatch.

Because nothing writes, its windows may overlap: windows(needle.len - 1) finds a match straddling a boundary without a second pass over the seams. Count only matches that BEGIN inside a window's own range, which is w.ownLen(), the window's length before the overlap was added. Ask it rather than recomputing total / count: the last window takes the remainder of an uneven division, so the derived figure is wrong for exactly one window and the miscount is silent.

weld on this side asks for the same completeness the writing side does: every window it handed out must come back exactly once, by index, and must carry this shatter's identity. What it does not ask is that the windows cover the bytes disjointly, because overlapping ranges share bytes by design and a coverage-of-bytes test would reject the recommended usage.

Read-only does not exempt it from that check. The owner is the only thing keeping the string alive, so handing it back while a window is still out lets you mutate or drop a buffer a live StrShard still points into. Overlap is sound because reads do not race; a dangling read is not sound at all. A refusal returns a StrWeldRejected holding the string's owner (shards), the windows as you handed them in (returned), a reason and an index, so fixing the set costs nothing. An owner that never called windows() has nothing outstanding and gets its string back with reclaim().

See benchmarks/strscan/ for the worked example: 51.3 MiB, 35 ms sequential against 10 ms on eight windows, with the runner failing if any windowing disagrees with the sequential count.

Not for shared state

This divides data. It is not a concurrent map and not a substitute for a lock: two workers that need to touch the same element are outside what ownership can separate. Channels and atomics remain the answer there.