Milestone

To get started, we first implemented a basic thread-unsafe version of our skip list using C++ and
constructed a workload to test its correctness by comparing its result with std::map. On top
of this basic code, we have successfully completed two locking versions of our skip list, that is,
the global locking version and the fine-grained per-pointer locking version, based on algorithms
introduced by Pugh [1]. In addition, a workload has been built to empirically evaluate the
correctness of our locking implementations. On the 8-core GHC machine, We first spawned 8
threads to concurrently insert 215 consecutive integers to the skip list. Then a large outer loop
will iterate on the range of 1 to 215. During each iteration, an intense inner loop is executed
by the 8 threads, each of which performs high-contention operations on its assigned position
by continuously get, erase, and insert to the position a fixed number of times. After this,
we will examine the value of each of the 215 integers and finally, erase all numbers in the skip
list concurrently. Using this empirical workload, we found that even the most subtle bug and
deadlock can be exposed within less than two runs of the test.

For our fine-grained locking version, lazy deletion is employed when erasing a key-value pair in
case that some other threads are still accessing the deleted node. Similar to [1], we let the next
pointer of the deleted node point to its previous node to ensure that other threads accessing the
deleted node can still make progress. This method, however, imposes a challenge for garbage
collection because unlike other programming languages such as Java, C++ has no GC features.
Fortunately, we found an open-source C++ garbage collector called Boehm Garbage Collector.
In the constructor of our fine-grained locking skip list, we first allocate the header node using
GC MALLOC UNCOLLECTABLE primitive, indicating that the header is not garbage-collectable but
can be treated as the root of other memory allocations. This means that the garbage collector
will scan the header and track other memory locations referenced by pointers inside of the
header. Then in the insert function, we allocate a new node by using GC MALLOC primitive,
which indicates that the node is garbage-collectable as long as no other pointer is referencing to
it. By doing garbage collections, we ensure the correctness of our fine-grained locking version
during erase operations, while preventing the program from memory leakage.