Current status and potential improvements

[Sudha247]

I had a go at analysing the current status and potential improvements that can be made on the lockfree library. I'm summarising them below:

Kcas dependency

• Since there isn't any necessity for multi-word compare and swap in the existing structures, all kcas usage can be replaced with Atomic module. Remove Kcas dependency #5 attempts to do this.
• It also has a new exponential-backoff implementation done with Domain.Sync.cpu_relax instead of using the one in kcas that usesDomain.Sync.wait_for.
  • The hard coded numbers in the backoff implementation could use some more experimentation to validate if they are good enough for most cases.
  • cpu_relax works for only some architectures, so backoff might need an alternative in others.

Tests

• The testsuite currently has some tests, which may be useful as benchmarks but may not be useful for assessing correctness of the operations provided by the APIs. It might be useful to add some correctness tests for the data structures with both single-domain and multi-domain scenarios. A good starting point for this would be ocaml/ocaml standard library tests and JDK java.util.Concurrent module's tests.

Benchmarks

• A set of sequential and parallel benchmarks have been proposed in Lockfree benchmarks ocaml-bench/sandmark#194.
  • Performance: Performance numbers of the structures in multicore scenario needs more investigation. In particular, the expectations on scaling need to be set by profiling and referring to benchmarks of the same structures in other languages and ecosystems such as Java/C++/.NET. To find false sharing of cache lines, perf c2c could come in handy, here's a nice article about it.
  • Read/Write operations: The benchmarks only do read or write based on Random probability. They could also use some explicit producer-consumer cases, like (N/2) produecers and (N/2) consumers, 1 producer and (N-1) consumers, where N is the number of domains.
  • Parameters: The sandmark numbers only convey time and speedup. A better way to measure the throughput could be in terms of time taken for one million transactions, similar to how it is reported in lockfree literature in general.

[Sudha247]

Closing this issue as saturn has progressed quite a bit and other issues in the issue tracker capture the current status well.