[{"date_published":"2020-02-19T00:00:00Z","type":"conference","date_updated":"2024-02-28T12:53:46Z","citation":{"ieee":"N. Koval, M. Sokolova, A. Fedorov, D.-A. Alistarh, and D. Tsitelov, “Testing concurrency on the JVM with Lincheck,” in <i>Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP</i>, San Diego, CA, United States, 2020, pp. 423–424.","chicago":"Koval, Nikita, Mariia Sokolova, Alexander Fedorov, Dan-Adrian Alistarh, and Dmitry Tsitelov. “Testing Concurrency on the JVM with Lincheck.” In <i>Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP</i>, 423–24. Association for Computing Machinery, 2020. <a href=\"https://doi.org/10.1145/3332466.3374503\">https://doi.org/10.1145/3332466.3374503</a>.","ama":"Koval N, Sokolova M, Fedorov A, Alistarh D-A, Tsitelov D. Testing concurrency on the JVM with Lincheck. In: <i>Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP</i>. Association for Computing Machinery; 2020:423-424. doi:<a href=\"https://doi.org/10.1145/3332466.3374503\">10.1145/3332466.3374503</a>","apa":"Koval, N., Sokolova, M., Fedorov, A., Alistarh, D.-A., &#38; Tsitelov, D. (2020). Testing concurrency on the JVM with Lincheck. In <i>Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP</i> (pp. 423–424). San Diego, CA, United States: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3332466.3374503\">https://doi.org/10.1145/3332466.3374503</a>","ista":"Koval N, Sokolova M, Fedorov A, Alistarh D-A, Tsitelov D. 2020. Testing concurrency on the JVM with Lincheck. Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP. PPOPP: Principles and Practice of Parallel Programming, 423–424.","mla":"Koval, Nikita, et al. “Testing Concurrency on the JVM with Lincheck.” <i>Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP</i>, Association for Computing Machinery, 2020, pp. 423–24, doi:<a href=\"https://doi.org/10.1145/3332466.3374503\">10.1145/3332466.3374503</a>.","short":"N. Koval, M. Sokolova, A. Fedorov, D.-A. Alistarh, D. Tsitelov, in:, Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP, Association for Computing Machinery, 2020, pp. 423–424."},"year":"2020","abstract":[{"lang":"eng","text":"Concurrent programming can be notoriously complex and error-prone. Programming bugs can arise from a variety of sources, such as operation re-reordering, or incomplete understanding of the memory model. A variety of formal and model checking methods have been developed to address this fundamental difficulty. While technically interesting, existing academic methods are still hard to apply to the large codebases typical of industrial deployments, which limits their practical impact."}],"doi":"10.1145/3332466.3374503","publication_identifier":{"isbn":["9781450368186"]},"day":"19","status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"id":"2F4DB10C-F248-11E8-B48F-1D18A9856A87","last_name":"Koval","first_name":"Nikita","full_name":"Koval, Nikita"},{"first_name":"Mariia","last_name":"Sokolova","full_name":"Sokolova, Mariia","id":"26217AE4-77FF-11EA-8101-AD24D49E41F4"},{"full_name":"Fedorov, Alexander","first_name":"Alexander","last_name":"Fedorov"},{"id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian","first_name":"Dan-Adrian","last_name":"Alistarh"},{"last_name":"Tsitelov","first_name":"Dmitry","full_name":"Tsitelov, Dmitry"}],"publication":"Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP","_id":"7635","scopus_import":"1","month":"02","title":"Testing concurrency on the JVM with Lincheck","publication_status":"published","oa_version":"None","department":[{"_id":"DaAl"}],"date_created":"2020-04-05T22:00:48Z","article_processing_charge":"No","language":[{"iso":"eng"}],"page":"423-424","quality_controlled":"1","conference":{"start_date":"2020-02-22","name":"PPOPP: Principles and Practice of Parallel Programming","location":"San Diego, CA, United States","end_date":"2020-02-26"},"publisher":"Association for Computing Machinery"},{"publisher":"Association for Computing Machinery","page":"276-291","quality_controlled":"1","ec_funded":1,"title":"Non-blocking interpolation search trees with doubly-logarithmic running time","publication_status":"published","article_processing_charge":"No","date_created":"2020-04-05T22:00:49Z","department":[{"_id":"DaAl"}],"author":[{"id":"3569F0A0-F248-11E8-B48F-1D18A9856A87","full_name":"Brown, Trevor A","last_name":"Brown","first_name":"Trevor A"},{"full_name":"Prokopec, Aleksandar","last_name":"Prokopec","first_name":"Aleksandar"},{"id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","full_name":"Alistarh, Dan-Adrian","orcid":"0000-0003-3650-940X","last_name":"Alistarh","first_name":"Dan-Adrian"}],"_id":"7636","scopus_import":"1","acknowledgement":"This project has received funding from the European Research Council (ERC) under the European Union Horizon 2020 research and innovation program, grant agreement No 805223, ERC Starting Grant ScaleML. We acknowledge the support of the Natural Sciences and\r\nEngineering Research Council of Canada (NSERC). ","abstract":[{"text":"Balanced search trees typically use key comparisons to guide their operations, and achieve logarithmic running time. By relying on numerical properties of the keys, interpolation search achieves lower search complexity and better performance. Although interpolation-based data structures were investigated in the past, their non-blocking concurrent variants have received very little attention so far.\r\nIn this paper, we propose the first non-blocking implementation of the classic interpolation search tree (IST) data structure. For arbitrary key distributions, the data structure ensures worst-case O(log n + p) amortized time for search, insertion and deletion traversals. When the input key distributions are smooth, lookups run in expected O(log log n + p) time, and insertion and deletion run in expected amortized O(log log n + p) time, where p is a bound on the number of threads. To improve the scalability of concurrent insertion and deletion, we propose a novel parallel rebuilding technique, which should be of independent interest.\r\nWe evaluate whether the theoretical improvements translate to practice by implementing the concurrent interpolation search tree, and benchmarking it on uniform and nonuniform key distributions, for dataset sizes in the millions to billions of keys. Relative to the state-of-the-art concurrent data structures, the concurrent interpolation search tree achieves performance improvements of up to 15% under high update rates, and of up to 50% under moderate update rates. Further, ISTs exhibit up to 2X less cache-misses, and consume 1.2 -- 2.6X less memory compared to the next best alternative on typical dataset sizes. We find that the results are surprisingly robust to distributional skew, which suggests that our data structure can be a promising alternative to classic concurrent search structures.","lang":"eng"}],"doi":"10.1145/3332466.3374542","day":"19","isi":1,"external_id":{"isi":["000564476500020"]},"date_updated":"2024-02-28T12:55:14Z","year":"2020","citation":{"ieee":"T. A. Brown, A. Prokopec, and D.-A. Alistarh, “Non-blocking interpolation search trees with doubly-logarithmic running time,” in <i>Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i>, San Diego, CA, United States, 2020, pp. 276–291.","chicago":"Brown, Trevor A, Aleksandar Prokopec, and Dan-Adrian Alistarh. “Non-Blocking Interpolation Search Trees with Doubly-Logarithmic Running Time.” In <i>Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i>, 276–91. Association for Computing Machinery, 2020. <a href=\"https://doi.org/10.1145/3332466.3374542\">https://doi.org/10.1145/3332466.3374542</a>.","apa":"Brown, T. A., Prokopec, A., &#38; Alistarh, D.-A. (2020). Non-blocking interpolation search trees with doubly-logarithmic running time. In <i>Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i> (pp. 276–291). San Diego, CA, United States: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3332466.3374542\">https://doi.org/10.1145/3332466.3374542</a>","ama":"Brown TA, Prokopec A, Alistarh D-A. Non-blocking interpolation search trees with doubly-logarithmic running time. In: <i>Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i>. Association for Computing Machinery; 2020:276-291. doi:<a href=\"https://doi.org/10.1145/3332466.3374542\">10.1145/3332466.3374542</a>","ista":"Brown TA, Prokopec A, Alistarh D-A. 2020. Non-blocking interpolation search trees with doubly-logarithmic running time. Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. PPOPP: Principles and Practice of Parallel Programming, 276–291.","mla":"Brown, Trevor A., et al. “Non-Blocking Interpolation Search Trees with Doubly-Logarithmic Running Time.” <i>Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i>, Association for Computing Machinery, 2020, pp. 276–91, doi:<a href=\"https://doi.org/10.1145/3332466.3374542\">10.1145/3332466.3374542</a>.","short":"T.A. Brown, A. Prokopec, D.-A. Alistarh, in:, Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Association for Computing Machinery, 2020, pp. 276–291."},"conference":{"name":"PPOPP: Principles and Practice of Parallel Programming","start_date":"2020-02-22","end_date":"2020-02-26","location":"San Diego, CA, United States"},"language":[{"iso":"eng"}],"month":"02","oa_version":"Published Version","project":[{"grant_number":"805223","name":"Elastic Coordination for Scalable Machine Learning","call_identifier":"H2020","_id":"268A44D6-B435-11E9-9278-68D0E5697425"}],"publication":"Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","main_file_link":[{"open_access":"1","url":"https://doi.org/10.1145/3332466.3374542"}],"oa":1,"publication_identifier":{"isbn":["9781450368186"]},"date_published":"2020-02-19T00:00:00Z","type":"conference"}]