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 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.
Original language | English |
---|---|
Pages (from-to) | 950-965 |
Number of pages | 16 |
Journal | Theory and practice of logic programming |
Volume | 16 |
Issue number | 5-6 |
DOIs | |
Publication status | Published - 1 Sept 2016 |
Keywords
- atom
- atom garbage collection
- hash table
- lock-free
- symbol table