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 =     {187-206},
  volume =    {52}, 
  number =    {3},
  month =     {June},
  year =      {2024},
}

Download Paper

PDF file
Springer