Vesa Karvonen polytypic

How can one understand and predict the performance of multicore algorithms?

As a first step, I'd recommend acquiring a basic understanding of the MSI protocol. Modern systems use somewhat more complex protocols, but a basic understanding of MSI should be enough to predict the most important phenomena.

Below is an even further simplified model of shared memory based on the MSI protocol. While the model is not precise, and makes several simplifications not based on actual hardware, it should be accurate enough to predict many

Extending k-CAS with efficient read-only CMP operations

The kcas library currently uses the GKMZ algorithm for Efficient Multi-word Compare and Swap or MCAS aka k-CAS. This is a nearly optimal algorithm for MCAS as it requires only k + 1 CAS operations.

The new library API also provides a transactional API for using the algorithm. For example, suppose one would create the following shared memory locations:

title
k-CAS for sweat-free concurrent programming

k-CAS for sweat-free concurrent programming

Vesa Karvonen

A generalized approach to turn a functional data structure into a lock-free starvation avoiding data structure

Any functional data structure can be turned into a lock-free data structure by wrapping it inside an Atomic. For example, consider the following set implementation:

module Identity_set : sig
  type 'a t
  val empty : 'a t

A pattern for using GADTs to subset cases

Consider the following straightforward mutable queue implementation using two stacks:

type 'a adt_queue = {
  mutable head : 'a head;
  mutable tail : 'a tail;
}

For a long time OCaml has supported lightweight threads exposed via the Thread module. These threads are often called “systhreads”, but I will simply call them “threads” in this post.

The OCaml Stdlib also provides many mutable data structures such as Hashtbl, Queue, and Stack. As the documentation alerts, none of these are thread-safe.

Currently OCaml 5 provides a Domain.DLS module for domain-local storage.

Unfortunately,

there is no corresponding Thread.TLS for (sys)thread-local storage, and
the current implementation of Domain.DLS is not thread-safe.

A lock-free starvation avoiding bag

module type Bag = sig
  type 'a t
  val create : unit -> 'a t
  val to_list : 'a t -> 'a list
  type 'a handle
  val add : 'a t -> 'a -> 'a handle
  val remove : 'a t -> 'a handle -> unit

	// This is a very brief and incomplete sketch of how the technique used in
	//
	// Effectful OCaml with Objects and Variants
	// https://github.com/polytypic/rea-ml#effectful-ocaml-with-objects-and-variants
	//
	// could be translated to F#. The following F# will likely make more sense after
	// reading the introduction that you'll find by following the above link.

	[<AutoOpen>]
	module Rea =

	(* Copyright (c) 2023 Vesa Karvonen

	Permission to use, copy, modify, and/or distribute this software for any
	purpose with or without fee is hereby granted, provided that the above
	copyright notice and this permission notice appear in all copies.

	THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH
	REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
	AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT,
	INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM