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.