Monthly Archives: March 2016

A scalable lock-free hash table with open addressing

A scalable lock-free hash table with open addressing

  • Jesper Puge Nielsen and Sven Karlsson. A scalable lock-free hash table with open addressing. In Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP 2016), pages 33:1-33:2, New York, NY, USA, 2016. ACM. doi:10.1145/2851141.2851196
    [BibTeX] [Abstract]

    Concurrent data structures synchronized with locks do not scale well with the number of threads. As more scalable alternatives, concurrent data structures and algorithms based on widely available, however advanced, atomic operations have been proposed. These data structures allow for correct and concurrent operations without any locks. In this paper, we present a new fully lock-free open addressed hash table with a simpler design than prior published work. We split hash table insertions into two atomic phases: first inserting a value ignoring other concurrent operations, then in the second phase resolve any duplicate or conflicting values. Our hash table has a constant and low memory usage that is less than existing lock-free hash tables at a fill level of 33\% and above. The hash table exhibits good cache locality. Compared to prior art, our hash table results in 16\% and 15\% fewer L1 and L2 cache misses respectively, leading to 21\% fewer memory stall cycles. Our experiments show that our hash table scales close to linearly with the number of threads and outperforms, in throughput, other lock-free hash tables by 19\%.

    @InProceedings{2016-03-NIELSEN,
    title = {{A scalable lock-free hash table with open addressing}},
    author = {Jesper Puge Nielsen and Sven Karlsson},
    booktitle = {{Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP 2016)}},
    date = {2016-03-12/2016-03-16},
    year = {2016},
    pages = {33:1-33:2},
    doi = {10.1145/2851141.2851196},
    date = {2016},
    publisher = {ACM},
    address = {New York, NY, USA},
    abstract = {Concurrent data structures synchronized with locks do not scale well with the number of threads. As more scalable alternatives, concurrent data structures and algorithms based on widely available, however advanced, atomic operations have been proposed. These data structures allow for correct and concurrent operations without any locks. In this paper, we present a new fully lock-free open addressed hash table with a simpler design than prior published work. We split hash table insertions into two atomic phases: first inserting a value ignoring other concurrent operations, then in the second phase resolve any duplicate or conflicting values.
    Our hash table has a constant and low memory usage that is less than existing lock-free hash tables at a fill level of 33\% and above. The hash table exhibits good cache locality. Compared to prior art, our hash table results in 16\% and 15\% fewer L1 and L2 cache misses respectively, leading to 21\% fewer memory stall cycles. Our experiments show that our hash table scales close to linearly with the number of threads and outperforms, in throughput, other lock-free hash tables by 19\%.}
    }

Posted in Dissemination | Leave a comment