A few simple ways to achieve 1.3x to 970x speedup of Python for loops with minimal effort.

dummy-image.png
Image generated using DALL·E 3

Quantifying Performance Improvements

A commonly used functionality built into Python is the timeit module. It has a Python interface as well as a command-line interface. The code snippets used below use the former to measure the current and improved performance of loops.

For each approach, first, a baseline is established by running a test which involves running the function under test 100K times (loops) over 10 test runs and then calculating the average time per loop (measured in nanoseconds, ns). More details here.

A Few Simple Ways

A few simple ways to speedup Python loops.

#1 List Comprehension

The humble List Comprehension

# Baseline version (Inefficient way)
# Calculating the power of numbers
# Without using List Comprehension
def test_01_v0(numbers):
  output = []
  for n in numbers:
      output.append(n ** 2.5)
  return output

# Improved version
# (Using List Comprehension)
def test_01_v1(numbers):
  return [n ** 2.5 for n in numbers]

Potential performance improvement using List Comprehension: 2.4x speedup

     Baseline: 31.486 ns per loop
     Improved: 13.019 ns per loop
% Improvement: 58.7 %
      Speedup: 2.42x

#2 Calculate Outside Loop

If you need to rely on the length of a list to iterate over, calculate outside the for loop.

# Baseline version (Inefficient way)
# (Length calculation inside the for loop)
def test_02_v0(numbers):
  output_list = []
  for i in range(len(numbers)):
    output_list.append(i * 2)
  return output_list

# Improved version
# (Length calculation outside the for loop)
def test_02_v1(numbers):
  my_list_length = len(numbers)
  output_list = []
  for i in range(my_list_length):
    output_list.append(i * 2)
  return output_list

Potential performance improvement that can be achieved just by moving list length calculation outside the for loop: 1.6x speedup

     Baseline: 112.135 ns per loop
     Improved:  68.304 ns per loop
% Improvement: 39.1 %
      Speedup: 1.64x

#3 Use Sets

Use sets for scenarios you’d otherwise use for loops for comparisons.

# Use for loops for nested lookups
def test_03_v0(list_1, list_2):
  # Baseline version (Inefficient way)
  # (nested lookups using for loop)
  common_items = []
  for item in list_1:
      if item in list_2:
          common_items.append(item)
  return common_items

def test_03_v1(list_1, list_2):
  # Improved version
  # (use sets to replace the nested lookups)
  set_1 = set(list_1)
  set_2 = set(list_2)
  common_items = set_1.intersection(set_2)
  return common_items

Potential performance improvement that can be achieved by using sets for scenarios you’d otherwise use nested for loops for comparisons: 498x speedup

     Baseline: 9047.078 ns per loop
     Improved:   18.161 ns per loop
% Improvement: 99.8 %
      Speedup: 498.17x

#4 Skip Irrelevant

Avoid redundant computations, i.e. skip irrelevant iterations.

# Example of inefficient code used to find the first even square in a list of numbers
def function_do_something(numbers):
  for n in numbers:
    square = n * n
    if square % 2 == 0:
        return square

  return None  # No even square found

# Example of improved code that finds result without redundant computations
def function_do_something_v1(numbers):
  even_numbers = [n for n in numbers if n%2==0]
  for n in even_numbers:
    square = n * n
    return square

  return None  # No even square found

Potential performance improvement that can be achieved by avoiding redundant computations, i.e. skipping irrelevant iterations: 1.9x speedup

     Baseline: 16.912 ns per loop
     Improved:  8.697 ns per loop
% Improvement: 48.6 %
      Speedup: 1.94x

#5 Refactor Functions

In certain cases, directly incorporating the code of simple functions into loops can improve code compactness and execution speed.

# Example of inefficient code
# Loop that calls the is_prime function n times.
def is_prime(n):
  if n <= 1:
    return False
  for i in range(2, int(n**0.5) + 1):
    if n % i == 0:
      return False

  return True

