Yet Another Lock-Free Atom Table Design for Scalable Symbol Management in Prolog

Pedro Moreno, Miguel Areias, Ricardo Rocha and Vítor Santos Costa

2024

---

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},
  pages =     {--},
  volume =    {}, 
  number =    {},
  month =     {},
  year =      {2024},
  note =      {(First online: March 2024)},
}

Download Paper

PDF file
Springer