Native Run-time Performance for Dynamic Programming Languages

Updated: never

Presentation for the StrangeLoop conference Sep-Oct'21 (CFP talk submission, prospective)

Abstract

Much has been told about advantages and disadvantages of static vs dynamic type checking, without reaching a definitive conclusion. Being a low-budget project, the programming language MANOOL has to seek major conceptual economy, leading to a compact implementation. For instance, MANOOL is a homoiconic language (like Lisp or Tcl). On the other hand, its design and implementation simplicity is the most compelling reason for the dynamic typing choice.

Static type checking is often associated with languages that admit high-performance implementations (e.g., C or Java), but this does not always has to be the case. For instance, sophisticated dynamic specialization (e.g., in case of JavaScript/V8 or LuaJIT) bridges the performance gap between static and dynamic typing languages. Unfortunately, such techniques may be prohibitively expensive for a small project like MANOOL, while being still insufficient to reach the highest possible run-time performance (achievable for C/C++).

Despite of dynamic typing, MANOOL is specifically designed to admit effective static optimizations and thus, nearly native run-time performance. While not a new idea (e.g., Julia has the necessary properties for that), it seems that it has been underexplored so far in mainstream programming (and hopefully, MANOOL has a more general-purpose design than Julia).

You will learn about the overall architecture of MANOOL and its compiler, the intermediate representations, the sources of inefficiencies in high-level dynamic languages (including the dynamic typing), and how they can be overcome. No prior knowledge of modern compiler technology is required.

About the presenter

Alexey Protasov

Alex is an enthusiastic independent developer with Russian origins living in Medellin, Colombia. He constantly dreams with “better” programming languages and has over 30 years of experience with designing and implementing languages and development tools — he offered in the past a shareware visual programming tool, worked in the area of compilers at Intel and Sun Microsystems, and taught compiler construction and the theory of formal languages at a university.

Alex speaks Spanish, English, and Russian. When he is not working on programming languages, he likes swimming, traveling, and dancing (Salsa, Porro, Merengue, Cumbia, etc.).

What will the attendee learn? — Comments for reviewers

Presentation outline

• Introduction
  • About the author, the current status of MANOOL, references and contact details
  • When run-time performance of a language implementation is relevant and when it is not
  • Own middle-end/back-end rationale (why not just using LLVM)
• Language and compiler architecture
  • Scanner and parser
  • The compiler core dispatcher
  • Optimization and code generation pipeline
  • Object module linker/loader (for separate compilation)
• Intermediate representations
  • Abstract syntax tree
  • Compiled tree representation
  • Register machine
  • Object modules (persistent cache thereof)
• Sources of inefficiencies in high-level dynamic languages
  • Run-time dispatch by type (AKA dynamic overloading in MANOOL), run-time type checking
  • Run-time specification of polymorphic operations and composite member names (in case of MANOOL)
  • Value (un)boxing (pointer dereferencing), tracing GC or reference counting, run-time memory allocation (from heap)
  • General redundancies that can be eliminated by seeing through abstraction boundaries and applying static code specialization
• Overcoming the inefficiencies during design of a dynamic language
  • Homogeneous composite data
  • Procedure inlining and explicit precondition checking in monomorphic and polymorphic cases
  • Value (copy-on-write) and move semantics (in case of MANOOL)
• Middle-end overview (analysis and transformations)
  • Converting to SSA (static single assignment form), to enable advanced data and control flow analysis (especially IPSCCP)
  • Interprocedural conditional constant propagation (more complete than in LLVM), inlining, constant folding, type inference as IPSCCP
  • Constraints on procedure specialization (or inlining)
  • Copy propagation, dead code elimination (including unused and unreachable code)
  • Jump/branching optimizations (basic block merging and jump threading)
  • Elimination of redundant loads/stores, reference counter increments/decrements, and heap memory allocations/deallocations
  • Other analysis/transformations (GVN, CSE, PRE, invariant code motion, strength reduction, loop unrolling, autovectorization, etc.)
• Back-end overview (machine code generation)
  • Converting out of SSA, register allocation
  • Instruction selection, peephole optimizations, etc.
• Example (Conway's Game of Life)
  • Source code in MANOOL
  • Discussion of applicable optimizations and run-time performance
• Conclusions + Questions & Answers