On the Implementation of a Lock-Free Atom Table in a Prolog System
Abstract
Prolog systems rely on an atom table for symbol management, which is usually implemented as a dynamically resizeable hash table. This is ideal for single threaded execution, but can become a bottleneck in a multi-threaded scenario. In this work, we replace the original atom table implementation in the Yet Another Prolog (YAP) system with a lock-free hash-based data structure, named Lock-free Hash Tries (LFHT), in order to provide efficient and scalable symbol management. Being lock-free, the new implementation also provides better guarantees, namely, immunity to priority inversion, to deadlocks and to livelocks. Performance results show that the new lock-free LFHT implementation has better results in single threaded execution and much better scalability than the original lock based dynamically resizing hash table.
Bibtex
@InProceedings{moreno-hlpp23,
author = {P. Moreno and M. Areias and R. Rocha and V. Santos Costa},
title = {{On the Implementation of a Lock-Free Atom Table in a Prolog System}},
booktitle = {Proceedings of the 16th International Symposium on High-level Parallel Programming and
Applications (HLPP 2023)},
pages = {--},
editor = {V. Niculescu and D. Bufnea and A. Sterca},
month = {June},
year = {2023},
address = {Cluj-Napoca, Romania},
}