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 Sep 2016

Fingerprint

Garbage Collection
Prolog
Table
Atoms
Runtime Systems
Swap
Bottles
Concurrent
Servers
Server
Derivatives
Real-time
Derivative

Keywords

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

Cite this

@article{f44232faddb84b7aa7237bf52d151970,
title = "Lock-free atom garbage collection for multithreaded Prolog",
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.",
keywords = "atom, atom garbage collection, hash table, lock-free, symbol table",
author = "Jan Wielemaker and Keri Harris",
year = "2016",
month = "9",
day = "1",
doi = "10.1017/S1471068416000272",
language = "English",
volume = "16",
pages = "950--965",
journal = "Theory and practice of logic programming",
issn = "1471-0684",
publisher = "Cambridge University Press",
number = "5-6",

}

Lock-free atom garbage collection for multithreaded Prolog. / Wielemaker, Jan; Harris, Keri.

In: Theory and practice of logic programming, Vol. 16, No. 5-6, 01.09.2016, p. 950-965.

Research output: Contribution to JournalArticleAcademicpeer-review

TY - JOUR

T1 - Lock-free atom garbage collection for multithreaded Prolog

AU - Wielemaker, Jan

AU - Harris, Keri

PY - 2016/9/1

Y1 - 2016/9/1

N2 - 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.

AB - 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.

KW - atom

KW - atom garbage collection

KW - hash table

KW - lock-free

KW - symbol table

UR - http://www.scopus.com/inward/record.url?scp=84991509186&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84991509186&partnerID=8YFLogxK

U2 - 10.1017/S1471068416000272

DO - 10.1017/S1471068416000272

M3 - Article

VL - 16

SP - 950

EP - 965

JO - Theory and practice of logic programming

JF - Theory and practice of logic programming

SN - 1471-0684

IS - 5-6

ER -