Python Optimization

Optimization

Table of Contents

1. Where to optimize
2. for loops
   1. List Comprehensions
   2. Iterators
   3. Vectors
3. List Lookups
4. Assertions

Introduction

While RAVEN takes great advantage of the power and flexibility of Python, sometimes the most efficient methods in Python are unintuitive. To that end, we gather here a list of suggestions for rapid development.

If you find additional tips, let us know!

Where to optimize

In general, python is quite efficient and it is seldom worth spending significant time optimizing every line of code. However, there are a few instances where optimization is very worthwhile:

• A line of code could be evaluated millions of times per RAVEN run,
• A line of code is in the serial portions of a RAVEN run, instead of the parallel portion.

In these cases, it may be worth trying to improve the speed of the code.

for loops

In general, loops in Python are quite slow, and most optimization techniques revolve around avoiding them. Any time operations can be done in vectors or without looping they should be. Here are some ways to mitigate looping.

List Comprehensions

If we want to populate a list with items, we might be tempted to use an algorithm such as the following:

a = []
for x in range(100):
  a.append(x)
# time: 1.307e-5

Obviously this specific code is poor and not very useful; however, the same structure is seen frequently. On a particular test machine, averaging over 100,000 samples, this code took 1.307e-5 seconds per evaluation. Using list comprehensions, instead, we could do

a = list(x for x in range(100))
# time: 1.286e-6

On the same test machine, averaging over 100,000 samples, this code took 1.286e-6 seconds per evaluation, or roughly an order of magnitude improvement in speed.

Iterators

Furthermore, if a list is being constructed only for iterating over, an iterator is faster than an actual list, as it doesn't evaluate until it is needed. Keeping with our previous example, consider the following:

a = list(x for x in range(100))
for x in a:
  print x
# time: 3.230e-4

versus

a = (x for x in range(100))
for x in a:
  print x
# time: 3.194e-4

Again, not particularly useful code, but the pattern gets used. On the same test machine, the first took 3.230e-4 seconds, while the second took 3.194e-4 seconds. This saves less time than comprehensions, but does save on memory as well.

Vector Operations

If we want to find the element-wise product of two lists, we might try

a = range(1,1001)
b = range(1000,2000)
c = list(a[i]*b[i] for i in range(len(a)))
# time: 1.406e-4

Using numpy arrays,

import numpy as np
a = np.arange(1,1001)
b = np.arange(1000,2000)
c = a*b
# time: 4.81e-6

For vector or matrix operations of floats, numpy methods tend to be far superior to python loops.

List lookups

While in small dictionaries the lookup if key in myDict.keys() looks innocuous, it is rather expensive to look up the key. One option is to store the lookup as sorted tuples and use the bisect algorithm. For example, searching the list keys for the entry find:

keys = itertools.product('abcd',repeat=10) #creates all combinations of these letters in 10-letter words, sorted
find = 'c'*10 # 'cccccccccc'

Naively,

if find in keys:
  print 'yes'
# time: 8.048e-3 seconds

Using bisect,

i = bisect.bisect_left(keys,find)
if i != len(keys) and keys[i] == find:
  print 'yes'
# time: 1.044e-6 seconds

However, bisect only works on sorted lists.

Assertions

Python natively uses assert statements to check boolean evaluations that are necessary when developing or debugging, but not necessary during run time. For example:

if True: pass
# time: 7.701e-8 seconds

assert(True)
# time: 5.984e-8 seconds

Furthermore, running Python with the -O option erases these assertion statements,

# using "python -O test.py"
assert(True)
# time: 3.600e-8 seconds

By default, running raven_framework uses the -O option. This is the expected run for RAVEN users. For developers, however, assert statements can help debug development. To run RAVEN in debug mode, pass the -D flag to raven_framework, as

raven_framework -D test.py