This time Ph.D. student Ibrahim Umar will give a talk about DeltaTrees:
Ibrahim will talk about DeltaTree, a practical locality-aware concurrent search tree that integrates both locality-optimization techniques from vEB-based trees, and concurrency-optimization techniques from non-blocking and highly-concurrent search trees. As a result, DeltaTree minimizes data transfer from memory to CPU while supporting high concurrency.
DeltaTree is a k-ary leaf-oriented tree of DeltaNodes where each DeltaNode is a fixed size tree-container with the van Emde Boas layout.
Our experimental evaluation using the recent implementation of non-blocking binary search trees, highly concurrent B-trees, conventional vEB trees, as well as the concurrent AVL trees, red-black trees, and speculation friendly trees from the Synchrobench benchmark shows that DeltaTree are up to 140% faster than the other trees on commodity Intel high performance computing (HPC) platforms. On commodity ARM embedded platforms, DeltaTree are up to 100% faster than the other trees.