Yet Another Lock-Free Atom Table Design for Scalable Symbol Management in Prolog
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 YAP Prolog 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
@Article{moreno-ijpp24, author = {P. Moreno and M. Areias and R. Rocha and V. Santos Costa}}, title = {{Yet Another Lock-Free Atom Table Design for Scalable Symbol Management in Prolog}}, journal = {International Journal of Parallel Programming}, isbn = {1573-7640}, pages = {--}, volume = {--}, number = {--}, month = {March}, year = {2024}, }
Download Paper
PDF fileSpringer