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

• Type: Article in International Scientific Journal
• Date: 2024

Authors

Moreno, P (Author) Other; Miguel Areias (Author) FCUP; Ricardo Rocha (Author) FCUP; Costa, VS (Author) FCUP

Journal

Title: International Journal of Parallel Programming

Vol. 52

Pages: 187-206

ISSN: 0885-7458

Publisher: Springer Nature

Indexing

ISI Web of Knowledge - 1 Citation

Scopus - 1 Citation

Scientific classification

CORDIS: Technological sciences > Engineering > Computer engineering

FOS: Natural sciences > Computer and information sciences

Other information

Authenticus ID: P-010-5J0

DOI: 10.1007/s10766-024-00766-z

Abstract (EN): 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.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 20