def test_05_v0(n):
  # Baseline version (Inefficient way)
  # (calls the is_prime function n times)
  count = 0
  for i in range(2, n + 1):
    if is_prime(i):
      count += 1
  return count

def test_05_v1(n):
  # Improved version
  # (inlines the logic of the is_prime function)
  count = 0
  for i in range(2, n + 1):
    if i <= 1:
      continue
    for j in range(2, int(i**0.5) + 1):
      if i % j == 0:
        break
    else:
      count += 1
  return count

Potential performance improvement that can be achieved by directly incorporating the code of simple functions into loops: 1.3x speedup

     Baseline: 1271.188 ns per loop
     Improved:  939.603 ns per loop
% Improvement: 26.1 %
      Speedup: 1.35x

Key Takeaway

  • Calling a function involves overhead, such as pushing and popping variables on the stack, function lookup, and argument passing.
  • When a simple function is called repeatedly within a loop, the overhead of function calls can add up and impact performance.
  • Inlining the function’s code directly into the loop can eliminate this overhead, potentially leading to significant speedups.

"premature optimization is the root of all evil"
Sir Tony Hoare (popularized by Donald Knuth)

⚠️ Caution: Balance the need for code readability vs the frequency at which the function is called.

#6 Avoid Pointless Checks

Where possible, avoid pointless checks, some of which might be redundant and slow down your code. For example,

for v in list_of_values:
  if v > 0:
    # Do something for values greater than zero
  if v != 0:
    # Do something for non-zero values

💸 The second if statement (if v != 0:) is redundant because it will always execute for any value that passes the first if statement (if v > 0:). This means the code within the second if block will always run whenever the code within the first if block runs.

A more complete example to help prove the point.

def test_06_v0(numbers):
  # Example of inefficient code
  # (Redundant checks, duplicate work, buggy output)
  output = []
  for v in numbers:
    if v > 0:
      output.append(v*2)
    if v != 0:  # Redundant check
      output.append(v*2)
  
  return output

def test_06_v1(numbers):
  # Improved version
  # (Remove redundant checks, no duplicate work, bug free)
  return [num*2 for num in numbers if num > 0]

Potential performance improvement that can be achieved by avoiding pointless checks: 1.9x speedup

     Baseline: 133.312 ns per loop
     Improved: 67.379 ns per loop
% Improvement: 49.5 %
      Speedup: 1.98x

Being Lazy Can Be Good

#7 Avoid Repeats

Consider avoiding repetitive calculations, some of which might be redundant and slow down your code. Instead, consider precomputation(s), where applicable.

An example to help prove the point.

def test_07_v0(n):
  # Example of inefficient code
  # Repetitive calculation within nested loop
  result = 0
  for i in range(n):
    for j in range(n):
      result += i * j
  return result

def test_07_v1(n):
  # Example of improved code
  # Utilize precomputed values to help speedup
  pv = [[i * j for j in range(n)] for i in range(n)]
  result = 0
  for i in range(n):
    result += sum(pv[i][:i+1])
  return result

Potential performance improvement that can be achieved by avoiding repetitive calculations: 1.5x speedup

     Baseline: 139.146 ns per loop
     Improved:  92.325 ns per loop
% Improvement: 33.6 %
      Speedup: 1.51x

#8 Use Generators

Consider using generators.

  • Generators enable lazy evaluation, i.e. the expressions inside are only evaluated when you request the next value from it.
  • This allows the processing of large datasets without loading everything into memory at once, which would otherwise have caused performance issues.
  • Processing data on the fly helps reduce memory usage and improve performance.
def test_08_v0(n):
  # Baseline version (Inefficient way)
  # (Inefficiently calculates the nth Fibonacci
  # number using a list)
  if n <= 1:
    return n
  f_list = [0, 1]
  for i in range(2, n + 1):
    f_list.append(f_list[i - 1] + f_list[i - 2])
  return f_list[n]

