2016-09-01
Lock-free atom garbage collection for multithreaded Prolog
Publication
Publication
Theory and Practice of Logic Programming , Volume 16 - Issue 5-6
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 24 × 7 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.
Additional Metadata | |
---|---|
SecuritEase, New Zealand | |
doi.org/10.1017/S1471068416000272 | |
Theory and Practice of Logic Programming | |
International Conference on Logic Programming | |
Organisation | Human-Centered Data Analytics |
Wielemaker, J., & Harris, K. (Keri). (2016). Lock-free atom garbage collection for multithreaded Prolog. Theory and Practice of Logic Programming, 16(5-6). doi:10.1017/S1471068416000272 |