Document Open Access Logo

Hinted Dictionaries: Efficient Functional Ordered Sets and Maps

Authors Amir Shaikhha, Mahdi Ghorbani, Hesam Shahrokhi

PDF
Thumbnail PDF

File

LIPIcs.ECOOP.2023.28.pdf
  • Filesize: 1.07 MB
  • 30 pages

Document Identifiers

Author Details

Amir Shaikhha
  • University of Edinburgh, UK
Mahdi Ghorbani
  • University of Edinburgh, UK
Hesam Shahrokhi
  • University of Edinburgh, UK

Acknowledgements

The authors would like to thank Huawei for their support of the distributed data management and processing laboratory at the University of Edinburgh.

Cite As Get BibTex

Amir Shaikhha, Mahdi Ghorbani, and Hesam Shahrokhi. Hinted Dictionaries: Efficient Functional Ordered Sets and Maps. In 37th European Conference on Object-Oriented Programming (ECOOP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 263, pp. 28:1-28:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ECOOP.2023.28

Abstract

This paper introduces hinted dictionaries for expressing efficient ordered sets and maps functionally. As opposed to the traditional ordered dictionaries with logarithmic operations, hinted dictionaries can achieve better performance by using cursor-like objects referred to as hints. Hinted dictionaries unify the interfaces of imperative ordered dictionaries (e.g., C++ maps) and functional ones (e.g., Adams' sets). We show that such dictionaries can use sorted arrays, unbalanced trees, and balanced trees as their underlying representations. Throughout the paper, we use Scala to present the different components of hinted dictionaries. We also provide a C++ implementation to evaluate the effectiveness of hinted dictionaries. Hinted dictionaries provide superior performance for set-set operations in comparison with the standard library of C++. Also, they show a competitive performance in comparison with the SciPy library for sparse vector operations.

Subject Classification

ACM Subject Classification
  • Software and its engineering → Functional languages
  • Theory of computation → Data structures design and analysis
Keywords
  • Functional Collections
  • Ordered Dictionaries
  • Sparse Linear Algebra

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Stephen Adams. Efficient sets - a balancing act. JFP, 3(4):553-561, 1993. Google Scholar
  2. Georgy Adelson-Velsky and E. M. Landis. An algorithm for the organization of information. Proc. of the USSR Academy of Sciences, 145:263-266, 1962. In Russian, English translation by Myron J. Ricci in Soviet Doklady, 3:1259-1263, 1962. Google Scholar
  3. Rudolf Bayer. Symmetric Binary B-Trees: Data Structure and Maintenance Algorithms. Acta Informatica, 1:290-306, 1972. Google Scholar
  4. Guy E Blelloch, Daniel Ferizovic, and Yihan Sun. Just join for parallel ordered sets. In SPAA'16, pages 253-264, 2016. Google Scholar
  5. Sébastien Doeraene. A type-parametric unboxed Option type for Scala. https://github.com/sjrd/scala-unboxed-option, 2019. Accessed: 2021-10-11.
  6. Yoichi Hirai and Kazuhiko Yamamoto. Balancing weight-balanced trees. Journal of Functional Programming, 21(3):287-307, 2011. Google Scholar
  7. Changkyu Kim, Tim Kaldewey, Victor W Lee, Eric Sedlar, Anthony D Nguyen, Nadathur Satish, Jatin Chhugani, Andrea Di Blas, and Pradeep Dubey. Sort vs. hash revisited: Fast join implementation on modern multi-core CPUs. PVLDB, 2(2):1378-1389, 2009. Google Scholar
  8. Hećate Moonlight. unpacked sum types · Wiki · Glasgow Haskell Compiler / GHC. https://gitlab.haskell.org/ghc/ghc/-/wikis/unpacked-sum-types, 2021. Accessed: 2021-10-11.
  9. Jürg Nievergelt and Edward M. Reingold. Binary search trees of bounded balance. SIAM J. Comput., 2(1):33-43, 1973. Google Scholar
  10. Bruno CdS Oliveira, Adriaan Moors, and Martin Odersky. Type classes as objects and implicits. ACM Sigplan Notices, 45(10):341-360, 2010. Google Scholar
  11. Raimund Seidel and Cecilia R Aragon. Randomized search trees. Algorithmica, 16(4):464-497, 1996. Google Scholar
  12. Amir Shaikhha, Mathieu Huot, Jaclyn Smith, and Dan Olteanu. Functional collection programming with semi-ring dictionaries. PACMPL, 6(OOPSLA1):1-33, 2022. Google Scholar
  13. Amir Shaikhha, Marios Kelepeshis, and Mahdi Ghorbani. Fine-tuning data structures for query processing. In Proceedings of the 21st ACM/IEEE International Symposium on Code Generation and Optimization, CGO 2023, pages 149-161, New York, NY, USA, 2023. Association for Computing Machinery. URL: https://doi.org/10.1145/3579990.3580016.
  14. Boost Software. Class template flat_map - 1.79.0. https://www.boost.org/doc/libs/1_79_0/doc/html/boost/container/flat_map.html, 2018. Accessed: 2021-10-5.
  15. Milan Straka. The performance of the haskell containers package. ACM Sigplan Notices, 45(11):13-24, 2010. Google Scholar
  16. Milan Straka. Adams’ trees revisited. In International Symposium on Trends in Functional Programming, pages 130-145. Springer, 2011. Google Scholar
  17. Yihan Sun, Daniel Ferizovic, and Guy E Belloch. PAM: parallel augmented maps. In Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 290-304, 2018. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact