Lock-free atom garbage collection for multithreaded Prolog
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.
|SecuritEase, New Zealand|
|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