Compiler Support for Parallel Evaluation of C++ Constant Expressions

• Autorzy: Gozillon Andrew , Seyed H. Haeri , Riordan James , Keir Paul

Identyfikatory

DOI

10.15439/2023F4268

• Języki publikacji: EN

Abstrakty

EN

Metaprogramming, the practice of writing programs that manipulate other programs at compile-time, continues to impact software development; enabling new approaches to optimisation, static analysis, and reflection. Nevertheless, a significant challenge associated with advanced metaprogramming techniques, including the constexpr functionality introduced to C++ in 2011, is an increase in compilation times. This paper presents ClangOz, a novel Clang-based research compiler that addresses this issue by evaluating relevant constant expressions in parallel, thereby reducing compilation time.

Słowa kluczowe

EN

instruction set; semantics; C++ language; static analysis; benchmark testing; load management

PL

instrukcja; semantyka; Język C++; analiza statyczna; test porównawczy; zarządzanie obciążeniem

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2023
• Tom: Vol. 35
• Strony: 481--490
• Opis fizyczny: Bibliogr. 37 poz., il., wykr.

Twórcy

autor

Gozillon Andrew

• Advanced Micro Devices AB, Nordenskioldsgatan 11 A, Office 233 211 19 Malmö, Sweden

• https://orcid.org/0000-0001-7558-7166

autor

Seyed H. Haeri

• University of Bergen, Norway & PLWorkz R&D, Belgium Av. Chapelle-aux-Champs 49, Brussels, Belgium

• https://orcid.org/0000-0002-7969-8573

autor

Riordan James

• University of the West of Scotland High St., Paisley PA1 2BE, Scotland, United Kingdom

• https://orcid.org/0000-0001-6516-9446

autor

Keir Paul

• University of the West of Scotland High St., Paisley PA1 2BE, Scotland, United Kingdom

• https://orcid.org/0000-0002-4781-9377

Bibliografia

