Lock-free atom garbage collection for multithreaded Prolog

Jan Wielemaker, Keri Harris

Research output: Contribution to JournalArticleAcademicpeer-review

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 languageEnglish
Pages (from-to)950-965
Number of pages16
JournalTheory and practice of logic programming
Volume16
Issue number5-6
DOIs
Publication statusPublished - 1 Sept 2016

Keywords

  • atom
  • atom garbage collection
  • hash table
  • lock-free
  • symbol table

Fingerprint

Dive into the research topics of 'Lock-free atom garbage collection for multithreaded Prolog'. Together they form a unique fingerprint.

Cite this