{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,19]],"date-time":"2026-04-19T08:07:15Z","timestamp":1776586035851,"version":"3.51.2"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2017,5,10]],"date-time":"2017-05-10T00:00:00Z","timestamp":1494374400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000038","name":"NSERC","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2017,12,15]]},"abstract":"<jats:p>\n            We attempt to determine the best order and search algorithm to store\n            <jats:italic>n<\/jats:italic>\n            comparable data items in an array,\n            <jats:italic>A<\/jats:italic>\n            , of length\n            <jats:italic>n<\/jats:italic>\n            so we can, for any query value,\n            <jats:italic>x<\/jats:italic>\n            , quickly find the smallest value in\n            <jats:italic>A<\/jats:italic>\n            that is greater than or equal to\n            <jats:italic>x<\/jats:italic>\n            . In particular, we consider the important case where there are many such queries to the same array,\n            <jats:italic>A<\/jats:italic>\n            , which resides entirely in RAM. In addition to the obvious sorted order\/binary search combination we consider the Eytzinger breadth-first-search (BFS) layout normally used for heaps, an implicit B-tree layout that generalizes the Eytzinger layout, and the van Emde Boas layout commonly used in the cache-oblivious algorithms literature.\n          <\/jats:p>\n          <jats:p>\n            After extensive testing and tuning on a wide variety of modern hardware, we arrive at the conclusion that, for small values of\n            <jats:italic>n<\/jats:italic>\n            , sorted order, combined with a good implementation of binary search, is best. For larger values of\n            <jats:italic>n<\/jats:italic>\n            , we arrive at the surprising conclusion that the Eytzinger layout is usually the fastest. The latter conclusion is unexpected and goes counter to earlier experimental work by Brodal, Fagerberg, and Jacob (SODA 2003), who concluded that both the B-tree and van Emde Boas layouts were faster than the Eytzinger layout for large values of\n            <jats:italic>n<\/jats:italic>\n            . Our fastest C++ implementations, when compiled, use conditional moves to avoid branch mispredictions and prefetching to reduce cache latency.\n          <\/jats:p>","DOI":"10.1145\/3053370","type":"journal-article","created":{"date-parts":[[2017,5,10]],"date-time":"2017-05-10T18:08:53Z","timestamp":1494439733000},"page":"1-39","source":"Crossref","is-referenced-by-count":22,"title":["Array Layouts for Comparison-Based Searching"],"prefix":"10.1145","volume":"22","author":[{"given":"Paul-Virak","family":"Khuong","sequence":"first","affiliation":[{"name":"AppNexus, New York"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pat","family":"Morin","sequence":"additional","affiliation":[{"name":"Carleton University, Ottawa, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,5,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"key":"e_1_2_1_2_1","volume-title":"Top-down skiplists. CoRR abs\/1407.7917","author":"Barba Luis","year":"2014","unstructured":"Luis Barba and Pat Morin . 2014. Top-down skiplists. CoRR abs\/1407.7917 ( 2014 ). http:\/\/arxiv.org\/abs\/1407.7917 Luis Barba and Pat Morin. 2014. Top-down skiplists. CoRR abs\/1407.7917 (2014). http:\/\/arxiv.org\/abs\/1407.7917"},{"key":"e_1_2_1_3_1","volume-title":"Intel Core i7 -- Nehalem Architecture Dive. bit-tech. Retrieved","year":"2008","unstructured":"bit-tech 2008. Intel Core i7 -- Nehalem Architecture Dive. bit-tech. Retrieved November 3, 2008 from http:\/\/www.bit-tech.net\/hardware\/cpus\/2008\/11\/03\/intel-core-i7-nehalem-architecture-dive\/. bit-tech 2008. Intel Core i7 -- Nehalem Architecture Dive. bit-tech. Retrieved November 3, 2008 from http:\/\/www.bit-tech.net\/hardware\/cpus\/2008\/11\/03\/intel-core-i7-nehalem-architecture-dive\/."},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms. David Eppstein (Ed.). ACM\/SIAM, 39--48","author":"Brodal Gerth St\u00f8lting","year":"2002","unstructured":"Gerth St\u00f8lting Brodal , Rolf Fagerberg , and Riko Jacob . 2002 . Cache oblivious search trees via binary trees of small height . In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms. David Eppstein (Ed.). ACM\/SIAM, 39--48 . Gerth St\u00f8lting Brodal, Rolf Fagerberg, and Riko Jacob. 2002. Cache oblivious search trees via binary trees of small height. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms. David Eppstein (Ed.). ACM\/SIAM, 39--48."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375688"},{"key":"e_1_2_1_6_1","volume-title":"\u201cEytzinger","author":"Eytzinger M.","unstructured":"M. Eytzinger . 1590. Thesaurus Principum Hac Aetate in Europa Viventium (Cologne). {In commentaries, \u201cEytzinger \u201d may appear in variant forms, including: Aitsingeri, Aitsingero, Aitsingerum , Eyzingern .} M. Eytzinger. 1590. Thesaurus Principum Hac Aetate in Europa Viventium (Cologne). {In commentaries, \u201cEytzinger\u201d may appear in variant forms, including: Aitsingeri, Aitsingero, Aitsingerum, Eyzingern.}"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/355588.365103"},{"key":"e_1_2_1_8_1","volume-title":"Retrieved","author":"Fog A.","year":"2014","unstructured":"A. Fog . 2014. Instruction Tables . Retrieved December 7, 2014 from http:\/\/www.agner.org\/optimize\/instruction_tables.pdf. A. Fog. 2014. Instruction Tables. Retrieved December 7, 2014 from http:\/\/www.agner.org\/optimize\/instruction_tables.pdf."},{"key":"e_1_2_1_9_1","volume-title":"Intel Developer Zone. Retrieved","author":"Hegde Ravi","year":"2008","unstructured":"Ravi Hegde . 2008 . Optimizing Application Performance on Intel Core Microarchitecture Using Hardware-Implemented Prefetchers . Intel Developer Zone. Retrieved October 28, 2008 from https:\/\/goo.gl\/X1gNta. Ravi Hegde. 2008. Optimizing Application Performance on Intel Core Microarchitecture Using Hardware-Implemented Prefetchers. Intel Developer Zone. Retrieved October 28, 2008 from https:\/\/goo.gl\/X1gNta."},{"key":"e_1_2_1_10_1","unstructured":"Intel. Intel Core i7-4790K Processor (8M Cache up to 4.40 GHz). Retrieved from http:\/\/ark.intel.com\/products\/80807\/Intel-Core-i7-4790K-Processor-8M-Cache-up-to-4_40-GHz.  Intel. Intel Core i7-4790K Processor (8M Cache up to 4.40 GHz). Retrieved from http:\/\/ark.intel.com\/products\/80807\/Intel-Core-i7-4790K-Processor-8M-Cache-up-to-4_40-GHz."},{"key":"e_1_2_1_11_1","unstructured":"Intel. 2016. System Programming Guide Part 2. Intel 64 and IA-32 Architectures Software Developers Manual Vol. 3B. Intel.  Intel. 2016. System Programming Guide Part 2. Intel 64 and IA-32 Architectures Software Developers Manual Vol. 3B. Intel."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/5684.5686"},{"key":"e_1_2_1_13_1","volume-title":"Paul Khuong: Some Lisp. Retrieved","author":"Khuong P.","year":"2012","unstructured":"P. Khuong . 2012 . Binary Search is a Pathological Case for Caches . Paul Khuong: Some Lisp. Retrieved July 30, 2012 from http:\/\/www.pvk.ca\/Blog\/2012\/07\/30\/binary-search-is-a-pathological-case-for-caches\/. P. Khuong. 2012. Binary Search is a Pathological Case for Caches. Paul Khuong: Some Lisp. Retrieved July 30, 2012 from http:\/\/www.pvk.ca\/Blog\/2012\/07\/30\/binary-search-is-a-pathological-case-for-caches\/."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807206"},{"key":"e_1_2_1_15_1","volume-title":"Sorting and Searching","author":"Knuth D.","unstructured":"D. Knuth . 1997. Sorting and Searching ( 2 nd ed.). The Art of Computer Programming, Vol . 3. Addison-Wesley . D. Knuth. 1997. Sorting and Searching (2nd ed.). The Art of Computer Programming, Vol. 3. Addison-Wesley.","edition":"2"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/235141.235145"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2003.1261383"},{"key":"e_1_2_1_18_1","volume-title":"Technical Report TR-06-06. University of Alberta Department of Computer Science.","author":"Niewiadomski R.","year":"2006","unstructured":"R. Niewiadomski and J. N. Amaral . 2006 . Chopping Up Trees to Improve Spatial Locality in Implicit k-Heaps. Technical Report TR-06-06. University of Alberta Department of Computer Science. R. Niewiadomski and J. N. Amaral. 2006. Chopping Up Trees to Improve Spatial Locality in Implicit k-Heaps. Technical Report TR-06-06. University of Alberta Department of Computer Science."},{"key":"e_1_2_1_19_1","volume-title":"Modern Microprocessors: A 90 Minute Guide! Retrieved","author":"Patterson J. R. C.","year":"2015","unstructured":"J. R. C. Patterson . 2015 . Modern Microprocessors: A 90 Minute Guide! Retrieved May 2015 from http:\/\/www.lighterra.com\/papers\/modernmicroprocessors\/. J. R. C. Patterson. 2015. Modern Microprocessors: A 90 Minute Guide! Retrieved May 2015 from http:\/\/www.lighterra.com\/papers\/modernmicroprocessors\/."},{"key":"e_1_2_1_20_1","volume-title":"Cache-Oblivious Algorithms. Master\u2019s thesis","author":"Prokop H.","unstructured":"H. Prokop . 1999. Cache-Oblivious Algorithms. Master\u2019s thesis . Massachusetts Institute of Technology . H. Prokop. 1999. Cache-Oblivious Algorithms. Master\u2019s thesis. Massachusetts Institute of Technology."},{"key":"e_1_2_1_21_1","volume-title":"VentureBeat. Retrieved","author":"Protalinksi E.","year":"2015","unstructured":"E. Protalinksi . 2015 . Google Chrome now has over 1 billion users . VentureBeat. Retrieved May 28, 2015 from http:\/\/venturebeat.com\/2015\/05\/28\/google-chrome-now-has-over-1-billion-users\/. E. Protalinksi. 2015. Google Chrome now has over 1 billion users. VentureBeat. Retrieved May 28, 2015 from http:\/\/venturebeat.com\/2015\/05\/28\/google-chrome-now-has-over-1-billion-users\/."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30140-0_69"},{"key":"e_1_2_1_23_1","volume-title":"Linux Kernel Newsgroup. Retrieved","author":"Torvalds L.","year":"2007","unstructured":"L. Torvalds . 2007. CMOV. Linux Kernel Newsgroup. Retrieved January 2007 from http:\/\/yarchive.net\/comp\/linux\/cmov.html. L. Torvalds. 2007. CMOV. Linux Kernel Newsgroup. Retrieved January 2007 from http:\/\/yarchive.net\/comp\/linux\/cmov.html."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2452376.2452380"},{"key":"e_1_2_1_25_1","volume-title":"The Free Encyclopedia.","year":"2015","unstructured":"Wikipedia. 2015. Find first set. Wikipedia , The Free Encyclopedia. ( 2015 ). Retrieved July 21, 2015 from https:\/\/en.wikipedia.org\/wiki\/Find_first_set. Wikipedia. 2015. Find first set. Wikipedia, The Free Encyclopedia. (2015). Retrieved July 21, 2015 from https:\/\/en.wikipedia.org\/wiki\/Find_first_set."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/512274.512284"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/123465.123475"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/285930.286004"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3053370","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3053370","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:03:35Z","timestamp":1750215815000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3053370"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,10]]},"references-count":28,"alternative-id":["10.1145\/3053370"],"URL":"https:\/\/doi.org\/10.1145\/3053370","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,5,10]]}}}