On the Correctness and Efficiency of Lock-Free Expandable Tries for Tabled Logic Programs
Miguel Areias and Ricardo Rocha
January 2014
Abstract
Tabling is an implementation technique that improves the
declarativeness and expressiveness of Prolog in dealing with recursion
and redundant sub-computations. A critical component in the
implementation of an efficient tabling framework is the design of the
data structures and algorithms to access and manipulate tabled
data. One of the most successful data structures for tabling is
tries. In previous work, our initial approach to deal with concurrent
table accesses, implemented on top of the Yap Prolog system, was to
use lock-based trie data structures. In this work, we propose a new
design based on lock-free data structures and, in particular, we focus
our discussion on the correctness and efficiency of extending Yap's
tabling framework to support lock-free expandable tries. Experimental
results show that our new lock-free design can effectively reduce the
execution time and scale better, when increasing the number of
threads, than the original lock-based design.
Bibtex
@InProceedings{areias-padl14,
author = {M. Areias and R. Rocha},
title = {{On the Correctness and Efficiency of Lock-Free Expandable Tries for
Tabled Logic Programs}},
booktitle = {Proceedings of the 16th International Symposium on Practical Aspects of Declarative
Languages (PADL 2014)},
pages = {168--183},
number = {8324},
series = {LNCS},
publisher = {Springer},
editor = {M. Flatt and Hai-Feng Guo},
month = {January},
year = {2014},
address = {San Diego, California, USA},
}
Download Paper
PDF file
Springer