THREAD-SAFE ASSOCIATIVE ARRAYS, BASED ON TRANSACTIONAL MEMORY

In this paper several algorithms of thread-safe associative arrays (red-black tree, a hash table with open addressing based on the method of Hopscotch hashing collision resolution) using software transactional memory are proposed. Efficiency analysis of associative arrays with different number of used threads and processor cores, comparison with similar data structures based on locks and recommendations for transaction making are described. Basic principles of software trans-actional memory, different object update politics, conflict detection strategies are introduced. Different lock methods using transactional memory in GCC 5.4.0 are presented. Alternatives used nowadays are reviewed, pros and cons are shown.

Authors: V. A. Smirnov, A. R. Omelnichenko, A. A. Paznikov

Direction: Informatics and Computer Technologies

Keywords: Transactional memory, thread-safe data structures, red-black tree, hash table, multi-threaded programming, synchronization multithreaded programs

---

View full article