kprotty

modification order:

• atomic vars are an array of writes, each write tagged if its Release + tagged if its rmw
• reads to it return some write in the array, each read tagged if its Acquire or not
• an rmw, atomically, pushes a write and returns the previous last-write as a read. So it can be tagged both Acquire (for the read part) & Release (for the write part)

coherence:

• each thread could be reading from different points in a given atomic-var write-array
• in each thread, a read never goes backwards i.e. read a[1]; read a[0] is invalid, but 1; 1 or 1; 2 is fine
• different read points also means threads could see writes to multiple arrays happen in different orders e.g. T1 does a.push(x); b.push(y) but T2 could see b's push before seeing a's push (T2's a-cursor hasnt updated yet)

kprotty

Currently, the std.Io interface isn't too optimizable:

1. All forms of concurrent execution goes through io.async/asynConcurrent(f) and io.await which can't be statically aware of when .await will be called, so it must dynamically allocate the context needed to run f.
2. The main api for blocking/unblocking on an arbitrary state is through Mutex & Condvar which require locking a mutex to wait (& wake correctly) + restrict implementors to only a usize with a biased representation for each state.
3. It ties cancellation to the task/concurrency model instead of to blocking operations (which are really the ones getting cancelled); To cancel a set of operations, they must be wrapped in a new spawned Future. It's also unclear, due to the racy nature of io.cancel, if a blocking operation consumes the stored cancellation request, or if it persists & causes all future blocking ops in that Future to return Cancelled.

I've thought of some ideas on how to address these + the all-encompassing nature of th

kprotty

// zig 0.15.2
// `zig run t.zig -OReleaseFast`

// NOTE: change this
//
// const Updater = Batched;
const Updater = Serial;

const std = @import("std");

kprotty

const std = @import("std");

fn writeExtended(w: *std.Io.Writer, value: u32) !void {
    const num_max_bytes = value / 0xff;
    try w.splatByteAll(0xff, num_max_bytes);
    try w.writeByte(@intCast(value - (num_max_bytes * 0xff)));
}

fn readExtended(r: *std.Io.Reader) !u32 {
    var value: u32 = 0;

kprotty

partial ordering: time/events are related to each other as graphs of dependencies
total ordering: time/events are related to each other as a sequence of steps

atomic op: op which is observed to either happen fully or not at all (no in-between)
atomic variable: memory location which atomic ops happen to
data race: non-atomic ops from 2+ threads on same memory location where one op is a write

load: an atomic read to observe a value
store: an atomic write to publish a value
read-modify-write (rmw): a read, updating the value, then a write, all atomically

kprotty

1. Every atomic object has a timeline (TL) of writes:

   • A write is either a store or a read-modify-write (RMW): it read latest write & pushed new one.
   • A write is either tagged Relaxed, Release, or SeqCst.
   • A read observes some write on the timeline:
     • On the same thread, future reads can't go backwards on the timeline.
     • A read is either tagged Relaxed, Acquire, or SeqCst.
     • RMWs can also be tagged Acquire (or AcqRel). If so, the Acquire refers to the "read" portion of "RMW".

2. Each thread has its own view of the world:

• Shared write timelines but each thread could be reading at different points.

kprotty

const std = @import("std");
const builtin = @import("builtin");

pub fn main() !void {
    try bench(struct {
        pub const name = "FAA";

        pub fn inc(counter: *std.atomic.Value(usize), current: usize, rng: *u32) usize {
            _ = rng;
            _ = current;

kprotty

pub fn ParkingLot(comptime Config: type) type {
    return struct {
        pub const Lock: type = Config.Lock;

        pub const Event: type = Config.Event;

        pub const nanotime: fn() u64 = switch (@hasDecl(Config, "nanotime")) {
            true => Config.nanotime,

kprotty

// Bit-vector + rand shuffle order scheduler

const std = @import("std");
const Allocator = std.mem.Allocator;

const workload_size = 1 << 20;
const n_workloads = 4;
const repetition = 4;
const use_async = true;
const use_manual_prefetch = true;

kprotty

const std = @import("std");

const Channel = struct {
    value: u32 = undefined,
    frame: anyframe,
};

fn generate(out_channel: **Channel) void {
    var ch = Channel{ .frame = @frame() };
    suspend out_channel.* = &ch;