A Simple and Efficient Lock-Free Hash Trie Design for Concurrent Tabling

ABSTRACT. A critical component in the design of a concurrent tabling system is the implementation of the table space. One of the most successful data structure for representing tables is based on a two-level trie data structure, where one trie level stores the tabled subgoal calls and the other stores the computed answers. In the previous work, we have presented a sophisticated lock-free design where both levels of the tries where shared among threads in a concurrent environment. To implement lock-freedom we used the CAS atomic instruction that nowadays can be widely found on many common architectures. The CAS reduces the granularity of the synchronization when threads access concurrent areas. However, different concurrent areas can interfere with each other on strong memory hardware architectures, creating problems such as false sharing or cache memory ping pong effects. In this work, we present a simpler and efficient lock-design design based on hash tries that minimizes these problems by dispersing as much as possible the concurrent areas. 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 previous designs.