kprotty

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

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

const std = @import("std");

kprotty

API

const Coherency = enum {
  // writes have defined order across threads, reads observe some write
  atomic,
  // happens atomically, but writes dont need to have a defined order across threads
  unordered,
  // need not be atomic: on data-race, produces an unspecified value instead of UB
  racy,
  // not atomic. data-race is UB

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

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 M = 12; // Probability scale for rANS state. Symbol frequencies in this log range. Usually 8-12.
const L = 23; // Renormalization factor to control dumping rANS state to bitstream. From rans_byte.h.
const m_min = 8 - 2 - (std.math.divCeil(u32, M, 4) catch unreachable); // Small-size-opt limit when compressing frequencies.
const m_max = [_]u16{m_min, m_min+16, m_min+16+256, m_min+16+256+4096, 1<<M}; // Size ranges for frequencies after small size limit.

fn compress(dst: anytype, src: []const u8) !void {
    // Histogram for the frequency of each byte in input.
    var hist = [_]u32{0} ** 256;
    for (src) |byte| hist[byte] += 1;

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

const std = @import("std");
const assert = std.debug.assert;
const log = std.log.scoped(.lsm_manifest_fuzz);

const vsr = @import("../vsr.zig");
const constants = @import("../constants.zig");
const stdx = @import("../stdx.zig");
const fuzz = @import("../testing/fuzz.zig");
const allocator = fuzz.allocator;
const snapshot_latest = @import("tree.zig").snapshot_latest;

kprotty

#include <cstdint>
#include <cstddef>
#include <cstring>
#include <cassert>
#include <x86intrin.h>

typedef struct {
    __m256i state[2];
    __m256i counter;
    __m256i output;

kprotty

type Event:
    wait()
    set()

type Link:
    get(ptr: Ptr):
        if LOAD(ptr, Acquire) |value|:
            return value
        
        e = Event{}