Lock-free atom garbage collection for multithreaded Prolog

DOI10.1017/S1471068416000272zbMATH Open1379.68086arXiv1608.00989MaRDI QIDQ4593072FDOQ4593072

Publication date: 9 November 2017

Published in: Theory and Practice of Logic Programming (Search for Journal in Brave)

Abstract: The runtime system of dynamic languages such as Prolog or Lisp and their derivatives contain a symbol table, in Prolog often called the atom table. A simple dynamically resizing hash-table used to be an adequate way to implement this table. As Prolog becomes fashionable for 24x7 server processes we need to deal with atom garbage collection and concurrent access to the atom table. Classical lock-based implementations to ensure consistency of the atom table scale poorly and a stop-the-world approach to implement atom garbage collection quickly becomes a bottle-neck, making Prolog unsuitable for soft real-time applications. In this article we describe a novel implementation for the atom table using lock-free techniques where the atom-table remains accessible even during atom garbage collection. Relying only on CAS (Compare And Swap) and not on external libraries, the implementation is straightforward and portable. Under consideration for acceptance in TPLP.

Full work available at URL: https://arxiv.org/abs/1608.00989

Recommendations

zbMATH Keywords

atom lock-free hash table symbol table atom garbage collection

Mathematics Subject Classification ID

Logic programming (68N17)

Cites Work

Logic Programming

Cited In (2)

This page was built for publication: Lock-free atom garbage collection for multithreaded Prolog

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4593072)