Trace-based Just-in-Time Type Specialization for Dynamic Languages

Andreas Gal, Brendan Eich, Mike Shaver, David Anderson, David Mandelin, 2009, PLDI

About this paper

This paper is under a licence that does not allow it to be reproduced, so what is here is its front matter and a short abstract. Read it at the publisher's page.

English
Tiếng Việt

Mozilla Corporation* {gal,brendan,shaver,danderson,dmandelin,mrbkap,graydon,bz,jorendorff,jruderman}@mozilla.com

Adobe Corporation# {edwsmith,rreitmai}@adobe.com

Intel Corporation\$ {mohammad.r.haghighat}@intel.com

University of California, Irvine+ {mbebenit,changm,franz}@uci.edu

Abstract

Dynamic languages such as JavaScript are more difficult to compile than statically typed ones. Since no concrete type information is available, traditional compilers need to emit generic code that can handle all possible type combinations at runtime. We present an alternative compilation technique for dynamically-typed languages that identifies frequently executed loop traces at run-time and then generates machine code on the fly that is specialized for the actual dynamic types occurring on each path through the loop. Our method provides cheap inter-procedural type specialization, and an elegant and efficient way of incrementally compiling lazily discovered alternative paths through nested loops. We have implemented a dynamic compiler for JavaScript based on our technique and we have measured speedups of 10x and more for certain benchmark programs.

Categories and Subject Descriptors D.3.4 [Programming Languages]: Processors — Incremental compilers, code generation.

General Terms Design, Experimentation, Measurement, Performance.

Keywords JavaScript, just-in-time compilation, trace trees.

Mozilla Corporation*

{gal,brendan,shaver,danderson,dmandelin,mrbkap,graydon,bz,jorendorff,jruderman}@mozilla.com

Adobe Corporation#

{edwsmith,rreitmai}@adobe.com

Intel Corporation\$

{mohammad.r.haghighat}@intel.com

University of California, Irvine+

{mbebenit,changm,franz}@uci.edu

Tóm tắt

Các ngôn ngữ động như JavaScript khó biên dịch hơn các ngôn ngữ có kiểu tĩnh. Vì không có thông tin kiểu cụ thể, các trình biên dịch truyền thống cần sinh ra mã tổng quát có thể xử lý mọi tổ hợp kiểu có thể xảy ra tại thời gian chạy. Chúng tôi trình bày một kỹ thuật biên dịch thay thế cho các ngôn ngữ có kiểu động, xác định các dấu vết vòng lặp được thực thi thường xuyên tại thời gian chạy và sau đó sinh mã máy ngay lập tức được chuyên biệt hóa cho các kiểu động thực tế xuất hiện trên mỗi đường đi qua vòng lặp. Phương pháp của chúng tôi cung cấp chuyên biệt hóa kiểu liên thủ tục với chi phí thấp, cùng với một cách thức thanh lịch và hiệu quả để biên dịch gia tăng các đường đi thay thế được phát hiện một cách lười biếng qua các vòng lặp lồng nhau. Chúng tôi đã triển khai một trình biên dịch động cho JavaScript dựa trên kỹ thuật của mình và đã đo được các mức tăng tốc 10x và cao hơn đối với một số chương trình phép đo chuẩn nhất định.

Các danh mục và mô tả chủ thể D.3.4 [Ngôn ngữ lập trình]: Bộ xử lý — Trình biên dịch gia tăng, sinh mã.

Các thuật ngữ chung Thiết kế, Thực nghiệm, Đo lường, Hiệu năng.

Từ khóa JavaScript, biên dịch đúng lúc, cây dấu vết.

  1. Giới thiệu

Các ngôn ngữ động như JavaScript, Python và Ruby phổ biến vì chúng giàu khả năng biểu đạt, dễ tiếp cận đối với người không chuyên, và giúp việc triển khai trở nên dễ dàng như phân phối một tệp mã nguồn. Chúng được sử dụng cho các tập lệnh nhỏ cũng như các ứng dụng phức tạp.

1 Introduction

This section is missing here.

2 Overview: Example Tracing Run

This section is missing here.

3 Trace Trees

This section is missing here.

Acknowledgments

This section is missing here.

References

  1. LuaJIT roadmap 2008 - http://lua-users.org/lists/lua-l/2008-02/msg00051.html.
  2. Mozilla — Firefox web browser and Thunderbird email client - http://www.mozilla.com.
  3. SPECJVM98 - http://www.spec.org/jvm98/.
  4. SpiderMonkey (JavaScript-C) Engine - http://www.mozilla.org/js/spidermonkey/.
  5. Surfin’ Safari - Blog Archive - Announcing SquirrelFish Extreme - http://webkit.org/blog/214/introducing-squirrelfish-extreme/.
  6. A. Aho, R. Sethi, J. Ullman, and M. Lam. Compilers: Principles, techniques, and tools, 2006.
  7. V. Bala, E. Duesterwald, and S. Banerjia. Dynamo: A transparent dynamic optimization system. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 1–12. ACM Press, 2000.
  8. M. Berndl, B. Vitale, M. Zaleski, and A. Brown. Context Threading: a Flexible and Efficient Dispatch Technique for Virtual Machine Interpreters. In Code Generation and Optimization, 2005. CGO 2005. International Symposium on, pages 15–26, 2005.
  9. C. Chambers and D. Ungar. Customization: Optimizing Compiler Technology for SELF, a Dynamically-Typed Object-Oriented Programming Language. In Proceedings of the ACM SIGPLAN 1989 Conference on Programming Language Design and Implementation, pages 146–160. ACM New York, NY, USA, 1989.
  10. A. Gal. Efficient Bytecode Verification and Compilation in a Virtual Machine Dissertation. PhD thesis, University Of California, Irvine, 2006.
  11. A. Gal, C. W. Probst, and M. Franz. HotpathVM: An effective JIT compiler for resource-constrained devices. In Proceedings of the International Conference on Virtual Execution Environments, pages 144–153. ACM Press, 2006.
  12. C. Garrett, J. Dean, D. Grove, and C. Chambers. Measurement and Application of Dynamic Receiver Class Distributions. 1994.
  13. J. Ha, M. R. Haghighat, S. Cong, and K. S. McKinley. A concurrent trace-based just-in-time compiler for javascript. Dept.of Computer Sciences, The University of Texas at Austin, TR-09-06, 2009.
  14. B. McCloskey. Personal communication.
  15. I. Piumarta and F. Riccardi. Optimizing direct threaded code by selective inlining. In Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, pages 291–300. ACM New York, NY, USA, 1998.
  16. A. Rigo. Representation-Based Just-In-time Specialization and the Psyco Prototype for Python. In PEPM, 2004.
  17. M. Salib. Starkiller: A Static Type Inferencer and Compiler for Python. In Master’s Thesis, 2004.
  18. T. Suganuma, T. Yasue, and T. Nakatani. A Region-Based Compilation Technique for Dynamic Compilers. ACM Transactions on Programming Languages and Systems (TOPLAS), 28(1):134–174, 2006.
  19. M. Zaleski, A. D. Brown, and K. Stoodley. YETI: A gradually Extensible Trace Interpreter. In Proceedings of the International Conference on Virtual Execution Environments, pages 83–93. ACM Press, 2007.

Read off the page by a vision model reading the page images using olmOCR-2-7B-1025-FP8.

Read off the page by a vision model reading the page images using olmOCR-2-7B-1025-FP8. Translated into Tiếng Việt by gpt-5, against glossary version 7. Translated from the English.