README

This is the README file for the stacklock distribution.
stacklock is a library for a novel type of queue lock in Rust

  Copyright (C) 2017 Steven Stewart-Gallus

  Copying and distribution of this file, with or without modification,
  are permitted in any medium without royalty provided the copyright
  notice and this notice are preserved.

To make some code faster some people invented spin locks where instead
of delving into the OS threads spin on a memory location.  However,
this can be slow on manycore machines.  For improved performance the
CLH and MCS queue locks were invented.  Instead of one memory location
multiple are used.  This novel algorithm uses a similar idea but
instead uses a stack.

So far performance numbers are ok.  GLibc's mutexes are 2.7 times
slower.  The parking_lot crate is about 1.7 times faster.  A highly
tuned implementation of futexes similar to the implementation in
Ulrich Drepper's Futexes are Tricky is about the same in performance
but drastically falls in performance in very heavily contended
scenarios.  HLE locks are about 1.6 times faster.  Future work should bring HLE
performance improvements and try use some of parking_lot's ideas.

To investigate correctness of the algorithm two main methods are used.
First, a test-suite.  Second, a TLA+ approximation of the algorithm is
used to exhaustively check for correctness under a small number of
threads.  There are currently TLA+ specs for the stack lock algorithm
and the Futexes are Tricky futex algorithm but not one for the
combination of them both.

stacklock is licensed under the Apache License, Version 2.0 (the
"License"); you may not use stacklock except in compliance with
the License. You may obtain a copy of the License at

     http://www.apache.org/licenses/LICENSE-2.0

You should have received a copy of the Licence under the file COPYING
distributed with this program.

stacklock is free software.  See the file COPYING for copying conditions.