def test_08_v1(n):
  # Improved version
  # (Efficiently calculates the nth Fibonacci
  # number using a generator)
  a, b = 0, 1
  for _ in range(n):
    yield a
    a, b = b, a + b

Potential performance improvement that can be achieved by using generators: 22x speedup

     Baseline: 0.083 ns per loop
     Improved: 0.004 ns per loop
% Improvement: 95.5 %
      Speedup: 22.06x

A Few Interesting Ways

#9 Use map()

Use Python’s built-in map() function.

This function allows the processing and transformation of all items in an iterable without using an explicit for loop. This technique is referred to as mapping.

An example to help prove the point.

def some_function_X(x):
  # This would normally be a function containing application logic which
  # required it to be made into a separate function
  # (for the purpose of this test, just calculate and return the square)
  return x**2

def test_09_v0(numbers):
  # Baseline version (Inefficient way)
  output = []
  for i in numbers:
    output.append(some_function_X(i))

  return output

def test_09_v1(numbers):
  # Improved version
  # (Using Python's built-in map() function)
  output = map(some_function_X, numbers)
  return output

Potential performance improvement using Python’s built-in map() function instead of an explicit for loop: 970x speedup

     Baseline: 4.402 ns per loop
     Improved: 0.005 ns per loop
% Improvement: 99.9 %
      Speedup: 970.69x

How Does It Work?

