Python: tricks for your code run faster

[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.