[ANN] kcas and kcas_data 0.2.4 for lock-free concurrent programming

Ecosystem
1

I’m happy to announce that the kcas package now has a kcas_data companion package that provides implementations of compositional lock-free data structures implemented using kcas.

What is kcas?

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

On top of the efficient multi-word compare-and-set algorithm, kcas provides compositional transactional programming interfaces that can make it much easier to implement concurrent algorithms.

The first version of the new kcas_data package includes domain safe Hashtbl, Queue, and Stack data structures that all mimic the corresponding Stdlib module interfaces and can more or less be used as drop-in replacements when domain safety is needed.

The kcas_data data structures also provide transactional interfaces that allow one to compose new lock-free operations with any other kcas based transactions. For example, given a queue and a stack one can atomically take an element from the queue and push it to the stack using a transaction written in direct style via explicit transaction log passing as follows:

let tx ~xt =
  match Queue.Xt.take_opt ~xt queue with
  | None -> ()
  | Some value ->
    Stack.Xt.push ~xt stack value
in
Xt.commit { tx }

Aside from offering composability, the provided data structures should give good performance and scalability compared to protecting all accesses of unsynchronized Stdlib data structures using locks.

Feel free to give the new kcas_data package a spin!

I would also like to encourage people to try and implement more compositional lock-free data structures using kcas. It is fairly straightforward to translate textbook imperative data structures using kcas to make them domain safe and lock-free and the project README comes with many examples.

Note that while the kcas_data package is currently in the kcas repository, it might later be moved to be a part of the repository that is currently called lockfree.

18 Likes