[ANN] Major updates to kcas in 0.1.8 and 0.2.0

Community
,
1

I’m happy to announce that the kcas library has received major updates.

What is kcas?

kcas provides an implementation of atomic lock-free multi-word
compare-and-swap (MCAS), which is a powerful tool for designing concurrent
algorithms.

First, kcas now uses a new lock-free algorithm that improves performance of kcas significantly over the previously used algorithm. The new algorithm is provided in kcas version 0.1.8 with an API compatible with previous versions of kcas.

Second, the latest version of kcas, 0.2.0, went through a major API redesign. The same functionality as can be found in previous versions is now available through cleaned-up modules. Additionally, the latest library offers a new transactional API, essentially a basic form of STM or Software Transactional Memory, that can make it significantly easier to program lock-free algorithms.

Third, documentation has also been overhauled and there is now both an introduction to the use of the library as well as a reference manual.

So, click here, check out the new documentation, the new transactional API, and enjoy the performance!

Last, there is still more to come. There are plans to extend the range of the library further via a brand-new algorithm and extended support for transactions.

10 Likes
3

Looking at your kcas examples, I see that transactions are in monadic style:

let pop_front q =
  Tx.(
    get q.front >>= function
    | x :: xs -> set q.front xs >>. x
    | [] -> (
        q.back |> get_as List.rev >>= function
        | [] -> forget
        | x :: xs -> set q.back [] >> set q.front xs >>. x))

But in the code the monad is just a “state” monad for a log. In OCaml, manually using the state monad is syntactically heavy and unpleasant, but it can be reformulated as a reader monad on a mutable data structure:

let pop_front ~log q =
  let open Tx in
  match get ~log q.front with
  | x :: xs -> set ~log q.front xs; x
  | [] ->
    match q.back |> get_as ~log List.rev with
    | [] -> forget ~log
    | x :: xs -> set ~log q.back []; set ~log q.front xs; x

Have you considered this?

Now that log is mutable (instead of a persistent value as in the current implementation), you sometimes need to explicitly copy it for backtracking purpose. In particular Tx has a

try_in op
  (fun exn -> ...)
  (fun res -> ...)

operation that can be rewritten in direct style as

let old_log = copy log in
match op with
| exception exn -> let log = old_log in ...
| res -> ...

(This is a bit more verbose and error-prone if you know that resetting the log on error is always the right default, but it also suggests that this approach gives more control to users and may require less built-in combinators, simplifying the overall design.)

3 Likes
5

(Note: I used log inspired by the code but this could be just tx or tx_state or tx_ctx, what have you.)
There is a risk of users deliberately “leaking” the log and reusing it in improper ways, but the API would not encourage you to do this. I think that the benefits in convenience would vastly outweigh this cost in practice.

I also wonder whether there might be some way to avoid the monadic clutter altogether.

My proposal doesn’t have any monadic clutter.

Oleg’s approach still uses combinators (you build terms in a computation DSL), so (this is more expressive in general but) the convenience cost is sensibly higher than passing a parameter around.

1 Like