{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T14:59:19Z","timestamp":1725634759796},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2018,7]]},"abstract":"Database systems use many pointer-based data structures, including hash tables and B+-trees, which require extensive \"pointer-chasing.\" Each pointer dereference, e.g., during a hash probe or a B+-tree traversal, can result in a CPU cache miss, stalling the CPU. Recent work has shown that CPU stalls due to main memory accesses are a significant source of overhead, even for cache-conscious data structures, and has proposed techniques to reduce this overhead, by hiding memory-stall latency. In this work, we compare and contrast the state-of-the-art approaches to reduce CPU stalls due to cache misses for pointer-intensive data structures. We present an in-depth experimental evaluation and a detailed analysis using four popular data structures: hash table, binary search, Masstree, and Bw-tree. Our focus is on understanding the practicality of using coroutines to improve throughput of such data structures. The implementation, experiments, and analysis presented in this paper promote a deeper understanding of how to exploit coroutines-based approaches to build highly efficient systems.<\/jats:p>","DOI":"10.14778\/3236187.3236216","type":"journal-article","created":{"date-parts":[[2018,9,10]],"date-time":"2018-09-10T12:12:28Z","timestamp":1536581548000},"page":"1702-1714","source":"Crossref","is-referenced-by-count":31,"title":["Exploiting coroutines to attack the \"killer nanoseconds\""],"prefix":"10.14778","volume":"11","author":[{"given":"Christopher","family":"Jonathan","sequence":"first","affiliation":[{"name":"Microsoft Research"}]},{"given":"Umar Farooq","family":"Minhas","sequence":"additional","affiliation":[{"name":"Microsoft"}]},{"given":"James","family":"Hunter","sequence":"additional","affiliation":[{"name":"Microsoft"}]},{"given":"Justin","family":"Levandoski","sequence":"additional","affiliation":[{"name":"Microsoft"}]},{"given":"Gor","family":"Nishanov","sequence":"additional","affiliation":[{"name":"University of Minnesota"}]}],"member":"320","published-online":{"date-parts":[[2018,7]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"The Clang project. https:\/\/clang.llvm.org\/. The Clang project. https:\/\/clang.llvm.org\/."},{"key":"e_1_2_1_2_1","unstructured":"Coroutines ISO. https:\/\/www.iso.org\/standard\/73008.html. Coroutines ISO. https:\/\/www.iso.org\/standard\/73008.html."},{"key":"e_1_2_1_3_1","unstructured":"CppCoro. https:\/\/github.com\/lewissbaker\/cppcoro. CppCoro. https:\/\/github.com\/lewissbaker\/cppcoro."},{"key":"e_1_2_1_4_1","unstructured":"Fibers. https:\/\/msdn.microsoft.com\/en-us\/library\/ms682661.aspx. Fibers. https:\/\/msdn.microsoft.com\/en-us\/library\/ms682661.aspx."},{"key":"e_1_2_1_5_1","unstructured":"Intel 64 and IA-32 architectures optimization reference manual. https:\/\/software.intel.com\/sites\/default\/files\/managed\/9e\/bc\/64-ia-32-architectures-optimization-manual.pdf. Intel 64 and IA-32 architectures optimization reference manual. https:\/\/software.intel.com\/sites\/default\/files\/managed\/9e\/bc\/64-ia-32-architectures-optimization-manual.pdf."},{"key":"e_1_2_1_6_1","unstructured":"Microsoft Visual Studio. https:\/\/www.visualstudio.com\/. Microsoft Visual Studio. https:\/\/www.visualstudio.com\/."},{"key":"e_1_2_1_7_1","unstructured":"Programming languages---C++ extensions for coroutines. proposed draft technical specification ISO\/IEC DTS 22277 (e). http:\/\/www.open-std.org\/jtc1\/sc22\/wg21\/docs\/papers\/2017\/n4680.pdf. Programming languages---C++ extensions for coroutines. proposed draft technical specification ISO\/IEC DTS 22277 (e). http:\/\/www.open-std.org\/jtc1\/sc22\/wg21\/docs\/papers\/2017\/n4680.pdf."},{"key":"e_1_2_1_8_1","unstructured":"Redis. https:\/\/redis.io\/. Redis. https:\/\/redis.io\/."},{"key":"e_1_2_1_9_1","first-page":"266","volume-title":"PVLDB","author":"Ailamaki A.","year":"1999"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3187009.3164147"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3015146"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1272743.1272747"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/366663.366704"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463710"},{"key":"e_1_2_1_15_1","first-page":"2007","article-title":"What every programmer should know about memory","volume":"11","author":"Drepper U.","year":"2007","journal-title":"Red Hat, Inc"},{"key":"e_1_2_1_16_1","first-page":"371","article-title":"MemC3: Compact and concurrent MemCache with dumber caching and smarter hashing","volume":"13","author":"Fan B.","year":"2013","journal-title":"NSDI"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807206"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/2856318.2856321"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544834"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780000031"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2168836.2168855"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/3149193.3149202"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335449"},{"key":"e_1_2_1_24_1","volume-title":"FAST","author":"Rumble S. M.","year":"2014"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536222.2536251"},{"key":"e_1_2_1_26_1","volume-title":"IEEE Data Eng. Bull.","author":"Stonebraker M.","year":"2013"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3236187.3236216","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:42:57Z","timestamp":1672220577000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3236187.3236216"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7]]},"references-count":26,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2018,7]]}},"alternative-id":["10.14778\/3236187.3236216"],"URL":"https:\/\/doi.org\/10.14778\/3236187.3236216","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2018,7]]}}}