Cited By
View all- Khan MChen S(2024)Gradual Typing Performance, Micro Configurations and Macro PerspectivesTheoretical Aspects of Software Engineering10.1007/978-3-031-64626-3_15(261-278)Online publication date: 29-Jul-2024
Type-Based Gradual Typing Performance Optimization
Article No.: 89, Pages 2667 - 2699
Abstract
Gradual typing has emerged as a popular design point in programming languages, attracting significant interests from both academia and industry. Programmers in gradually typed languages are free to utilize static and dynamic typing as needed. To make such languages sound, runtime checks mediate the boundary of typed and untyped code. Unfortunately, such checks can incur significant runtime overhead on programs that heavily mix static and dynamic typing. To combat this overhead without necessitating changes to the underlying implementations of languages, we present discriminative typing. Discriminative typing works by optimistically inferring types for functions and implementing an optimized version of the function based on this type. To preserve safety it also implements an un-optimized version of the function based purely on the provided annotations. With two versions of each function in hand, discriminative typing translates programs so that the optimized functions are called as frequently as possible while also preserving program behaviors.
We have implemented discriminative typing in Reticulated Python and have evaluated its performance compared to guarded Reticulated Python. Our results show that discriminative typing improves the performance across 95% of tested programs, when compared to Reticulated, and achieves more than 4× speedup in more than 56% of these programs. We also compare its performance against a previous optimization approach and find that discriminative typing improved performance across 93% of tested programs, with 30% of these programs receiving speedups between 4 to 25 times. Finally, our evaluation shows that discriminative typing remarkably reduces the overhead of gradual typing on many mixed type configurations of programs.
In addition, we have implemented discriminative typing in Grift and evaluated its performance. Our evaluation demonstrations that DT significantly improves performance of Grift
References
[1]
Ole Agesen. 1995. The Cartesian Product Algorithm: Simple and Precise Type Inference Of Parametric Polymorphism. In Proceedings of the 9th European Conference on Object-Oriented Programming (ECOOP ’95). Springer-Verlag, Berlin, Heidelberg. 2–26. isbn:3540601600
[2]
Esteban Allende, Johan Fabry, Ronald Garcia, and Éric Tanter. 2014. Confined Gradual Typing. In Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications (OOPSLA ’14). ACM, New York, NY, USA. 251–270. isbn:978-1-4503-2585-1 https://doi.org/10.1145/2660193.2660222
[3]
Esteban Allende, Johan Fabry, and Éric Tanter. 2013. Cast Insertion Strategies for Gradually-Typed Objects. In Proceedings of the 9th ACM Dynamic Languages Symposium (DLS 2013). ACM Press, Indianapolis, IN, USA. 27–36. ACM SIGPLAN Notices, 49(2)
[4]
Sven Apel, Don Batory, Christian Kästner, and Gunter Saake. 2016. Feature-Oriented Software Product Lines. Springer.
[5]
Spenser Bauman, Carl Friedrich Bolz-Tereick, Jeremy Siek, and Sam Tobin-Hochstadt. 2017. Sound Gradual Typing: Only Mostly Dead. Proc. ACM Program. Lang., 1, OOPSLA (2017), Article 54, Oct., 24 pages. issn:2475-1421 https://doi.org/10.1145/3133878
[6]
Gavin Bierman, Erik Meijer, and Mads Torgersen. 2010. Adding Dynamic Types to C♯. In ECOOP 2010 - Object-Oriented Programming, Theo D’Hondt (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg. 76–100. isbn:978-3-642-14107-2
[7]
Carl Friedrich Bolz, Antonio Cuni, Maciej Fijał kowski, Michael Leuschel, Samuele Pedroni, and Armin Rigo. 2011. Runtime Feedback in a Meta-Tracing JIT for Efficient Dynamic Languages. In Proceedings of the 6th Workshop on Implementation, Compilation, Optimization of Object-Oriented Languages, Programs and Systems (ICOOOLPS ’11). Association for Computing Machinery, New York, NY, USA. Article 9, 8 pages. isbn:9781450308946 https://doi.org/10.1145/2069172.2069181
[8]
Carl Friedrich Bolz, Antonio Cuni, Maciej Fijalkowski, and Armin Rigo. 2009. Tracing the Meta-Level: PyPy’s Tracing JIT Compiler. In Proceedings of the 4th Workshop on the Implementation, Compilation, Optimization of Object-Oriented Languages and Programming Systems (ICOOOLPS ’09). Association for Computing Machinery, New York, NY, USA. 18–25. isbn:9781605585413 https://doi.org/10.1145/1565824.1565827
[9]
John Campora, Sheng Chen, Martin Erwig, and Eric Walkingshaw. 2018. Migrating Gradual Types. In Proceedings of the 45th ACM SIGPLAN Symposium on Principles of Programming Languages (POPL ’18). ACM, New York, NY, USA.
[10]
John Peter Campora, Sheng Chen, and Eric Walkingshaw. 2018. Casts and Costs: Harmonizing Safety and Performance in Gradual Typing. Proc. ACM Program. Lang., 2, ICFP (2018), Article 98, July, 30 pages. issn:2475-1421 https://doi.org/10.1145/3236793
[11]
John Peter Campora, Mohammad Wahiduzzaman Khan, and Sheng Chen. 2023. Type-based Gradual Typing Performance Optimization. Available at https://people.cmix.louisiana.edu/schen/ws/techreport/dt-long.pdf
[12]
Robert Cartwright and Mike Fagan. 1991. Soft Typing. In Proceedings of the ACM SIGPLAN 1991 Conference on Programming Language Design and Implementation (PLDI ’91). ACM, New York, NY, USA. 278–292. isbn:0-89791-428-7 https://doi.org/10.1145/113445.113469
[13]
Tiago Carvalho, Pedro Pinto, and João M. P. Cardoso. 2015. Programming Strategies for Contextual Runtime Specialization. In Proceedings of the 18th International Workshop on Software and Compilers for Embedded Systems (SCOPES ’15). ACM, New York, NY, USA. 3–11. isbn:978-1-4503-3593-5 https://doi.org/10.1145/2764967.2764973
[14]
Craig David Chambers. 1992. The Design and Implementation of the Self Compiler, an Optimizing Compiler for Object-Oriented Programming Languages. Ph. D. Dissertation. Stanford, CA, USA. UMI Order No. GAX92-21602
[15]
Sheng Chen, Martin Erwig, and Eric Walkingshaw. 2012. An Error-tolerant Type System for Variational Lambda Calculus. In Proceedings of the 17th ACM SIGPLAN International Conference on Functional Programming (ICFP ’12). ACM, New York, NY, USA. 29–40. isbn:978-1-4503-1054-3 https://doi.org/10.1145/2364527.2364535
[16]
Sheng Chen, Martin Erwig, and Eric Walkingshaw. 2014. Extending Type Inference to Variational Programs. ACM Trans. Program. Lang. Syst., 36, 1 (2014), Article 1, March, 54 pages. issn:0164-0925 https://doi.org/10.1145/2518190
[17]
Charles Consel and François Noël. 1996. A General Approach for Run-time Specialization and Its Application to C. In Proceedings of the 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’96). ACM, New York, NY, USA. 145–156. isbn:0-89791-769-3 https://doi.org/10.1145/237721.237767
[18]
K.D. Cooper, M.W. Hall, and K. Kennedy. 1992. Procedure cloning. In Proceedings of the 1992 International Conference on Computer Languages. 96–105. https://doi.org/10.1109/ICCL.1992.185472
[19]
Jeffrey Dean, Craig Chambers, and David Grove. 1995. Selective Specialization for Object-Oriented Languages. In Proceedings of the ACM SIGPLAN 1995 Conference on Programming Language Design and Implementation (PLDI ’95). Association for Computing Machinery, New York, NY, USA. 93–102. isbn:0897916972 https://doi.org/10.1145/207110.207119
[20]
Martin Erwig and Eric Walkingshaw. 2011. The Choice Calculus: A Representation for Software Variation. ACM Trans. Softw. Eng. Methodol., 21, 1 (2011), Article 6, Dec., 27 pages. issn:1049-331X https://doi.org/10.1145/2063239.2063245
[21]
Daniel Feltey, Ben Greenman, Christophe Scholliers, Robert Bruce Findler, and Vincent St-Amour. 2018. Collapsible Contracts: Fixing a Pathology of Gradual Typing. Proc. ACM Program. Lang., 2, OOPSLA (2018), Article 133, Oct., 27 pages. issn:2475-1421 https://doi.org/10.1145/3276503
[22]
Daniel Feltey, Ben Greenman, Christophe Scholliers, Robert Bruce Findler, and Vincent St-Amour. 2018. Collapsible Contracts: Fixing a Pathology of Gradual Typing. Proc. ACM Program. Lang., 2, OOPSLA (2018), Article 133, oct, 27 pages. https://doi.org/10.1145/3276503
[23]
Andreas Gal, Brendan Eich, Mike Shaver, David Anderson, David Mandelin, Mohammad R. Haghighat, Blake Kaplan, Graydon Hoare, Boris Zbarsky, Jason Orendorff, Jesse Ruderman, Edwin W. Smith, Rick Reitmaier, Michael Bebenita, Mason Chang, and Michael Franz. 2009. Trace-Based Just-in-Time Type Specialization for Dynamic Languages. In Proceedings of the 30th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’09). Association for Computing Machinery, New York, NY, USA. 465–478. isbn:9781605583921 https://doi.org/10.1145/1542476.1542528
[24]
Ronald Garcia. 2013. Calculating Threesomes, with Blame. In Proceedings of the 18th ACM SIGPLAN International Conference on Functional Programming (ICFP ’13). ACM, New York, NY, USA. 417–428. isbn:978-1-4503-2326-0 https://doi.org/10.1145/2500365.2500603
[25]
Ronald Garcia and Matteo Cimini. 2015. Principal Type Schemes for Gradual Programs. In Proceedings of the 42Nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’15). ACM, New York, NY, USA. 303–315. isbn:978-1-4503-3300-9 https://doi.org/10.1145/2676726.2676992
[26]
Ben Greenman and Matthias Felleisen. 2018. A Spectrum of Type Soundness and Performance. Proc. ACM Program. Lang., 2, ICFP (2018), Article 71, July, 32 pages. issn:2475-1421 https://doi.org/10.1145/3236766
[27]
Ben Greenman and Zeina Migeed. 2018. On the Cost of Type-tag Soundness. In Proceedings of the ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation (PEPM ’18). ACM, New York, NY, USA. 30–39. isbn:978-1-4503-5587-2 https://doi.org/10.1145/3162066
[28]
Ben Greenman, Asumu Takikawa, Max S. New, Daniel Feltey, Robert Bruce Findler, Jan Vitek, and Matthias Felleisen. 2019. How to evaluate the performance of gradual type systems. Journal of Functional Programming, 29 (2019), e4. https://doi.org/10.1017/S0956796818000217
[29]
Fritz Henglein. 1994. Dynamic Typing: Syntax and Proof Theory. In Selected Papers of the Symposium on Fourth European Symposium on Programming (ESOP’92). Elsevier Science Publishers B. V., Amsterdam, The Netherlands, The Netherlands. 197–230. http://dl.acm.org/citation.cfm?id=197475.190867
[30]
David Herman, Aaron Tomb, and Cormac Flanagan. 2010. Space-efficient Gradual Typing. Higher Order Symbol. Comput., 23, 2 (2010), June, 167–189. issn:1388-3690 https://doi.org/10.1007/s10990-011-9066-z
[31]
Jian Huang, Michael Allen-Bond, and Xuechen Zhang. 2017. Pallas: Semantic-Aware Checking for Finding Deep Bugs in Fast Path. In Proceedings of the Twenty-Second International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS ’17). ACM, New York, NY, USA. 709–722. isbn:978-1-4503-4465-4 https://doi.org/10.1145/3037697.3037743
[32]
Madhukar N. Kedlaya, Jared Roesch, Behnam Robatmili, Mehrdad Reshadi, and Ben Hardekopf. 2013. Improved Type Specialization for Dynamic Scripting Languages. SIGPLAN Not., 49, 2 (2013), oct, 37–48. issn:0362-1340 https://doi.org/10.1145/2578856.2508177
[33]
K. Kelsey, T. Bai, C. Ding, and C. Zhang. 2009. Fast Track: A Software System for Speculative Program Optimization. In 2009 International Symposium on Code Generation and Optimization. 157–168. https://doi.org/10.1109/CGO.2009.18
[34]
Minhaj Ahmad Khan, H. P. Charles, and D. Barthou. 2008. An Effective Automated Approach to Specialization of Code. In Languages and Compilers for Parallel Computing, Vikram Adve, María Jesús Garzarán, and Paul Petersen (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg. 308–322.
[35]
Alex Kogan and Erez Petrank. 2012. A Methodology for Creating Fast Wait-free Data Structures. In Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP ’12). ACM, New York, NY, USA. 141–150. isbn:978-1-4503-1160-1 https://doi.org/10.1145/2145816.2145835
[36]
Andre Kuhlenschmidt, Deyaaeldeen Almahallawi, and Jeremy G. Siek. 2019. Toward Efficient Gradual Typing for Structural Types via Coercions. In Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2019). Association for Computing Machinery, New York, NY, USA. 517–532. isbn:9781450367127 https://doi.org/10.1145/3314221.3314627
[37]
Dylan McNamee, Jonathan Walpole, Calton Pu, Crispin Cowan, Charles Krasic, Ashvin Goel, Perry Wagle, Charles Consel, Gilles Muller, and Renauld Marlet. 2001. Specialization Tools and Techniques for Systematic Optimization of System Software. ACM Trans. Comput. Syst., 19, 2 (2001), May, 217–251. issn:0734-2071 https://doi.org/10.1145/377769.377778
[38]
Philippe Meunier, Robert Bruce Findler, and Matthias Felleisen. 2006. Modular Set-based Analysis from Contracts. In Conference Record of the 33rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’06). ACM, New York, NY, USA. 218–231. isbn:1-59593-027-2 https://doi.org/10.1145/1111037.1111057
[39]
Yusuke Miyazaki, Taro Sekiyama, and Atsushi Igarashi. 2019. Dynamic Type Inference for Gradual Hindley-Milner Typing. PACMPL, POPL (2019).
[40]
Colin Moock. 2004. Essential ActionScript 2.0. O’Reilly Media, Inc. isbn:0596006527
[41]
Cameron Moy, Phúc C. Nguyễn, Sam Tobin-Hochstadt, and David Van Horn. 2021. Corpse Reviver: Sound and Efficient Gradual Typing via Contract Verification. Proc. ACM Program. Lang., 5, POPL (2021), Article 53, jan, 28 pages. https://doi.org/10.1145/3434334
[42]
Fabian Muehlboeck and Ross Tate. 2017. Sound Gradual Typing is Nominally Alive and Well. In OOPSLA. ACM, New York, NY, USA. https://doi.org/10.1145/3133880
[43]
Phúc C. Nguyen, Thomas Gilray, Sam Tobin-Hochstadt, and David Van Horn. 2017. Soft Contract Verification for Higher-order Stateful Programs. Proc. ACM Program. Lang., 2, POPL (2017), Article 51, Dec., 30 pages. issn:2475-1421 https://doi.org/10.1145/3158139
[44]
Phúc C. Nguyen, Sam Tobin-Hochstadt, and David Van Horn. 2014. Soft Contract Verification. In Proceedings of the 19th ACM SIGPLAN International Conference on Functional Programming (ICFP ’14). ACM, New York, NY, USA. 139–152. isbn:978-1-4503-2873-9 https://doi.org/10.1145/2628136.2628156
[45]
Francisco Ortin, Miguel Garcia, and Seán McSweeney. 2019. Rule-based program specialization to optimize gradually typed code. Knowledge-Based Systems, 179 (2019), 145–173. issn:0950-7051 https://doi.org/10.1016/j.knosys.2019.05.013
[46]
Massimiliano Poletto, Wilson C. Hsieh, Dawson R. Engler, and M. Frans Kaashoek. 1999. C and Tcc: A Language and Compiler for Dynamic Code Generation. ACM Trans. Program. Lang. Syst., 21, 2 (1999), March, 324–369. issn:0164-0925 https://doi.org/10.1145/316686.316697
[47]
Aseem Rastogi, Avik Chaudhuri, and Basil Hosmer. 2012. The Ins and Outs of Gradual Type Inference. In Proceedings of the 39th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’12). ACM, New York, NY, USA. 481–494. isbn:978-1-4503-1083-3 https://doi.org/10.1145/2103656.2103714
[48]
Aseem Rastogi, Nikhil Swamy, Cédric Fournet, Gavin M. Bierman, and Panagiotis Vekris. 2015. Safe & Efficient Gradual Typing for TypeScript. In POPL.
[49]
Gregor Richards, Ellen Arteca, and Alexi Turcotte. 2017. The VM Already Knew That: Leveraging Compile-time Knowledge to Optimize Gradual Typing. Proc. ACM Program. Lang., 1, OOPSLA (2017), Article 55, Oct., 27 pages. issn:2475-1421 https://doi.org/10.1145/3133879
[50]
Gregor Richards, Francesco Zappa Nardelli, and Jan Vitek. 2015. Concrete Types for TypeScript. In 29th European Conference on Object-Oriented Programming (ECOOP 2015), John Tang Boyland (Ed.) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 37). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany. 76–100. isbn:978-3-939897-86-6 issn:1868-8969 https://doi.org/10.4230/LIPIcs.ECOOP.2015.76
[51]
Jeremy Siek, Peter Thiemann, and Philip Wadler. 2015. Blame and Coercion: Together Again for the First Time. In Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’15). ACM, New York, NY, USA. 425–435. isbn:978-1-4503-3468-6 https://doi.org/10.1145/2737924.2737968
[52]
Jeremy Siek, Michael M. Vitousek, Matteo Cimini, Sam Tobin-Hochstadt, and Ronald Garcia. 2015. Monotonic References for Efficient Gradual Typing. isbn:978-3-662-46668-1 https://doi.org/10.1007/978-3-662-46669-8_18
[53]
Jeremy G. Siek and Walid Taha. 2006. Gradual Typing for Functional Languages. In In Scheme and Functional Programming Workshop. 81–92.
[54]
Jeremy G Siek, Michael M Vitousek, Matteo Cimini, and John Tang Boyland. 2015. Refined criteria for gradual typing. In LIPIcs-Leibniz International Proceedings in Informatics. 32.
[55]
Jeremy G. Siek and Philip Wadler. 2010. Threesomes, with and Without Blame. In Proceedings of the 37th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’10). ACM, New York, NY, USA. 365–376. isbn:978-1-60558-479-9 https://doi.org/10.1145/1706299.1706342
[56]
Asumu Takikawa, Daniel Feltey, Ben Greenman, Max S. New, Jan Vitek, and Matthias Felleisen. 2016. Is Sound Gradual Typing Dead? In Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’16). ACM, New York, NY, USA. 456–468. isbn:978-1-4503-3549-2 https://doi.org/10.1145/2837614.2837630
[57]
Sam Tobin-Hochstadt and Matthias Felleisen. 2008. The Design and Implementation of Typed Scheme. In Proceedings of the 35th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’08). ACM, New York, NY, USA. 395–406. isbn:978-1-59593-689-9 https://doi.org/10.1145/1328438.1328486
[58]
Michael M. Vitousek, Andrew M. Kent, Jeremy G. Siek, and Jim Baker. 2014. Design and Evaluation of Gradual Typing for Python. In Proceedings of the 10th ACM Symposium on Dynamic Languages (DLS ’14). ACM, New York, NY, USA. 45–56. isbn:978-1-4503-3211-8 https://doi.org/10.1145/2661088.2661101
[59]
Michael M. Vitousek, Jeremy G. Siek, and Avik Chaudhuri. 2019. Optimizing and Evaluating Transient Gradual Typing. In Proceedings of the 15th ACM SIGPLAN International Symposium on Dynamic Languages (DLS 2019). ACM, New York, NY, USA. 28–41. isbn:978-1-4503-6996-1 https://doi.org/10.1145/3359619.3359742
[60]
Michael M. Vitousek, Cameron Swords, and Jeremy G. Siek. 2017. Big Types in Little Runtime: Open-world Soundness and Collaborative Blame for Gradual Type Systems. In Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages (POPL 2017). ACM, New York, NY, USA. 762–774. isbn:978-1-4503-4660-3 https://doi.org/10.1145/3009837.3009849
[61]
Philip Wadler and Robert Bruce Findler. 2009. Well-Typed Programs Can’t Be Blamed. In Proceedings of the 18th European Symposium on Programming Languages and Systems: Held As Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2009 (ESOP ’09). Springer-Verlag, Berlin, Heidelberg. 1–16. isbn:978-3-642-00589-3 https://doi.org/10.1007/978-3-642-00590-9_1
[62]
Wen Xu, Sanjeev Kumar, and Kai Li. 2004. Fast Paths in Concurrent Programs. In Proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques (PACT ’04). IEEE Computer Society, Washington, DC, USA. 189–200. isbn:0-7695-2229-7 https://doi.org/10.1109/PACT.2004.16
Index Terms
- Type-Based Gradual Typing Performance Optimization
Recommendations
On polymorphic gradual typing
We study an extension of gradual typing—a method to integrate dynamic typing and static typing smoothly in a single language—to parametric polymorphism and its theoretical properties, including conservativity of typing and semantics over both statically ...
Gradual typing: a new perspective
We define a new, more semantic interpretation of gradual types and use it to ``gradualize'' two forms of polymorphism: subtyping polymorphism and implicit parametric polymorphism. In particular, we use the new interpretation to define three gradual type ...
Confined gradual typing
OOPSLA '14Gradual typing combines static and dynamic typing flexibly and safely in a single programming language. To do so, gradually typed languages implicitly insert casts where needed, to ensure at runtime that typing assumptions are not violated by untyped ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
January 2024
2820 pages
Copyright © 2024 Owner/Author.
This work is licensed under a Creative Commons Attribution 4.0 International License.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 05 January 2024
Published in PACMPL Volume 8, Issue POPL
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 447Total Downloads
- Downloads (Last 12 months)447
- Downloads (Last 6 weeks)83
Reflects downloads up to 30 Nov 2024
Other Metrics
Citations
Cited By
View all- Khan MChen S(2024)Gradual Typing Performance, Micro Configurations and Macro PerspectivesTheoretical Aspects of Software Engineering10.1007/978-3-031-64626-3_15(261-278)Online publication date: 29-Jul-2024
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in