• 1. L. V. Todd, “C++ templates are turing complete,” Available at cite-seer.ist.psu.edu/581150.html, 2003.
• 2. D. R. Gabriel, B. Stroustrup, and J. Maurer, “Generalized constant expressions–revision 5,” ISO SC22 WG21 TR, Tech. Rep., 2007.
• 3. (2023) ClangOz. [Online]. Available: https://github.com/agozillon/ClangOz
• 4. C. Lattner, “LLVM and Clang: Next generation compiler technology,” in The BSD conference, vol. 5, 2008.
• 5. H. Alblas, R. op den Akker, P. O. Luttighuis, and K. Sikkel, “A bibliography on parallel parsing,” ACM Sigplan Notices, vol. 29, no. 1, pp. 54–65, 1994.
• 6. H. P. Katseff, “Using data partitioning to implement a parallel assembler,” in Proceedings of the ACM/SIGPLAN conference on Parallel programming: experience with applications, languages and systems, 1988, pp. 66–76.
• 7. V. Seshadri, S. Weber, D. Wortman, C. Yu, and I. Small, “Semantic analysis in a concurrent compiler,” in Proceedings of the ACM SIGPLAN 1988 conference on Programming language design and implementation, 1988, pp. 233–240.
• 8. G. U. Srikanth, “Parallel lexical analyzer on the cell processor,” in 2010 Fourth International Conference on Secure Software Integration and Reliability Improvement Companion. IEEE, 2010, pp. 28–29.
• 9. T. Gross, A. Sobel, and M. Zolg, “Parallel compilation for a parallel machine,” in Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, 1989, pp. 91–100.
• 10. I. J. S. 22, ISO/IEC 14882:2020 Programming languages — C++, 2020.
• 11. P. Dimov, L. Dionne, N. Ranns, R. Smith, and D. Vandevoorde, “More constexpr containers,” 2019. [Online]. Available: http://www.open-std. org/jtc1/sc22/wg21/docs/papers/2019/p0784r7.html
• 12. A. Sutton, “C++ extensions for concepts,” 2017. [Online]. Available: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0734r0.pdf
• 13. H. Sutter, “Metaclasses: Generative c++,” 2018. [Online]. Available: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0707r3.pdf
• 14. M. Chochlík, A. Naumann, and D. Sankel, “Static reflection,” 2017. [Online]. Available: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0707r3.pdf
• 15. H. Dusíková. (2016) Compile time regular expressions. [Online]. Available: https://github.com/hanickadot/compile-time-regular-expressions
• 16. M. Sánchez. (2018) tinyrefl. [Online]. Available: https://github.com/Manu343726/tinyrefl
• 17. N. J. Bouman, “Multiprecision arithmetic for cryptology in c++ - compile-time computations and beating the performance of hand- optimized assembly at run-time,” https://arxiv.org/abs/1804.07236, 2018, https://arxiv.org/abs/1804.07236.
• 18. B. Fahller. (2017) lift. [Online]. Available: https://github.com/rollbear/lift
• 19. G. Steele, Common LISP: the language. Elsevier, 1990.
• 20. A. Alexandrescu, The D programming language. Addison-Wesley Professional, 2010.
• 21. N. D. Matsakis and F. S. Klock, “The rust language,” ACM SIGAda Ada Letters, vol. 34, no. 3, pp. 103–104, 2014.
• 22. J. Bezanson, A. Edelman, S. Karpinski, and V. B. Shah, “Julia: A fresh approach to numerical computing,” SIAM review, vol. 59, no. 1, pp. 65–98, 2017.
• 23. C. McCord, Metaprogramming Elixir, 1st ed. Pragmatic Bookshelf, 2015.
• 24. S. Baxter. (2020) Circle: The c++ automation language. [Online]. Available: https://benchmarksgame-team.pages.debian.net/benchmarksgame/
• 25. N. D. Jones, “An introduction to partial evaluation,” ACM Computing Surveys (CSUR), vol. 28, no. 3, pp. 480–503, 1996.
• 26. T. L. Veldhuizen, “C++ templates as partial evaluation,” arXiv preprint cs/9810010, 1998.
• 27. A. Tyurin, D. Berezun, and S. Grigorev, “Optimizing gpu programs by partial evaluation,” in Proceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, 2020, pp. 431–432.
• 28. R. Leißa, K. Boesche, S. Hack, A. Pérard-Gayot, R. Membarth, P. Slusallek, A. Müller, and B. Schmidt, “Anydsl: A partial evaluation framework for programming high-performance libraries,” Proceedings of the ACM on Programming Languages, vol. 2, no. OOPSLA, pp. 1–30, 2018.
• 29. T. Würthinger, C. Wimmer, C. Humer, A. Wöß, L. Stadler, C. Seaton, G. Duboscq, D. Simon, and M. Grimmer, “Practical partial evaluation for high-performance dynamic language runtimes,” in Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation, 2017, pp. 662–676.
• 30. C. Consel and O. Danvy, “Partial evaluation in parallel,” Lisp and Symbolic Computation, vol. 5, no. 4, pp. 327–342, 1993.
• 31. M. Sperber, P. Thiemann, and H. Klaeren, “Distributed partial evaluation,” in Proceedings of the second international symposium on Parallel symbolic computation, 1997, pp. 80–87.
• 32. A. Bouter, T. Alderliesten, A. Bel, C. Witteveen, and P. A. Bosman, “Large-scale parallelization of partial evaluations in evolutionary algorithms for real-world problems,” in Proceedings of the Genetic and Evolutionary Computation Conference, 2018, pp. 1199–1206.
• 33. K. Kennedy and J. R. Allen, Optimizing compilers for modern architectures: a dependence-based approach. Morgan Kaufmann Publishers Inc., 2001.
• 34. I. J. S. 22, “Technical specification for c++ extensions for parallelism,” Tech. Rep., 2018.
• 35. L. Dagum and R. Menon, “Openmp: an industry standard api for shared-memory programming,” IEEE computational science and engineering, vol. 5, no. 1, pp. 46–55, 1998.
• 36. C. Bienia, S. Kumar, J. P. Singh, and K. Li, “The parsec benchmark suite: Characterization and architectural implications,” in Proceedings of the 17th international conference on Parallel architectures and compilation techniques, 2008, pp. 72–81.
• 37. D. Bagley. (2001, Apr.) The computer language benchmarks game. [Online]. Available: https://benchmarksgame-team.pages.debian.net/benchmarksgame/

Uwagi

1. The authors wish to thank the Royal Society of Edinburgh for their support through the Saltire International Collaboration Award (Grant Number 1981).

2. Thematic Tracks Regular Papers

3. Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2024).