אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

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.