Skip to content

Instantly share code, notes, and snippets.

Avatar
🤔
Fωμ±

Vesa Karvonen polytypic

🤔
Fωμ±
  • Helsinki, Finland
View GitHub Profile
@polytypic
polytypic / slides.md
Last active February 15, 2023 09:43
k-CAS for sweat-free concurrent programming
View slides.md
title
k-CAS for sweat-free concurrent programming

k-CAS for sweat-free concurrent programming

Vesa Karvonen

@polytypic
polytypic / gkmz-with-read-only-cmp-ops.md
Last active February 10, 2023 15:55
Extending k-CAS with efficient read-only CMP operations
View gkmz-with-read-only-cmp-ops.md

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:

@polytypic
polytypic / article-simplified-msi-model-of-shared-memory.md
Last active January 19, 2023 10:57
Simplified MSI model of shared memory
View article-simplified-msi-model-of-shared-memory.md

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

@polytypic
polytypic / Rea.fsx
Last active August 6, 2022 10:34
Effectful F# with Objects
View Rea.fsx
// 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 =
@polytypic
polytypic / .gitignore
Last active May 14, 2023 21:37
Recursive generator using C++20 coroutines
@polytypic
polytypic / Zio.fsx
Last active January 16, 2023 14:42
Zio like monad in F#
View Zio.fsx
// Computations with extensible environment, error handling, and asynchronicity
// I recently reviewed some F# code that turned out to be using
//
// Dependency Interpretation
// https://fsharpforfunandprofit.com/posts/dependencies-4/
//
// and got thinking about whether one could construct a usable Zio like monad
//
// https://zio.dev/
View ReDiSL.md

Learning day: ReDiSL

Logistics team held a "learning day" on Thursday 2021-03-04 where we could spend one full day on a project or tutorial of our choosing. I worked on a little proof-of-concept project I dubbed ReDiSL or Redis DSL. This is a little writeup on the topic.

The motivation for working on the Redis DSL or ReDiSL was that it could make for a nice way to work with Redis especially when one is doing

@polytypic
polytypic / Hoas.scala
Last active December 8, 2020 18:51
Curious case of GADTs in Scala
View Hoas.scala
// Below is a simple attempt at using GADTs in Scala based on
//
// https://github.com/palladin/idris-snippets/blob/master/src/HOAS.idr
object Hoas {
// With case classes one can directly write down what looks like a GADT:
sealed trait Expr[A]
final case class Val[A](value: A) extends Expr[A]
final case class Bin[A, B, C](bin: (A, B) => C, lhs: Expr[A], rhs: Expr[B])
extends Expr[C]
@polytypic
polytypic / amateurfunctor-optics.1ml
Last active April 2, 2018 13:26
Amateurfunctor optics in 1ML --- WORK-IN-PROGRESS!
View amateurfunctor-optics.1ml
;; Amateurfunctor optics in 1ML --- WORK-IN-PROGRESS!
;;
;; Background:
;;
;; https://people.mpi-sws.org/~rossberg/1ml/
;; http://r6.ca/blog/20120623T104901Z.html
;;
;; Run as:
;;
;; ./1ml prelude.1ml amateurfunctor-optics.1ml
@polytypic
polytypic / tiv.1ml
Last active November 18, 2019 07:20
Type indexed values in 1ML
View tiv.1ml
;; Type indexed values in 1ML
;;
;; This is a very simple experiment at encoding type-indexed values in 1ML.
;;
;; Background:
;;
;; https://people.mpi-sws.org/~rossberg/1ml/
;; http://repository.readscheme.org/ftp/papers/zheyang-icfp98.pdf
;;
;; Run as: