Search

To explore multi-core programming, we re-implement the Lock Free Contention Adapting Search Tree. We follow the structure of the original, using immutable treaps as leaf nodes implemented with an array for better performance with memory caching. Memory leaks are prevented through preallocation of elements. We evaluate the performance of the LFCA tree and compare it to the previous MRLock version. The LFCA tree performs better in all cases with multiple threads.

This implementation is based on a publication by Gal Milman, Alex Kogan, Yossi Lev, Victor Luchangco, and Erez Petrank in 2018. [1] Titled BQ: A Lock-Free Queue with Batching, they describe the data structures functionality and correctness, along with the previous work it is based on. [1] All implementation details are from this paper unless otherwise stated. In this series of papers, we will be reimplementing and performance testing their data structure. This first paper covers an initial implementation involving no concurrency, using an MR Lock [2] to restrict threads access to the data structure. This ensures correctness as the operations on the queue are guaranteed to be mutually exclusive. Our source code is available here: ​ https://github.com/ClayDiGiorgio/ParallelTeam24

This paper describes an implementation of a lock-free queue that utilizes batching to increase performance by up to 16x over standard lock-free queues. We attempted to implement the design and algorithms from the original research paper BQ: A Lock-Free Queue with Batching and tried to reproduce similar functionality and performance. The original implementation of this data structure was done in C++, but we wanted to try and build this in Java so we could compare the results of how the data structure performs in two different languages.

We investigated the binary search tree data structure proposed in the publication, Efficient Lock-Free Binary Search Trees by Bapi Chatterjee, Nhan Nguyen and Philipas Tsigas. We will explore its correctness, progression factor, and the linearizability of its operations and report our findings. With a lock-free algorithm, software engineers will be able to use a thread-safe binary search tree that is capable of the many different operations that are normally available on a binary search tree. This includes the basic, primitive operations of Add(), Contains(), and Remove(), without the performance loss of using a binary search tree that uses object locking. An implementation of a binary search tree that uses locks to promote thread-safety takes a performance loss due to the threads waiting when another thread holds the lock and causing contention. The approach outlined in the aforementioned paper claims to have several key fundamental improvements over existing lock-free binary search tree algorithms. This implementation of the binary search tree eliminates contention in Contains() operations where, if a node was modified while a Contains() operation took place, the program would restart any current operation from the root of the tree. This happens because the thread can no longer reliably confide in the traversal of the tree and must restart its search. This is taxing to the performance of a binary search tree and an inefficient design can underperform a sequential implementation. Among other improvements, the authors of this paper claim that their algorithm is linearizable and has improved disjoint-access parallelism compared to similar existing algorithms.

In Scalable Lock-Free Vector with Combining [1], Walulya and Tsigas introduce the first implementation of a concurrent, lock-free vector that utilizes combining to increase performance. In our project, we implement this concurrent vector as described in [1] and describe our approach here. We also implement a concurrent vector utilizing a Software Transactional Memory library. We compare the performance of our two implementations to each other and to the authors performance evaluations.