Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theoretical and Experimental Methods for Concurrent Search Trees
event speaker icon
Maya Arbel (Ph.D. Thesis Seminar)
event date icon
Monday, 10.07.2017, 11:00
event location icon
Taub 601
event speaker icon
Advisor: Prof. H. Attiya, Dr. A. Morrison
As core counts continue to rise in modern processors, it is increasingly important for applications to be scalable. Designing scalable concurrent software is notoriously difficult (even for experts), and programmers must rely on efficient concurrent library code to be effective. Concurrent binary search trees (BSTs) represent some of the most fundamental building blocks in such libraries, and are important in both theory and practice. This talk will briefly introduce two techniques for addressing limitations of the well-known read copy update (RCU) synchronization primitives. These techniques facilitate efficient implementation of searches and updates in BSTs. The talk will also present a high level overview of a new approach for adding range queries to concurrent BSTs. Experiments comparing our techniques with state of the art solutions revealed unexpected results. Some BST algorithms had drastically different performance in read-heavy workloads even though their traversals were implemented similarly. The main part of the talk is in-depth analysis of the performance of 11 concurrent BSTs to understand exactly why these performance differences arise. The analysis revealed that many of these differences can be attributed to pathological memory layouts, and the caching and prefetching effects of modern x86-64 processors rather than real algorithmic differences.