Lock-free atom garbage collection for multithreaded Prolog. Issue 5 (14th October 2016)

• Record Type: Journal Article
• Authors: WIELEMAKER, JAN; HARRIS, KERI
• Editors: Carro, Manuel; King, Andy
• Is Part Of: Theory and practice of logic programming. Volume 16:Issue 5/6(2016)
• Page Start: 950
• Page End: 965
• Publication Date: 2016-10-14
• Subjects: atom, -- symbol table, -- atom garbage collection, -- lock-free, -- hash table; Logic programming -- Periodicals; Artificial intelligence -- Computer programs -- Periodicals; Constraint programming (Computer science) -- Periodicals; 005.115
• DOI: 10.1017/S1471068416000272
• Languages: English
• ISSNs: 1471-0684

Abstract

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.