Anzeige
Erschienen in:
2014 | OriginalPaper | Buchkapitel
On the Correctness and Efficiency of Lock-Free Expandable Tries for Tabled Logic Programs
verfasst von : Miguel Areias, Ricardo Rocha
Erschienen in: Practical Aspects of Declarative Languages
Verlag: Springer International Publishing
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.