English: arpitbhayani me/blogs/const…

Author: arprit

The cat under the Pea Flower

Note: This translation is for the purpose of communication and learning, based on CC BY-NC-SA 4.0 license agreement. The content has been changed slightly for ease of reading.

Every programming language needs a lot of compiler-level optimization in order to perform well and achieve great performance.

A well-known optimization technique is’ Constant Folding ‘: At compile time, the compiler tries to recognize a Constant expression, evaluate it, and then replace the expression with the result of evaluation, resulting in a leaner runtime.

In this article, we took a closer look at what constant folding is, learned about its applicability in the Python world, and finally looked at the Python source code (CPython) and how Python gracefully implements it.

Constant folding

Constant folding means that constant expressions are found and evaluated at compile time, rather than evaluated at run time, making the run time leaner and faster.

>>> day_sec = 24 * 60 * 60
Copy the code

When the compiler encounters a constant expression, as described above, it evaluates the expression and makes the substitution.

In general, expressions are replaced by computed values in the Abstract Syntax Tree (AST), but this entirely depends on the implementation of the language.

Therefore, the above expression can be executed equivalently as:

>>> day_sec = 86400
Copy the code

Constant folding in Python

In Python, we can use the Disassembler module to get CPython bytecode to better understand the process of code execution.

When disassembling the above constant expression using the DIS module, we get the following bytecode:

>>> import dis
>>> dis.dis("day_sec = 24 * 60 * 60")

        0 LOAD_CONST               0 (86400)
        2 STORE_NAME               0 (day_sec)
        4 LOAD_CONST               1 (None)
        6 RETURN_VALUE
Copy the code

As you can see from the bytecode, it has only one LOAD_CONST and a calculated value of 86400.

This indicates that the CPython interpreter collapses the constant expression 24 * 60 * 60 and replaces it with the computed value 86400 during parsing and building the abstract syntax tree.

The adaptive range of constant folding

Python tries to fold every constant expression, but in some cases, Python does not fold even if the expression is constant.

For example, Python will not fold x = 4 ** 64, but will fold x = 2 ** 64.

In addition to arithmetic expressions, Python also folds expressions involving strings and tuples, where string constant expressions of length up to 4096 are folded.

>>> a = "-" * 4096   # folded
>>> a = "-" * 4097   # not folded
>>> a = "--" * 4096  # not folded
Copy the code

Interior details of a constant fold

For now, let’s move on to the internal implementation details, focusing on where and how CPython implements constant folding.

All AST optimizations, including constant folding, can be found in the ast_opt.c file. The basic start function is astfold_expr, which collapses all expressions contained in Python source code.

This function iterates recursively through the AST and tries to collapse each constant expression, as shown in the following code snippet:

Astfold_expr tries to collapse its subexpressions (action objects) before collapsing an expression, and then proxies the collapse to a specific expression collapse function.

The collapse function for a particular operation evaluates the expression and returns the calculated constant, which is then put into the AST.

For example, whenever Astfold_expr encounters a binary operation, it calls fold_binop to recursively evaluate two subexpression objects (expressions).

The fold_binop function returns the computed constant value, as shown in the following code snippet:

The fold_binop function folds binary operations by checking the type of the current operator and then calling its corresponding handler. For example, if the current operation is an addition operation, it calls PyNumber_Add on its left and right operands to calculate the final value.

How elegant?

To efficiently fold constant expressions of certain patterns or types, CPython does not write special logic, but instead calls the same generic code. For example, when folding, it calls the generic PyNumber_Add function, just as it does regular addition.

Therefore, CPython eliminates the need to write special functions to handle constant folding by ensuring that its generic code/evaluation procedures can handle constant expression evaluation.

Reference material

  • Constant folding (en.wikipedia.org/wiki/Consta…).
  • Retaining optimization (stummjr.org/post/cpytho…).
  • Python dis module and constant folding (yasoob.me/2019/02/26/…)
  • CPython simple way to implement constant folding (utcc.utoronto.ca/~ CKS /space/…)
  • AST constant folding optimization process (bugs.python.org/issue134623…).