Speeding up function calls with just one line in Python

One line summary: Use lru_cache decorator

Caching

If we’re calling expensive functions in the program very frequently, It’s best to save the result of a function call and use it for future purposes rather than calling function every time. This will generally speed up the execution of the program.

The expensiveness of function can be in terms of computational (CPU usage) or latency (disk read, fetching a resource from the network).

The saving result of function calls is generally referred to as caching. The naive way to do caching is to store every function calls. But, this doesn’t scale very well with the number of parameters of function and range of each parameter.

So, we need a smart way to do caching with a fixed amount of memory. And, there are plenty of caching strategies available depending upon what type of information is available to us.

Caching is heavily used in plenty of areas from low-level (hardware/CPU) to high level (network/CDNs).

In most of the languages, We will choose caching strategies of our choice and implement them using a few data structures (hashmap, priority queue). Depending upon the language, It might take as little as few minutes to few hours to implement the generic solution of our need.

But, Python’s standard library functools already comes with one strategy of caching called LRU(Least Recently Used) . Thanks to decorators in python, It only takes one line to integrate into the existing codebase

Basic Recursive Implementation of Fibonacci numbers

import time as tt

def fib(n):
  if n <= 1:
    return n
  return fib(n-1) + fib(n-2)

t1 = tt.time()
fib(30)
print (f"Time taken: {tt.time() - t1}")

# Output : 
# Time taken: 0.3209421634674072

Speeding Up Recursive Implementation with LRU

import time as tt
import functools

# saving all function calls
@functools.lru_cache(maxsize=31)
def fib(n):
  if n <= 1:
    return n
  return fib(n-1) + fib(n-2)

t1 = tt.time()
fib(30)
print (f"Time taken: {tt.time() - t1}")
print (fib.cache_info())


# Output :
# Time taken: 1.7881393432617188e-05
# CacheInfo(hits=28, misses=31, maxsize=31, currsize=31)

In this example, we have saved all function calls. But, We know that Fibonacci can be implemented using DP .

Iterative implementation of Fibonacci

import time as tt

def fib_iterative(n):
  if n <= 1:
    return n
  f, s = 0, 1
  for i in range(n-1):
    t = f + s
    f, s = s, t
  return t

t1 = tt.time()
fib_iterative(30)
print (f"Time taken: {tt.time() - t1}")

# Output:
# Time taken: 5.0067901611328125e-06

Different Cache size

import time as tt
import functools

def lru_size(max_lru):
    @functools.lru_cache(maxsize=max_lru, typed=False)
    def fib_lru(n):
        if n <= 1:
            return n
        return fib_lru(n-1) + fib_lru(n-2)
    return fib_lru

for i in [1, 2, 5, 10, 31]:
    t1 = tt.time()
    fib = lru_size(i)
    fib(10)
    print (f"LRU size: {i} Time taken: {tt.time() - t1}")
    print (fib.cache_info())

# Output:
# LRU size: 1 Time taken: 0.6930997371673584
# CacheInfo(hits=0, misses=2692537, maxsize=1, currsize=1)
# LRU size: 2 Time taken: 0.012731075286865234
# CacheInfo(hits=8656, misses=41641, maxsize=2, currsize=2)
# LRU size: 5 Time taken: 5.817413330078125e-05
# CacheInfo(hits=28, misses=31, maxsize=5, currsize=5)
# LRU size: 10 Time taken: 3.9577484130859375e-05
# CacheInfo(hits=28, misses=31, maxsize=10, currsize=10)
# LRU size: 31 Time taken: 3.504753112792969e-05
# CacheInfo(hits=28, misses=31, maxsize=31, currsize=31)

As, we can see the optimal cache size of fib function is 5 . Increasing cache size will not result in much gain in terms of speedup.

Important Note

I strictly suggest to use lru decorator in only deterministic functions.

Deterministic Functions

In computer science, a deterministic algorithm is an algorithm which, given a particular input, will always produce the same output, with the underlying machine always passing through the same sequence of states. Deterministic algorithms are by far the most studied and familiar kind of algorithm, as well as one of the most practical, since they can be run on real machines efficiently.
– Wikipedia

Because,

There are only two hard things in Computer Science: cache invalidation and naming things.
– Phil Karlton