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}, }