Python Patterns - An Optimization Anecdote

Abstraction: Iterative Python optimization from naive loop to 12x speedup

Key points:

• Naive string concatenation in a loop (f1) has O(N^2) behavior due to repeated allocation; for N=2048 it ran ~16x slower than for N=256
• Using map() with a built-in function (f3) was 2x faster than a for loop because chr() is looked up once and the inner loop runs in C
• Local variable lookup is much faster than global/built-in lookup; caching a built-in to a local gives ~40% speedup
• string.joinfields with map (f6) was 4-5x faster than f3 by using only implied loops implemented in C
• Winner (f7): array.array('B', list).tostring() was 12-15x faster than f3 and avoids quadratic behavior
• Key rules: use built-in functions, avoid lambdas in inner loops, prefer implied loops, check for quadratic behavior, profile first

Connections: Python · Performance Optimization · Python Internals

Source: https://www.python.org/doc/essays/list2str/