On the Implementation of a Lock-Free Atom Table in a Prolog System
Pedro Moreno, Miguel Areias, Ricardo Rocha and VĂtor Santos Costa
June 2023
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},
}
Download Paper
PDF file