Re-implementation of Lock-free Contention Adapting SearchTrees

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.

Content

Author and article information

Journal

Title: ScienceOpen Preprints

Publisher: ScienceOpen

Publication date (Electronic preprint): 1 April 2020

Affiliations

[1 ] University of Central Florida

Author information

Kevin Boyles https://orcid.org/0000-0002-1176-4562

Article

DOI: 10.14293/S2199-1006.1.SOR-.PPVIJDB.v1

SO-VID: 5a6536f5-a298-421a-9389-1d2de80cbdec

License:

This work has been published open access under Creative Commons Attribution License CC BY 4.0 , which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Conditions, terms of use and publishing policy can be found at www.scienceopen.com .

History

Date received : 1 April 2020

Data availability: The datasets generated during and/or analysed during the current study are available in the repository: https://github.com/kboyles8/lock-free-search-tree

ScienceOpen disciplines: Data structures & Algorithms

Keywords: lock-free,contention adaption,tree,MRLock,multi-core programming,treap,coarse-grained locking,memory management