Asynchronized Concurrency: The Secret to Scaling Concurrent Search Data Structures

We introduce “asynchronized concurrency (ASCY), ” a paradigm consisting of four complementary programming patterns. ASCY calls for the design of concurrent search data structures (CSDSs) to resemble that of their sequen-tial counterparts. We argue that ASCY leads to implemen-tations which are portably scalable: they scale across differ-ent types of hardware platforms, including single and multi-socket ones, for various classes of workloads, such as read-only and read-write, and according to different performance metrics, including throughput, latency, and energy. We sub-stantiate our thesis through the most exhaustive evaluation of CSDSs to date, involving 6 platforms, 22 state-of-the-art CSDS algorithms, 10 re-engineered state-of-the-art CSDS algorithms following the ASCY patterns, and 2 new CSDS algorithms designed with ASCY in mind. We observe up to 30 % improvements in throughput in the re-engineered algo-rithms, while our new algorithms out-perform the state-of-the-art alternatives