GreenBST: Energy-Efficient Concurrent Search Tree

Like other fundamental abstractions for energy-efficient computing, search trees need to support both high concurrency and fine-grained data locality. However, existing locality-aware search trees such as ones based on the van Emde Boas layout vEB-based trees, poorly support concurrent update operations while existing highly-concurrent search trees such as the non-blocking binary search trees do not consider data locality. We present GreenBST, a practical energy-efficient concurrent search tree that supports fine-grained data locality as vEB-based trees do, but unlike vEB-based trees, GreenBST supports high concurrency. GreenBST is a k-ary leaf-oriented tree of GNodes where each GNode is a fixed size tree-container with the van Emde Boas layout. As a result, GreenBST minimizes data transfer between memory levels while supporting highly concurrent update operations. Our experimental evaluation using the recent implementation of non-blocking binary search trees, highly concurrent B-trees, conventional vEB trees, as well as the portably scalable concurrent trees shows that GreenBST is efficient: its energy efficiency in operations/Joule and throughput in operations/second are upi¾źto 65i¾ź% and 69i¾ź% higher, respectively, than the other trees on a high performance computing HPC platform Intel Xeon, an embedded platform ARM, and an accelerator platform Intel Xeon Phi. The results also provide insights into how to develop energy-efficient data structures in general.