Efficient Lock-Free Removing and Compaction for the Cache-Trie Data Structure

Cache-tries improve the running time of conventional lock-free hash tries through the addition of a cache. The addition of this cache has been shown to improve the run time of lookup and insert operations from O(log n) to O(1) time.

Here, as described in the accompanying paper, a lock-free remove operation for cache-tries is implemented, both with and without compaction. In addition, a further optimization to the remove operation is presented, along with a performance evaluation comparing the novel implementations against three similar data structures.

The implementations presented here are written in Scala using the concurrent reactive programming framework Reactors.IO. Full details on installation as well as running the presented benchmarks are provided in the file artifact-doc.pdf, located at the root level of the artifact.

This artifact is provided as a tarball that can be decompressed using standard utilities.