Is there a need for an STM analogue in zig?

Brainstorming
1

https://github.com/user-attachments/files/22373415/Transactional_Locking.pdf

1 Like
2

It doesn’t explain in sufficient detail what it’s doing behind the scenes.
I need an example that shows the actual benefits,

My understanding is it tracks how data is accessed and schedules threads in a manner that avoids overlapping accesses?

I think this could be done with an implementation of the future std.Io interface, though it might require some API beyond what the interface will provide.

3

I skimmed over the text and (coming from a DB background) it sounds interesting. However, the still complicated usage, at least in C++, would prevent me from using it, even if I had a use case.

I think it doesn’t avoid overlapping access. Instead it detects conflicts and resolves them by rolling back and giving the callers a chance to retry.

Reminds me of optimistic locking in ORMs.

If I understand correctly, it promises better performance than locking when the number of threads is high and the probability of actually conflicting changes is low. This fits to the spirit of Zig somehow…

1 Like
4

Using STM for modular concurrency

1 Like
5

Answer to the title: yes. I don’t think it needs to be in the standard library (although I’m not opposed either), but Zig-the-language does precisely nothing to tame the complexity of multi-threaded parallel code.

Nor should it, but that means that writing correct parallel code is a matter of discipline. That’s not as scary as it sounds, or it shouldn’t be: using STM is an example of discipline, and “do everything through this API”, unlike “just get it all right lol, lmao”, is an actually-practical approach to correctness in this context.

So yeah, absolutely a nice STM library would be a great addition to the ecosystem.

Yes, yes, yes, and yes. This is all correct. Having a native ‘effectful’ async system with event-loop characteristics, will go a long way towards making the hard parts (like retries) easier, as @vulpesx points out.

For those who prefer to read, rather than watch video, the STM Wikipedia entry is both approachable, and has links to all the foundational papers on the subject (which are themselves well worth reading).

1 Like
6

If a transaction fails to commit, the STM will attempt to rerun it. This requires that the transaction cannot modify any non-STM variables. A transaction is a piece of code that can contain arbitrary function calls. These calls must also ensure that they do not modify any non-STM variables. Furthermore, no transaction can be run within a transaction (this is implemented in Haskell using the STM monad. Running transactions is done within I/O, and STM cannot contain I/O).

From Zig’s perspective, only language-level support for these behavioral checks can ensure the correctness of transaction code; any other approach cannot prevent users from writing incorrect code.

7

Indeed, that’s the part where the new monad-esque IO system can help.

Perhaps this could be asserted using a .Debug only mutex within the STM struct? Just brute force it.

Zig isn’t really about preventing users from writing incorrect code. It wants to help! But other values are more prominent.

However, if you have a solid idea of what that language-level support would look like, I’m curious to hear it. Especially if the feature(s) would be minimal, broadly applicable, and compatible with what we already have.

1 Like
8

Following the STM monad here, my simple idea is as follows:

  1. First, define a native type TVar(a), which represents the variable of STM. TVar has three operations:
    newTVar(T: type, val: T) TVar(T)
    readTVar(ref: TVar(T)) T
    writerTVar(ref: TVar(T), T) void

  2. STM code blocks are allowed. TVar(a) operations can only occur within STM blocks. Non-TVar variables cannot be modified within STM blocks. STM blocks may be retried and allowed to execute multiple times until successful. Function calls can be made within STM blocks, but both the called and the function must meet the above requirements.

  3. There is an atomically function that runs the STM block. The STM block cannot be executed by itself and can only be executed by the atomically function.

// TVar()
// STMBlock
// atomically(STMBlock) STMBlock return type{}

fn foo() void {
    tv1: TVar(i32) = atomically({//STM block
        newTVar(i32, i);
    });
    tv2: TVar(i32) = atomically({//STM block
        newTVar(i32, i);
    });

    k1 = atomically({//STM block
        v1 = readTVar(tv1);
        writerTVar(tv2, v1 + 1);
    });

    atomically(bar(tv1, tv2));

}

fn bar(tv1: TVar(i32), tv2: TVar(i32)) i32 {//STM block
    v1 = readTVar(tv1);
    v2 = readTVar(tv2);
    const res = v1 + v2
    //The retry operation can only be performed in the STM block. 
    //It will block the thread until changes occur in tv1 and tv2. 
    //The thread is awakened and the transaction is retried.
    if(res > 100) retry();  

    writerTVar(tv1, res);
    return res;
}
1 Like
9

Seems plausible.

Zig doesn’t have blocks, of course, but it does allow the construction of context objects. Could that be made to suffice?

10

Could you provide some concrete example code?

In my example, STMBlock == STM monad. I’m not sure how context objects achieve this.

11

Context object like:

pub const StmBlock = struct {
   ctx: *anyopaque,
   atom_fn: *const fn(*StmBlock) StmBlock,

   pub fn atomically(self: StmBlock) StmBlock {
        return self.atom_fn(self.ctx);
    }
};

That’s just the barest possible sketch, but it’s what I meant. atomically would have to handle everything except the provided atomic function, which gets an opaque pointer to any state it needs, and whatever else you decide that the interface requires.