sponsored

Concurrency for Hash Tables

istock 456509949
istock/akindo

Hash tables, also known as unordered associative maps, are efficient data structures that should be discussed as part of any introductory data structures course or book.Given the importance of parallel programming these days, understanding how to have efficient concurrent use of our data structures is especially relevant.

Intel Threading Building Blocks (TBB) has been a key source for a highly concurrent hash table for this past decade. The TBB open source project’s home is https://www.threadingbuildingblocks.org.

Concurrency and Hash Tables

Like any data structure, when used with parallel programming we need to consider issues related to concurrent access. A simple solution with any data structure is to forbid concurrent access. This is done by having some form of mutual exclusion (usually done with a “lock,” commonly known as a “mutex”). The problem with mutual exclusion is that it tends to limit performance in a parallel program, because it leads to stalling if the data structure is heavily used. Therefore, we need something better than the simple solution.

Since hash tables often represent significant amounts of information in an application, they are used heavily enough to warrant consideration for efficient concurrent access.

Hardware vs. Software Solutions

Software solutions to give greater concurrency for hash tables make use of the fact that hash tables are generally quite large. This means the likelihood that concurrent uses actually touch the same part of a hash table is low. Instead of having mutual exclusion cover the entire hash table, it is possible to divide the hash table into smaller regions and lock only the affected region for a given update. With such a scheme, accesses from different threads can read or write different parts of a table concurrently. The potential for conflicts remains, but the occurrence of conflicts is greatly reduced with such a scheme.

More recently, research into transactional memory designs has encouraged support in hardware that can assist in these situations. Such support is also designed in anticipation that conflicts will occur in the context of a large data structure, such as hash table, but the occurrence of real collisions over accesses to the same memory locations will be minimal. About five years, ago, Intel introduced instructions known as Transactional Synchronization eXtensions (TSX).

Intel TBB implements hash tables, also known as unordered associative maps, which will use the appropriate combination of software and hardware support automatically based on the capabilities of the processor being used. This is done automatically when we use TBB.

Illustrating Concurrency in a Hash Table

Let’s consider a simple hash table. Hash tables are used to map a key to a key and value pair in linear time. Two key operations are add (insert) and lookup (retrieve). Resizing and deletion are two additional operations of general interest.

Consider the following illustrated example with five incoming requests (in parallel). If no concurrent operations were allowed, each of the five operations shown would have to occur one at a time.

5hashtables JamesReindeers

Five hash table operations requested

Considering this example, three of the operations have no collisions with the other operations. Note that one of the operations was a lookup (read). Reads never need to wait for reads, but they do need to wait for a write (such as an add) to complete so that information that is read is complete.

The two operations that map to the same hash table entry must not do their updates concurrently. Whatever type of mutual exclusion is utilized, the contention over the same memory will need to be detected and problems avoided by staggering their updates.

Hash Table Interfaces: Three Choices

TBB defines unordered associative containers that have strong support for concurrency while meeting all of the Container Requirements of the ISO C++ standard. The original TBB interfaces predate C++11, so it has a historical hash function which remains quite valuable and did not need to change to match the standard. TBB has also added unordered_map and unordered_multimap support to mirror the C++11 additions, with the interfaces augmented or adjusted only as needed to support concurrent access.  This table summarizes the pros/cons of the interfaces available with TBB:

comparison Reindeers

Free and Easy Download

Providing for high performance when using a hash table is as easy as downloading and using the free and open source Intel TBB. It is available from Intel’s free library download site.

Useful links for more information

·       Intel Performance Libraries – free library download site

·       TBB online documentation: concurrent_hash_map template class

·       TBB online documentation: Concurrent Containers

·       Intel Threading Building Blocks Open Source Project home page

·       Coarse-grained locks and Transactional Synchronization explained

·       Intel ISA extensions, (see the Intel® Architecture Instruction Set Extensions Programming Reference for more information on Transactional Synchronization eXtensions (TSX)).

Related:

Copyright © 2018 IDG Communications, Inc.