Suggestions for first-time contributors to k-CAS

[polytypic]

The kcas library currently lacks benchmarks, tests, and cool examples and those can also serve as a good way to understand k-CAS itself. The kcas_data library provides a few data structures, but there is plenty of room for more.

Here are some potential ideas:

• Using k-CAS, create examples of solutions to well known concurrency problems such as

  • The dining philosophers problem — an example already exists here

• Implement examples and benchmarks of lock-free data structures:

  • Stacks — simple list based stacks already exists (e.g. Stack); what about something using an array?
  • Queues — a few queue implementations already exist (e.g. Queue), but there are many ways to implement queues
  • Deques
  • Linked lists — a doubly linked list example already exists (e.g. Dllist); what about singly linked lists?
  • Skip lists
  • Binary search trees — there are many different ways to implement binary search trees
  • Maps and Sets — possibly using some binary search tree or skip list
  • Hash tables — a couple of hash table examples already exists (e.g. Hashtbl), but there is definitely room for more
  • Bags
  • Priority queues — there is an example of a leftist heap, but there are many other approaches to priority queues

  Note that with k-CAS it is possible to straighforwardly translate an imperative data-structure to a lock-free data-structure by using transactions.

• Use k-CAS to implement composable synchronization primitives (mutexes, condition variables, semaphores, barriers, ...) with the idea being that one can commit a transaction that e.g. simultaenously acquires multiple mutexes

• Use k-CAS e.g. with domainslib to parallelize algorithms that e.g. manipulate non-trivial data structures and are difficult to parallelize otherwise.

• Device tests / benchmarks / examples that perform particularly poorly, e.g.

  • example that performs poorly with the default commit ~mode:Mode.obstruction_free and significantly better with commit ~mode:Mode.lock_free, or
  • example that suffers from starvation.

[dangdennis]

I see there’s already a PR that uses ocurrent’s benchmark tools. Is this for certain?

I have an initial MVP here that uses hyperfine instead. https://github.com/dangdennis/kcas/pull/1

Thanks for the lib! I’ve always been curious how Haskell‘s STM worked but couldn’t ever understand the code much.

[polytypic]

Sorry for taking a long time to reply!

I see there’s already a PR that uses ocurrent’s benchmark tools. Is this for certain?

It is work in progress. The benchmarking infrastructure has not previously supported parallel benchmarks and I guess there is still work to do there. I will likely be taking over the integration work.

Currently there are some simple benchmarks developed while working on the library and I have indeed been using hyperfine to run those (you can see results of benchmark runs in various PRs, e.g. here is a recent one). It is very useful to have some benchmarks to check that changes do not cause obvious performance regressions and also to test whether potential improvements are as expected. The set of benchmarks is far from comprehensive, however.

For better or worse, I think that the most wanted kind of benchmarks would be benchmarks that compare performance of kcas and and kcas_data data structures against plain atomics, lock-free data structures, and lock based data structures. The goal being to understand what is the overhead / cost of the composability. Writing such comparative benchmarks tends to be difficult as it is easy to create biased benchmarks. Also, there currently isn't a really good lock implementation for OCaml — one that would be scheduler independent and friendly. There is work in progress towards that, however.