The map() function takes a function object and an iterable as arguments and returns an iterator that yields transformed items on demand. What it does is that it (the map() function) applies the function (passed as the first argument) to each item in the iterable in a loop and returns a new iterator that yields transformed items on demand. Since the map() function is written in C and is highly optimized, its internal implied loop is a lot more efficient than a regular Python for loop. Hence the speed gains.
– Paraphrased from the explanation at [#5]

#10 Use Memoization

Memoization optimises algorithms with recursive function calls or repeated calculations. The idea is to cache (or “memoize”) the results of expensive function calls and return them when the same inputs appear. It can reduce redundant calculations and speed up the program.

An example to help prove the point. First, an inefficient version of the code.

# Example of inefficient code
def fibonacci(n):
  if n == 0 or n == 1:
    return n
  return fibonacci(n - 1) + fibonacci(n-2)

def test_10_v0(list_of_numbers):
  output = []
  for i in numbers:
    output.append(fibonacci(i))

  return output

Next, an efficient version of the same functionality, but using Python’s built-in functools’ lru_cache function.

# Example of efficient code
# Using Python's functools' lru_cache function
import functools

@functools.lru_cache()
def fibonacci_v2(n):
  if n == 0:
    return 0
  elif n == 1:
    return 1
  return fibonacci_v2(n - 1) + fibonacci_v2(n-2)

def _test_10_v1(numbers):
  output = []
  for i in numbers:
    output.append(fibonacci_v2(i))

  return output

Potential performance improvement using Memoization using Python’s built-in functools’ lru_cache function: 59x speedup

     Baseline: 77.908 ns per loop
     Improved: 1.310 ns per loop
% Improvement: 98.3 %
      Speedup: 59.48x

How Does The lru_cache Function Make This Happen?

  • “LRU” is the acronym for “Least Recently Used”.
  • The lru_cache function is a decorator which can be applied to functions to enable memoization.
  • The lru_cache stores the results of recent function calls in a cache and can serve the cached result when the same inputs occur again, thus saving computation time.
  • The lru_cache function, when applied as a decorator, allows for an optional maxsize argument like so: @lru_cache(maxsize=None). The maxsize argument determines the maximum size of the cache (i.e., how many different input values it stores results for). [#6]
    • If the maxsize argument is set to None, the LRU feature is disabled, and the cache can grow without bound. 🚨

#11 Use Vectorization

An example to help prove the point.

import numpy as np

def test_11_v0(n):
  # Baseline version
  # (Inefficient way of summing numbers in a range)
  output = 0
  for i in range(0, n):
    output = output + i

  return output

def test_11_v1(n):
  # Improved version
  # (# Efficient way of summing numbers in a range)
  output = np.sum(np.arange(n))
  return output

Potential performance improvement using Vectorization : 28x speedup

     Baseline: 32.936 ns per loop
     Improved:  1.171 ns per loop
% Improvement: 96.4 %
      Speedup: 28.13x

#12 Use filterfalse

Avoid creating intermediate lists. It helps use less memory.

An example to help prove the point.

def test_12_v0(numbers):
  # Baseline version (Inefficient way)
  filtered_data = []
  for i in numbers:
    filtered_data.extend(list(
        filter(lambda x: x % 5 == 0,
                range(1, i**2))))
  
  return filtered_data

Next, an improved version of the same functionality using Python’s built-in itertools’ filterfalse function [#7].

from itertools import filterfalse

def test_12_v1(numbers):
  # Improved version
  # (using filterfalse)
  filtered_data = []
  for i in numbers:
    filtered_data.extend(list(
        filterfalse(lambda x: x % 5 != 0,
                    range(1, i**2))))
    
    return filtered_data

Depending on the use case, whilst there might not be a significant increase in the speed of execution, there would be a drop in the memory usage achieved by avoiding the creation of intermediate lists.

the filterfalse function of itertools helps avoid creating an intermediate list [#2]

Potential performance improvement using the filterfalse function of itertools : 131x speedup

     Baseline: 333167.790 ns per loop
     Improved: 2541.850 ns per loop
% Improvement: 99.2 %
      Speedup: 131.07x

#13 Proper Way To Concatenate Strings

Any string concatenation operation using the + operator will be slow and consume more memory. Use join instead.

An example to help prove the point.


def test_13_v0(l_strings):
  # Baseline version (Inefficient way)
  # (use concatenation inside the for loop)
  output = ""
  for a_str in l_strings:
    output += a_str

  return output

def test_13_v1(l_strings):
  # Improved version
  # (using join)
  output_list = []
  for a_str in l_strings:
    output_list.append(a_str)

  return "".join(output_list)

Since this test will require an easy way to generate a large-ish list of strings, here’s a simple helper function to generate the required list of strings for the purpose of running the tests.

from faker import Faker

def generate_fake_names(count : int=10000):
  # Helper function used to generate a large-ish list of names
  fake = Faker()
  output_list = []
  for _ in range(count):
    output_list.append(fake.name())
  return output_list

l_strings = generate_fake_names(count=50000)

Potential performance improvement using the join function instead using the + operator : 1.5x speedup

     Baseline: 32.423 ns per loop
     Improved: 21.051 ns per loop
% Improvement: 35.1 %
      Speedup: 1.54x

Why is the join function faster? The string concatenation operation using the + operator has a time complexity of O(n²), whereas the string concatenation operation using the join function has a time complexity of O(n). [#8]

TL;DR

A few simple ways to achieve 1.3x to 970x speedup of Python for loops with minimal effort.

  • 970x speedup using Python’s built-in map() function instead of an explicit for loop [details]
  • 498x speedup using sets instead of nested for loops for comparisons [details]
  • 131x speedup using the filterfalse function of itertools [details]
  • 57x speedup using Memoization using lru_cache function of functools[details]

👨🏻‍💻 All code samples can be replicated via this Google Colab notebook. Due to external factors, the numbers may differ when you run the notebook.

References

  1. timeit() Python Function Usage Guide (With Examples) (Aug, 2023)
  2. 15 Techniques to Optimize Python Code (Apr, 2023)
  3. Vectorization in Python- An Alternative to Python Loops (Mar, 2023)
  4. Loops in Python – Comparison and Performance (Aug, 2019)
  5. Python’s map(): Processing Iterables Without a Loop
  6. Python’s built-in functools’ lru_cache function
  7. Python’s built-in itertools’ filterfalse function
  8. Time complexity of string concatenation in Python (May, 2016)