Document Open Access Logo

Best-Effort Lazy Evaluation for Python Software Built on APIs

Authors Guoqiang Zhang, Xipeng Shen

PDF
Thumbnail PDF

File

LIPIcs.ECOOP.2021.15.pdf
  • Filesize: 1.31 MB
  • 24 pages

Document Identifiers

Author Details

Guoqiang Zhang
  • Department of Computer Science, North Carolina State University, Raleigh, NC, USA
Xipeng Shen
  • Department of Computer Science, North Carolina State University, Raleigh, NC, USA

Funding

This material is based upon work supported by the National Science Foundation (NSF) under Grants CCF-1703487. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of NSF.

Cite As Get BibTex

Guoqiang Zhang and Xipeng Shen. Best-Effort Lazy Evaluation for Python Software Built on APIs. In 35th European Conference on Object-Oriented Programming (ECOOP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 194, pp. 15:1-15:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ECOOP.2021.15

Abstract

This paper focuses on an important optimization opportunity in Python-hosted domain-specific languages (DSLs): the use of laziness for optimization, whereby multiple API calls are deferred and then optimized prior to execution (rather than executing eagerly, which would require executing each call in isolation). In existing supports of lazy evaluation, laziness is "terminated" as soon as control passes back to the host language in any way, limiting opportunities for optimization. This paper presents Cunctator, a framework that extends this laziness to more of the Python language, allowing intermediate values from DSLs like NumPy or Pandas to flow back to the host Python code without triggering evaluation. This exposes more opportunities for optimization and, more generally, allows for larger computation graphs to be built, producing 1.03-14.2X speedups on a set of programs in common libraries and frameworks.

Subject Classification

ACM Subject Classification
  • Software and its engineering → Dynamic compilers
  • Software and its engineering → Runtime environments
Keywords
  • Lazy Evaluation
  • Python
  • API Optimization

Metrics

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

References

  1. Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, Manjunath Kudlur, Josh Levenberg, Rajat Monga, Sherry Moore, Derek Gordon Murray, Benoit Steiner, Paul A. Tucker, Vijay Vasudevan, Pete Warden, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. Tensorflow: A system for large-scale machine learning. In Kimberly Keeton and Timothy Roscoe, editors, 12th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2016, Savannah, GA, USA, November 2-4, 2016, pages 265-283. USENIX Association, 2016. URL: https://www.usenix.org/conference/osdi16/technical-sessions/presentation/abadi.
  2. Randy Allen and Ken Kennedy. Optimizing Compilers for Modern Architectures: A Dependence-based Approach. Morgan Kaufmann, 2001. Google Scholar
  3. Adrienne G. Bloss, Paul Hudak, and Jonathan Young. Code optimizations for lazy evaluation. LISP Symb. Comput., 1(2):147-164, 1988. Google Scholar
  4. Edmund M. Clarke and E. Allen Emerson. Design and synthesis of synchronization skeletons using branching-time temporal logic. In Dexter Kozen, editor, Logics of Programs, Workshop, Yorktown Heights, New York, USA, May 1981, volume 131 of Lecture Notes in Computer Science, pages 52-71. Springer, 1981. URL: https://doi.org/10.1007/BFb0025774.
  5. Cunctator Docker Image. URL: https://github.com/sangongs/Cunctator_docker.
  6. Krzysztof Czarnecki and Ulrich W. Eisenecker. Generative programming - methods, tools and applications. Addison-Wesley, 2000. URL: http://www.addison-wesley.de/main/main.asp?page=englisch/bookdetails&productid=99258.
  7. Bruno Morais Ferreira, Britaldo Silveira Soares-Filho, and Fernando Magno Quintão Pereira. The dinamica EGO virtual machine. Sci. Comput. Program., 173:3-20, 2019. URL: https://doi.org/10.1016/j.scico.2018.02.002.
  8. Samuel Z. Guyer and Calvin Lin. Broadway: A compiler for exploiting the domain-specific semantics of software libraries. Proc. IEEE, 93(2):342-357, 2005. URL: https://doi.org/10.1109/JPROC.2004.840489.
  9. Peter Henderson and James H. Morris Jr. A lazy evaluator. In Susan L. Graham, Robert M. Graham, Michael A. Harrison, William I. Grosky, and Jeffrey D. Ullman, editors, Conference Record of the Third ACM Symposium on Principles of Programming Languages, Atlanta, Georgia, USA, January 1976, pages 95-103. ACM Press, 1976. URL: https://doi.org/10.1145/800168.811543.
  10. Paul Hudak, John Hughes, Simon L. Peyton Jones, and Philip Wadler. A history of haskell: being lazy with class. In Barbara G. Ryder and Brent Hailpern, editors, Proceedings of the Third ACM SIGPLAN History of Programming Languages Conference (HOPL-III), San Diego, California, USA, 9-10 June 2007, pages 1-55. ACM, 2007. URL: https://doi.org/10.1145/1238844.1238856.
  11. Thomas Johnsson. Efficient compilation of lazy evaluation. In Mary S. Van Deusen and Susan L. Graham, editors, Proceedings of the 1984 SIGPLAN Symposium on Compiler Construction, Montreal, Canada, June 17-22, 1984, pages 58-69. ACM, 1984. URL: https://doi.org/10.1145/502874.502880.
  12. Project Jupyter. URL: https://jupyter.org/.
  13. Ken Kennedy, Bradley Broom, Arun Chauhan, Robert J. Fowler, John Garvin, Charles Koelbel, Cheryl McCosh, and John M. Mellor-Crummey. Telescoping languages: A system for automatic generation of domain languages. Proc. IEEE, 93(2):387-408, 2005. URL: https://doi.org/10.1109/JPROC.2004.840447.
  14. Georgios Korfiatis, Michalis A. Papakyriakou, and Nikolaos Papaspyrou. A type and effect system for implementing functional arrays with destructive updates. In Maria Ganzha, Leszek A. Maciaszek, and Marcin Paprzycki, editors, Federated Conference on Computer Science and Information Systems - FedCSIS 2011, Szczecin, Poland, 18-21 September 2011, Proceedings, pages 879-886, 2011. URL: http://ieeexplore.ieee.org/document/6078196/.
  15. Siu Kwan Lam, Antoine Pitrou, and Stanley Seibert. Numba: a llvm-based python JIT compiler. In Hal Finkel, editor, Proceedings of the Second Workshop on the LLVM Compiler Infrastructure in HPC, LLVM 2015, Austin, Texas, USA, November 15, 2015, pages 7:1-7:6. ACM, 2015. URL: https://doi.org/10.1145/2833157.2833162.
  16. John Launchbury. A natural semantics for lazy evaluation. In Mary S. Van Deusen and Bernard Lang, editors, Conference Record of the Twentieth Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Charleston, South Carolina, USA, January 1993, pages 144-154. ACM Press, 1993. URL: https://doi.org/10.1145/158511.158618.
  17. Wes McKinney. pandas: a foundational python library for data analysis and statistics. Python for High Performance and Scientific Computing, 14, 2011. Google Scholar
  18. Python memory-profiler Library. URL: https://pypi.org/project/memory-profiler/.
  19. Dan Moldovan, James M. Decker, Fei Wang, Andrew A. Johnson, Brian K. Lee, Zachary Nado, D. Sculley, Tiark Rompf, and Alexander B. Wiltschko. Autograph: Imperative-style coding with graph-based performance. CoRR, abs/1810.08061, 2018. URL: http://arxiv.org/abs/1810.08061.
  20. Thomas Neumann. Efficiently compiling efficient query plans for modern hardware. Proc. VLDB Endow., 4(9):539-550, 2011. URL: https://doi.org/10.14778/2002938.2002940.
  21. Martin Odersky and Tiark Rompf. Unifying functional and object-oriented programming with scala. Commun. ACM, 57(4):76-86, 2014. URL: https://doi.org/10.1145/2591013.
  22. Shoumik Palkar, James J Thomas, Anil Shanbhag, Deepak Narayanan, Holger Pirk, Malte Schwarzkopf, Saman Amarasinghe, Matei Zaharia, and Stanford InfoLab. Weld: A common runtime for high performance data analytics. In Conference on Innovative Data Systems Research (CIDR), 2017. Google Scholar
  23. Pandas Cookbook Example. URL: https://nbviewer.jupyter.org/github/jvns/pandas-cookbook/tree/v0.1/cookbook/.
  24. Introducing Pandas UDF for PySpark. URL: https://databricks.com/blog/2017/10/30/introducing-vectorized-udfs-for-pyspark.html.
  25. Adam Paszke, Sam Gross, Soumith Chintala, and Gregory Chanan. Tensors and dynamic neural networks in python with strong gpu acceleration, 2017. Google Scholar
  26. Arvind K. Sujeeth, Kevin J. Brown, HyoukJoong Lee, Tiark Rompf, Hassan Chafi, Martin Odersky, and Kunle Olukotun. Delite: A compiler architecture for performance-oriented embedded domain-specific languages. ACM Trans. Embed. Comput. Syst., 13(4s):134:1-134:25, 2014. URL: https://doi.org/10.1145/2584665.
  27. Sebastian Ullrich and Leonardo de Moura. Counting immutable beans: Reference counting optimized for purely functional programming. CoRR, abs/1908.05647, 2019. URL: http://arxiv.org/abs/1908.05647.
  28. Stéfan van der Walt, S. Chris Colbert, and Gaël Varoquaux. The numpy array: A structure for efficient numerical computation. Comput. Sci. Eng., 13(2):22-30, 2011. URL: https://doi.org/10.1109/MCSE.2011.37.
  29. Philip Wadler. Deforestation: Transforming programs to eliminate trees. In Harald Ganzinger, editor, ESOP '88, 2nd European Symposium on Programming, Nancy, France, March 21-24, 1988, Proceedings, volume 300 of Lecture Notes in Computer Science, pages 344-358. Springer, 1988. URL: https://doi.org/10.1007/3-540-19027-9_23.
  30. WeldNumpy. URL: https://www.weld.rs/weldnumpy/.
  31. Matei Zaharia, Mosharaf Chowdhury, Michael J. Franklin, Scott Shenker, and Ion Stoica. Spark: Cluster computing with working sets. In Erich M. Nahum and Dongyan Xu, editors, 2nd USENIX Workshop on Hot Topics in Cloud Computing, HotCloud'10, Boston, MA, USA, June 22, 2010. USENIX Association, 2010. URL: https://www.usenix.org/conference/hotcloud-10/spark-cluster-computing-working-sets.
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