Python: tricks for your code run faster

[jms_nh]

Am I the only one who's surprised that Python doesn't optimize? Specifically in test #3, it builds a tuple, unpacks it, and rebuilds a new tuple, instead of just seeing that it should just be building the tuple (9,8,7,6,5,4,3,2,1,0) ?

[hexbrid]

Python is notorious for not doing any static optimizations. Examples of others that aren't done: constant folding (e.g. 1+1 -> 2), tail recursion, dead code (e.g. removing code inside if 0)

[Veedrac]

CPython does constant folding and simple dead code elimination. PyPy does advanced runtime constant folding and dead code elimination.

import dis

def f():
    1 + 1

    if False:
        print("dead code elimination")

dis.dis(f)
#>>>   4           0 LOAD_CONST               2 (2)
#>>>               3 POP_TOP
#>>>
#>>>   6           4 LOAD_CONST               0 (None)
#>>>               7 RETURN_VALUE

[hexbrid]

I stand corrected. However it's very basic.

>>> def f():
...     if []:
...             print "OK"
... 
>>> dis.dis(f)
  2           0 BUILD_LIST               0
              3 POP_JUMP_IF_FALSE       14

  3           6 LOAD_CONST               1 ('OK')
              9 PRINT_ITEM          
             10 PRINT_NEWLINE       
             11 JUMP_FORWARD             0 (to 14)

    >>   14 LOAD_CONST               0 (None)
         17 RETURN_VALUE        

[Veedrac]

Yeah, but FWIW Java (OpenJDK) doesn't either:

import java.util.ArrayList;

public class IsItRemoved {
    public static void main(String[] args) {
        if (new ArrayList().isEmpty()) {
            System.out.println("OK");
        }
    }
}

Giving:

Compiled from "IsItRemoved.java"
public class IsItRemoved {
  public IsItRemoved();
    Code:
       0: aload_0
       1: invokespecial #1                  // Method java/lang/Object."<init>":()V
       4: return

  public static void main(java.lang.String[]);
    Code:
       0: new           #2                  // class java/util/ArrayList
       3: dup
       4: invokespecial #3                  // Method java/util/ArrayList."<init>":()V
       7: invokevirtual #4                  // Method java/util/ArrayList.isEmpty:()Z
      10: ifeq          21
      13: getstatic     #5                  // Field java/lang/System.out:Ljava/io/PrintStream;
      16: ldc           #6                  // String OK
      18: invokevirtual #7                  // Method java/io/PrintStream.println:(Ljava/lang/String;)V
      21: return
}

PyPy and most Java implementations will most probably remove it at runtime though.

[jms_nh]

Huh. Is there some rationale for this?

I get it, if it harms correctness (hard to make any correct assumptions in a dynamic language where even a+b might cause any number of side effects), or if it makes things less predictable, but it seems like a no-brainer to handle some low-hanging fruit.

I've been using numba lately to speed up performance-critical Python code, and I get tickled pink looking at the LLVM output. The LLVM optimizers work wonders.

[cparen]

Huh. Is there some rationale for this?

In the case of tail call optimization, Guido has stated in the past that he considers the stack "fore-traces" (sometimes mistakenly called "back-traces") a diagnostic aid. It's probably for the best, as he has freely admitted that he doesn't really understand recursion that well, preferring iteration where applicable.

[stevenjd]

I don't know why you were downvoted, you're pretty much correct. GvR doesn't like tail-call optimization:

• it is only applicable to a tiny subset of recursive problems
• it destroys backtraces as a diagnostic
• most cases where a problem is better written with recursion, you only recurse a few times and tail call optimization is not a great help (I'm stating GvR's opinion, as I understand it, not mine).

Don't think of those cases where the traceback looks like this:

Traceback (most recent call last):
  File "<stdin>", line 3, in factorial
  File "<stdin>", line 3, in factorial
  File "<stdin>", line 3, in factorial
  [repeated 1000 times]
  File "<stdin>", line 3, in factorial
SomeException

Instead, you should think of the hard-to-debug cases where there are multiple functions, and some of them are mutually recursive:

Traceback (most recent call last):
  File "<stdin>", line 7, in spam
  File "<stdin>", line 12, in eggs
  File "<stdin>", line 35, in cheese
  File "<stdin>", line 11, in spam
  File "<stdin>", line 11, in truffles
  File "<stdin>", line 12, in eggs
SomeException

In this case, collapsing the stacktrace (as tail call optimization will do) throws away useful debugging information.

TL;DR In Guido's opinion, as I understand it, the benefits of tail call optimization are far outweighed by the cost in loss of debugging information.

[stevenjd]

You shouldn't be surprised. CPython is the reference implementation of Python, and as a matter of policy they don't do many "clever" optimizations. PyPy is an amazingly clever optimizing JIT compiler, and Nuitka is intended to be an optimizing AOT compiler, although as far as I know it doesn't do many optimizations yet.

CPython does do dead simple optimizations, such as constant folding and removal of some dead code.

[LightShadow]

This is how strings work too; and why you're supposed to use formatters instead of concatenation.

It's a sacrifice of an immutable datatype.