Towards Efficient Implementation of Concurrent Hash Tables and Search Trees Based on Software Transactional Memory
Alexey A. Paznikov, V.A. Smirnov, A.R. Omelnichenko · 2019 International Multi-Conference on Industrial Engineering and Modern Technologies (FarEastCon) · 2019
Algorithms using software transactional memory for implementing thread-safe associative arrays (a red-black tree, a hash table with open addressing based on the Hopscotch method hashing collision resolution) are proposed. The analysis of the efficiency of associative arrays with different number of involved threads and processor cores is given, comparison with data structures based on coarse-grained and fine-grained locks is given, algorithm selection recommendations for performing transactions are also formulated. The basics of software transaction memory, various policies for updating objects in memory and strategies for conflict detection are described. Various locking methods for using transactional memory implemented in the GCC 5.4.0 compiler are presented. The alternatives currently in use are briefly considered, advantages and disadvantages are also highlighted.