PythonMastery
advanced 18 min read · lesson 7 of 9 in Python Advanced

Performance: Profile, Then Optimise

1 · The lesson

read

Most Python performance work goes wrong before the first edit, because someone guessed where the slow part was. Suppose you look at a 2000-line module and feel sure that the slow part is parse_row. You can spend an afternoon rewriting parse_row in C, and then discover that the real cost was a single SELECT * two functions earlier.

This lesson teaches the habit of measuring first. It covers the tools (timeit, cProfile, pstats, tracemalloc, dis), the changes that make a real difference, and the cases where pure Python is the wrong tool and you should use numpy, numba, or multiprocessing.

1. The Rule: Measure First

"Premature optimisation is the root of all evil." — Knuth (full quote includes "about 97% of the time").

The 3% that matters is real. In the other 97%, engineers can waste weeks rewriting code that was never slow. The only way to know whether you are in the 3% is to profile.

Three questions, in order, before you change a single line:

1. Is it really slow? Measure how long the workload takes in real time. If a nightly job takes 8s and nobody notices, leave it.
2. Where is the time going? Profile. Find the function (or line) responsible for the bulk of the time.
3. What's the algorithm? A big-O improvement is almost always worth more than a 2× micro-optimisation.

Only after those three questions should you try the small code-level speedups in Section 10.

2. timeit: Microbenchmarking a Snippet

timeit runs a small piece of code many times and reports the total time. Running it many times reduces the effect of random OS delays, GC pauses, and the slower first run (when caches are still empty).

python
import timeit

# Compare two ways to build a list of squares
t_loop = timeit.timeit("out = []\nfor x in range(1000):\n    out.append(x*x)",
                       number=10_000)
t_comp = timeit.timeit("[x*x for x in range(1000)]", number=10_000)

print(f"loop:        {t_loop:.3f}s")
print(f"comp:        {t_comp:.3f}s")
print(f"speedup:     {t_loop / t_comp:.2f}x")

In IPython or a Jupyter notebook, the same job is one line:

python
%timeit [x*x for x in range(1000)]
# 18.4 µs ± 120 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

%timeit chooses the loop count automatically and reports the mean and standard deviation, which is a good default for quick measurements. Use timeit.timeit (or timeit.repeat, and take the minimum) when you want to write the comparison as a script.

One pitfall: timeit runs your snippet in its own namespace. Pass setup code via the setup= argument, not by relying on globals:

python
timeit.timeit("sorted(data)", setup="import random; data = [random.random() for _ in range(1000)]",
              number=1000)
+ setup added so this can run · re-runs 1 earlier block on this page first
# Lightweight mock for objects whose attributes/methods aren't critical
class _AutoMock:
    def __init__(self, name='mock'): self._name = name
    def __getattr__(self, k): return _AutoMock(self._name + '.' + k)
    def __call__(self, *a, **kw):
        print('-> ' + self._name + '() called')
        return _AutoMock(self._name + '()')
    def __repr__(self): return '<mock ' + self._name + '>'
    def __str__(self): return '<mock ' + self._name + '>'
    def __bool__(self): return True
    def __iter__(self): return iter([])
    def __len__(self): return 0
    def __getitem__(self, k): return _AutoMock(self._name + '[...]')
    def __setitem__(self, k, v): pass
    def __enter__(self): return self
    def __exit__(self, *a): return False
    async def __aenter__(self): return self
    async def __aexit__(self, *a): return False
    def __add__(self, o): return self
    def __radd__(self, o): return self
    def __sub__(self, o): return self
    def __mul__(self, o): return self
    def __rmul__(self, o): return self
    def __truediv__(self, o): return self
    def __eq__(self, o): return isinstance(o, _AutoMock)
    def __hash__(self): return hash(self._name)
    def __lt__(self, o): return True
    def __le__(self, o): return True
    def __gt__(self, o): return False
    def __ge__(self, o): return False
    def __mro_entries__(self, bases): return (object,)

timeit = _AutoMock('timeit')

# Earlier blocks on this page that this one builds on, re-run quietly first.
try:
    import timeit
except Exception:
    pass
_pm_earlier = [
    'import timeit\n\n# Compare two ways to build a list of squares\nt_loop = timeit.timeit("out = []\\nfor x in range(1000):\\n    out.append(x*x)",\n                       number=10_000)\nt_comp = timeit.timeit("[x*x for x in range(1000)]", number=10_000)\n\nprint(f"loop:        {t_loop:.3f}s")\nprint(f"comp:        {t_comp:.3f}s")\nprint(f"speedup:     {t_loop / t_comp:.2f}x")',
]
def _pm_run_earlier(_srcs, _g):
    import sys as _s, io as _io, warnings as _w
    for _src in _srcs:
        _o, _e = _s.stdout, _s.stderr
        _s.stdout = _s.stderr = _io.StringIO()
        try:
            with _w.catch_warnings():
                _w.simplefilter('ignore')
                exec(compile(_src, '<earlier block>', 'exec'), _g)
        except (Exception, SystemExit):
            pass
        finally:
            _s.stdout, _s.stderr = _o, _e
    if 'matplotlib.pyplot' in _s.modules:
        _s.modules['matplotlib.pyplot'].close('all')   # their plots belong to their own blocks
_pm_run_earlier(_pm_earlier, globals())
del _pm_earlier, _pm_run_earlier

3. time.perf_counter(): Quick Timing

For a quick "how long did this block take," perf_counter from the time module (see the datetime lesson) gives you the highest-resolution monotonic clock (a clock that never goes backwards) that the OS provides.

python
import time

start = time.perf_counter()
result = expensive_pipeline(data)
elapsed = time.perf_counter() - start
print(f"pipeline: {elapsed:.3f}s")
+ setup added so this can run · defines expensive_pipeline, data
# Lightweight mock for objects whose attributes/methods aren't critical
class _AutoMock:
    def __init__(self, name='mock'): self._name = name
    def __getattr__(self, k): return _AutoMock(self._name + '.' + k)
    def __call__(self, *a, **kw):
        print('-> ' + self._name + '() called')
        return _AutoMock(self._name + '()')
    def __repr__(self): return '<mock ' + self._name + '>'
    def __str__(self): return '<mock ' + self._name + '>'
    def __bool__(self): return True
    def __iter__(self): return iter([])
    def __len__(self): return 0
    def __getitem__(self, k): return _AutoMock(self._name + '[...]')
    def __setitem__(self, k, v): pass
    def __enter__(self): return self
    def __exit__(self, *a): return False
    async def __aenter__(self): return self
    async def __aexit__(self, *a): return False
    def __add__(self, o): return self
    def __radd__(self, o): return self
    def __sub__(self, o): return self
    def __mul__(self, o): return self
    def __rmul__(self, o): return self
    def __truediv__(self, o): return self
    def __eq__(self, o): return isinstance(o, _AutoMock)
    def __hash__(self): return hash(self._name)
    def __lt__(self, o): return True
    def __le__(self, o): return True
    def __gt__(self, o): return False
    def __ge__(self, o): return False
    def __mro_entries__(self, bases): return (object,)

def expensive_pipeline(*_a, **_kw):
    print('-> expensive_pipeline() called')
    return _AutoMock('expensive_pipeline()')
data = _AutoMock('data')

Put it in a context manager and you have a reusable timer:

python
from contextlib import contextmanager

@contextmanager
def timer(label):
    start = time.perf_counter()
    try:
        yield
    finally:
        print(f"{label}: {time.perf_counter() - start:.3f}s")

with timer("load"):
    rows = load_csv("big.csv")
with timer("transform"):
    out = transform(rows)
+ setup added so this can run · defines load_csv, transform, time
# Lightweight mock for objects whose attributes/methods aren't critical
class _AutoMock:
    def __init__(self, name='mock'): self._name = name
    def __getattr__(self, k): return _AutoMock(self._name + '.' + k)
    def __call__(self, *a, **kw):
        print('-> ' + self._name + '() called')
        return _AutoMock(self._name + '()')
    def __repr__(self): return '<mock ' + self._name + '>'
    def __str__(self): return '<mock ' + self._name + '>'
    def __bool__(self): return True
    def __iter__(self): return iter([])
    def __len__(self): return 0
    def __getitem__(self, k): return _AutoMock(self._name + '[...]')
    def __setitem__(self, k, v): pass
    def __enter__(self): return self
    def __exit__(self, *a): return False
    async def __aenter__(self): return self
    async def __aexit__(self, *a): return False
    def __add__(self, o): return self
    def __radd__(self, o): return self
    def __sub__(self, o): return self
    def __mul__(self, o): return self
    def __rmul__(self, o): return self
    def __truediv__(self, o): return self
    def __eq__(self, o): return isinstance(o, _AutoMock)
    def __hash__(self): return hash(self._name)
    def __lt__(self, o): return True
    def __le__(self, o): return True
    def __gt__(self, o): return False
    def __ge__(self, o): return False
    def __mro_entries__(self, bases): return (object,)

def load_csv(*_a, **_kw):
    print('-> load_csv() called')
    return _AutoMock('load_csv()')
def transform(*_a, **_kw):
    print('-> transform() called')
    return _AutoMock('transform()')
time = _AutoMock('time')

perf_counter is for timing. Never use time.time() for measuring durations, because it can jump backwards when NTP adjusts the system clock.

4. cProfile: Function-Level Profiling

When the workload is bigger than a snippet, cProfile instruments every function call and tells you where the time goes. The easiest way is the command line:

bash
python -m cProfile -s tottime script.py

-s tottime sorts by total time spent inside the function (excluding sub-calls). Reading the output:

python
   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
   100000    1.842    0.000    2.103    0.000 parser.py:42(parse_row)
        1    0.215    0.215    2.318    2.318 script.py:10(run)
   100000    0.261    0.000    0.261    0.000 {method 'split' of 'str' objects}
  • ncalls: how many times this function was called.
  • tottime: seconds spent inside this function, not counting the functions it calls. The function that does the most work itself has the biggest tottime.
  • cumtime: seconds spent in this function plus everything it called. The top-level function of a slow call chain has the biggest cumtime.

Rule of thumb: sort by tottime to find expensive primitives, and sort by cumtime (-s cumulative) to find expensive call chains. Both views are useful.

For programmatic use, dump a profile to disk and analyse it later:

python
import cProfile
cProfile.run("run_pipeline()", filename="run.prof")

5. pstats: Exploring the Profile

pstats reads a .prof file and lets you query it: filter by filename, show only the top N, or sort by different columns without running the program again.

python
import pstats

p = pstats.Stats("run.prof")
p.strip_dirs()                    # remove the long absolute paths
p.sort_stats("cumulative")
p.print_stats(20)                 # top 20 by cumulative time

p.sort_stats("tottime")
p.print_stats("parser", 10)       # top 10 results whose path matches 'parser'

To explore further, open the file in a visual viewer: snakeviz run.prof (third-party, pip install snakeviz) shows an interactive chart of the call tree in your browser.

6. Line-Level Profiling: line_profiler

cProfile tells you which function is slow. When the function is 80 lines long, you still need to know which line. That's line_profiler (third-party):

bash
pip install line_profiler

Decorate the function with @profile (the tool injects it) and run via kernprof:

python
@profile
def parse_row(line):
    parts = line.split(",")           # is this the slow line?
    parts = [p.strip() for p in parts]
    return {"name": parts[0], "value": int(parts[1])}
+ setup added so this can run · defines profile
# Lightweight mock for objects whose attributes/methods aren't critical
class _AutoMock:
    def __init__(self, name='mock'): self._name = name
    def __getattr__(self, k): return _AutoMock(self._name + '.' + k)
    def __call__(self, *a, **kw):
        print('-> ' + self._name + '() called')
        return _AutoMock(self._name + '()')
    def __repr__(self): return '<mock ' + self._name + '>'
    def __str__(self): return '<mock ' + self._name + '>'
    def __bool__(self): return True
    def __iter__(self): return iter([])
    def __len__(self): return 0
    def __getitem__(self, k): return _AutoMock(self._name + '[...]')
    def __setitem__(self, k, v): pass
    def __enter__(self): return self
    def __exit__(self, *a): return False
    async def __aenter__(self): return self
    async def __aexit__(self, *a): return False
    def __add__(self, o): return self
    def __radd__(self, o): return self
    def __sub__(self, o): return self
    def __mul__(self, o): return self
    def __rmul__(self, o): return self
    def __truediv__(self, o): return self
    def __eq__(self, o): return isinstance(o, _AutoMock)
    def __hash__(self): return hash(self._name)
    def __lt__(self, o): return True
    def __le__(self, o): return True
    def __gt__(self, o): return False
    def __ge__(self, o): return False
    def __mro_entries__(self, bases): return (object,)

profile = _AutoMock('profile')
bash
kernprof -l -v script.py

Output is per-line: % Time, Hits, Time. Once you see which line takes most of the time, you can fix exactly that line.

7. Memory Profiling: tracemalloc and memory_profiler

tracemalloc is in the standard library, so you don't need to install it. It tracks the memory that Python allocates.

python
import tracemalloc

tracemalloc.start()
result = build_huge_thing()
current, peak = tracemalloc.get_traced_memory()
print(f"current: {current / 1e6:.1f} MB, peak: {peak / 1e6:.1f} MB")

snapshot = tracemalloc.take_snapshot()
for stat in snapshot.statistics("lineno")[:10]:
    print(stat)                       # top 10 lines by allocation
+ setup added so this can run · defines build_huge_thing
# Lightweight mock for objects whose attributes/methods aren't critical
class _AutoMock:
    def __init__(self, name='mock'): self._name = name
    def __getattr__(self, k): return _AutoMock(self._name + '.' + k)
    def __call__(self, *a, **kw):
        print('-> ' + self._name + '() called')
        return _AutoMock(self._name + '()')
    def __repr__(self): return '<mock ' + self._name + '>'
    def __str__(self): return '<mock ' + self._name + '>'
    def __bool__(self): return True
    def __iter__(self): return iter([])
    def __len__(self): return 0
    def __getitem__(self, k): return _AutoMock(self._name + '[...]')
    def __setitem__(self, k, v): pass
    def __enter__(self): return self
    def __exit__(self, *a): return False
    async def __aenter__(self): return self
    async def __aexit__(self, *a): return False
    def __add__(self, o): return self
    def __radd__(self, o): return self
    def __sub__(self, o): return self
    def __mul__(self, o): return self
    def __rmul__(self, o): return self
    def __truediv__(self, o): return self
    def __eq__(self, o): return isinstance(o, _AutoMock)
    def __hash__(self): return hash(self._name)
    def __lt__(self, o): return True
    def __le__(self, o): return True
    def __gt__(self, o): return False
    def __ge__(self, o): return False
    def __mro_entries__(self, bases): return (object,)

def build_huge_thing(*_a, **_kw):
    print('-> build_huge_thing() called')
    return _AutoMock('build_huge_thing()')

For decorated function-level memory profiling, memory_profiler (third-party, pip install memory_profiler) gives you a @profile decorator and a mprof run script.py CLI that produces a memory-over-time chart.

Memory bugs (leaks, memory that keeps growing) usually show up as a peak value that grows over repeated runs. CPU profiling won't find them. You need to look at allocations.

8. dis.dis(): Reading the Bytecode

When two pieces of code look equivalent and timeit says they aren't, the bytecode shows you why.

python
import dis

def f(xs):
    out = []
    for x in xs:
        out.append(x * x)
    return out

def g(xs):
    return [x * x for x in xs]

dis.dis(f)
dis.dis(g)

The list comprehension g compiles to a shorter loop that uses a LIST_APPEND opcode instead of looking up and calling the method out.append on every item (LOAD_ATTR + CALL on Python 3.12 and later, LOAD_METHOD + CALL_METHOD on Python 3.10 and earlier). That difference is the main reason comprehensions are faster than a manual for/append loop, and you can only see it in the bytecode.

You won't read dis output every day. It is useful when a colleague says "X is faster than Y" and you want to check whether that is true on your Python version.

9. Algorithms Beat Micro-Optimisations

A function with O(n²) behaviour and a 2× constant-factor speedup is still O(n²). The real improvement is to change the algorithm.

python
# O(n²): for each item, scan the rest of the list
def count_pairs_slow(items, target):
    n, total = len(items), 0
    for i in range(n):
        for j in range(i + 1, n):
            if items[i] + items[j] == target:
                total += 1
    return total

# O(n): one pass that looks up the complement in a dict
def count_pairs_fast(items, target):
    seen, total = {}, 0
    for x in items:
        total += seen.get(target - x, 0)
        seen[x] = seen.get(x, 0) + 1
    return total

For n = 10_000, the slow version is ~50 million comparisons. The fast version is 10,000 dict lookups. Even rewriting the slow version in Cython can't close that gap.

Kinds of speedup, from the biggest effect to the smallest:

1. Drop a whole call (memoise, cache, skip).
2. Replace O(n²) with O(n log n) or O(n).
3. Switch data structure (list → set/dict for membership).
4. Vectorise with numpy for numeric loops.
5. Move hot loops to C (numba, cython, native extension).
6. Micro-optimise pure-Python idioms (the Section 10 list).

Start at the top of this list. Don't spend time on Section 10 changes while a Section 9 improvement is still available.

10. Common Speedups in Pure Python

Once you've fixed the algorithm and you still want more:

Local variable lookups are faster than globals. A local name is an array index, but a global is a dict lookup. Inside a loop that runs very often, store them in local variables:

python
def hot_loop(xs):
    _len = len               # store builtins in local names (faster lookup)
    result = []
    _append = result.append
    for x in xs:
        if _len(x) > 3:
            _append(x)
    return result

Comprehensions are faster than manual for/append. Section 8 explains why at the bytecode level.

set/dict membership is O(1), but list is O(n).

python
banned = {"alice", "bob", "carol"}   # set: O(1) lookup
if name in banned: ...
+ setup added so this can run · defines name
# Lightweight mock for objects whose attributes/methods aren't critical
class _AutoMock:
    def __init__(self, name='mock'): self._name = name
    def __getattr__(self, k): return _AutoMock(self._name + '.' + k)
    def __call__(self, *a, **kw):
        print('-> ' + self._name + '() called')
        return _AutoMock(self._name + '()')
    def __repr__(self): return '<mock ' + self._name + '>'
    def __str__(self): return '<mock ' + self._name + '>'
    def __bool__(self): return True
    def __iter__(self): return iter([])
    def __len__(self): return 0
    def __getitem__(self, k): return _AutoMock(self._name + '[...]')
    def __setitem__(self, k, v): pass
    def __enter__(self): return self
    def __exit__(self, *a): return False
    async def __aenter__(self): return self
    async def __aexit__(self, *a): return False
    def __add__(self, o): return self
    def __radd__(self, o): return self
    def __sub__(self, o): return self
    def __mul__(self, o): return self
    def __rmul__(self, o): return self
    def __truediv__(self, o): return self
    def __eq__(self, o): return isinstance(o, _AutoMock)
    def __hash__(self): return hash(self._name)
    def __lt__(self, o): return True
    def __le__(self, o): return True
    def __gt__(self, o): return False
    def __ge__(self, o): return False
    def __mro_entries__(self, bases): return (object,)

name = _AutoMock('name')

str.join(list) is better than += on a string in a loop. Strings are immutable, so += can create a new string on each iteration, which makes a long loop quadratic. (CPython sometimes optimises this case, but you can't rely on it.)

python
# WRONG: O(n²)
out = ""
for chunk in chunks:
    out += chunk

# RIGHT: O(n)
out = "".join(chunks)
+ setup added so this can run · defines chunks
chunks = ["alpha", "beta", "gamma"]

Generators are better than lists when you iterate only once. They don't build the whole intermediate list in memory. See generators.

functools.lru_cache for repeated calls with the same args:

python
from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    return n if n < 2 else fib(n-1) + fib(n-2)

Memoisation turns exponential recursion into linear lookup. It only works with hashable arguments: pass a list and you get TypeError: unhashable type.

11. Signs That Pure Python Is the Wrong Tool

Some workloads are a poor fit for pure Python. Signs:

  • A hot inner loop over millions of numbers. Pure Python's per-iteration overhead is ~50ns. numpy vectorisation does the same work in C at ~1ns per element. That is a 50× speedup, often more.

python # SLOW: a Python loop total = sum(x * x for x in data) # 10M items: ~1.5s # FAST: numpy vectorisation import numpy as np arr = np.asarray(data) total = (arr * arr).sum() # 10M items: ~25ms

  • Per-row iteration of a DataFrame. df.iterrows() is one of the slowest ways to use pandas. Use vectorised column operations (df["price"] * df["qty"]), df.apply(..., axis=1) for work that really must happen row by row, or convert to numpy and process the array.
  • A CPU-bound function you want to run in parallel. Threading gives no speedup, because the GIL lets only one thread run Python bytecode at a time. Use multiprocessing or concurrent.futures.ProcessPoolExecutor. See multiprocessing.
  • Numerical kernels that even numpy can't vectorise. numba's @jit compiles a Python function to LLVM in seconds, and cython lets you add type annotations and compile to a C extension. For a hand-written loop, either one gives you speed close to C.

In short: pure Python is often fast enough. When it isn't, the solution is usually to move the slow part out of pure Python.

12. Other Tools Worth Knowing

__slots__ declares a fixed set of attributes on a class. This removes the per-instance __dict__. For a class you'll create millions of, the memory saving is large:

python
class Point:
    __slots__ = ("x", "y")
    def __init__(self, x, y):
        self.x, self.y = x, y

Trade-offs: no dynamic attributes, no per-instance __dict__, and multiple inheritance becomes harder. Use when you've measured a memory problem, not by default.

weakref lets you hold a reference without preventing garbage collection. This is useful for caches that should release entries when nothing else holds them.

Async vs multiprocessing depends on the workload. I/O-bound (network, disk, DB) → asyncio. CPU-bound → multiprocessing. Mixing them up is a common Python performance mistake: threading or async around a CPU-bound function is slower than running it sequentially, because of overhead and the GIL.

Common Mistakes

1. Optimising without profiling. Most of your code is not where the time goes, and the slow part might not be where you think. Without a profile, you are only guessing.

2. Micro-optimising while an O(n²) algorithm is still in the code. The small amount you save with comprehensions is tiny next to what you save by changing the algorithm. Fix the big-O first.

3. Premature numpy. For 100-element lists, pure Python can be faster than numpy, because creating an array has a fixed cost that is bigger than the benefit on small data. numpy wins from thousands of elements upwards.

4. Threading CPU-bound code. Because of the GIL, CPU-bound Python code runs one thread at a time, however many threads you start. CPU-bound parallelism needs multiprocessing, numba, or a native extension that releases the GIL.

5. @lru_cache on a function with mutable arguments.

python
@lru_cache(maxsize=128)
def search(items, target):              # items is a list, and lists are unhashable
    ...

search([1, 2, 3], 2)                    # TypeError: unhashable type: 'list'
+ setup added so this can run · re-runs 1 earlier block on this page first
# Lightweight mock for objects whose attributes/methods aren't critical
class _AutoMock:
    def __init__(self, name='mock'): self._name = name
    def __getattr__(self, k): return _AutoMock(self._name + '.' + k)
    def __call__(self, *a, **kw):
        print('-> ' + self._name + '() called')
        return _AutoMock(self._name + '()')
    def __repr__(self): return '<mock ' + self._name + '>'
    def __str__(self): return '<mock ' + self._name + '>'
    def __bool__(self): return True
    def __iter__(self): return iter([])
    def __len__(self): return 0
    def __getitem__(self, k): return _AutoMock(self._name + '[...]')
    def __setitem__(self, k, v): pass
    def __enter__(self): return self
    def __exit__(self, *a): return False
    async def __aenter__(self): return self
    async def __aexit__(self, *a): return False
    def __add__(self, o): return self
    def __radd__(self, o): return self
    def __sub__(self, o): return self
    def __mul__(self, o): return self
    def __rmul__(self, o): return self
    def __truediv__(self, o): return self
    def __eq__(self, o): return isinstance(o, _AutoMock)
    def __hash__(self): return hash(self._name)
    def __lt__(self, o): return True
    def __le__(self, o): return True
    def __gt__(self, o): return False
    def __ge__(self, o): return False
    def __mro_entries__(self, bases): return (object,)

def lru_cache(*_a, **_kw):
    print('-> lru_cache() called')
    return _AutoMock('lru_cache()')

# Earlier blocks on this page that this one builds on, re-run quietly first.
try:
    from functools import lru_cache
except Exception:
    pass
_pm_earlier = [
    'from functools import lru_cache\n\n@lru_cache(maxsize=None)\ndef fib(n):\n    return n if n < 2 else fib(n-1) + fib(n-2)',
]
def _pm_run_earlier(_srcs, _g):
    import sys as _s, io as _io, warnings as _w
    for _src in _srcs:
        _o, _e = _s.stdout, _s.stderr
        _s.stdout = _s.stderr = _io.StringIO()
        try:
            with _w.catch_warnings():
                _w.simplefilter('ignore')
                exec(compile(_src, '<earlier block>', 'exec'), _g)
        except (Exception, SystemExit):
            pass
        finally:
            _s.stdout, _s.stderr = _o, _e
    if 'matplotlib.pyplot' in _s.modules:
        _s.modules['matplotlib.pyplot'].close('all')   # their plots belong to their own blocks
_pm_run_earlier(_pm_earlier, globals())
del _pm_earlier, _pm_run_earlier

Either pass a tuple instead, or frozenset for "membership without order," or don't cache.

6. print-based "did this run" debugging in a hot loop. print writes to stdout, which is slow, especially when the output goes to a terminal. In a million-iteration loop, these calls can take longer than the real work. Use logging with a level filter, or count + report once after the loop.

🎯 Your Turn: From O(n²) to O(n)

You're given a slow count_pairs(items, target) that uses nested loops. Your job:

1. Write a fast version using a dict to look up complements in one pass.
2. Benchmark both with timeit for n = 1_000 random integers.
3. Confirm they agree on the answer.

python
import random
from timeit import timeit

def count_pairs_slow(items, target):
    """O(n^2): nested loops. This is the reference version."""
    n, total = len(items), 0
    for i in range(n):
        for j in range(i + 1, n):
            if items[i] + items[j] == target:
                total += 1
    return total

def count_pairs_fast(items, target):
    # TODO 1: walk items once
    # TODO 2: for each x, count how many earlier items equal (target - x)
    # TODO 3: track counts of items seen so far in a dict
    ...

# Quick check that both give the same answer
data = [random.randint(0, 50) for _ in range(200)]
assert count_pairs_slow(data, 50) == count_pairs_fast(data, 50)

# Benchmark with 1_000 items: about 500,000 comparisons for the slow one
big = [random.randint(0, 1000) for _ in range(1_000)]
t_slow = timeit(lambda: count_pairs_slow(big, 500), number=1)
t_fast = timeit(lambda: count_pairs_fast(big, 500), number=1)
print(f"slow: {t_slow:.3f}s   fast: {t_fast:.3f}s   speedup: {t_slow/t_fast:.0f}x")
Hint 1: One pass, two operations per item For each item x, you need two things: (a) count how many already-seen items equal target - x, and (b) add x itself to the seen-counts. Order matters: do (a) before (b), otherwise an item could pair with itself.
Hint 2: Use dict.get(key, 0) You're maintaining a count-of-occurrences dict. seen.get(key, 0) avoids a KeyError on the first sight of any value. Or use collections.Counter: the same idea, written in a more idiomatic way.
Show full solution
python
import random
from timeit import timeit
from collections import Counter

def count_pairs_slow(items, target):
    n, total = len(items), 0
    for i in range(n):
        for j in range(i + 1, n):
            if items[i] + items[j] == target:
                total += 1
    return total

def count_pairs_fast(items, target):
    """O(n): for each x, the number of new pairs is the count of (target - x) seen so far."""
    seen = Counter()
    total = 0
    for x in items:
        total += seen[target - x]       # pair x with every earlier occurrence of the complement
        seen[x] += 1                    # then record x for later pairs
    return total

# Correctness: match the reference on a small case
random.seed(0)
small = [random.randint(0, 50) for _ in range(200)]
assert count_pairs_slow(small, 50) == count_pairs_fast(small, 50)

# Benchmark with 1_000 items. The gap grows with n, so try 10_000 on your own machine
big = [random.randint(0, 1000) for _ in range(1_000)]
t_slow = timeit(lambda: count_pairs_slow(big, 500), number=1)
t_fast = timeit(lambda: count_pairs_fast(big, 500), number=1)
print(f"slow: {t_slow:.3f}s   fast: {t_fast:.3f}s   speedup: {t_slow/t_fast:.0f}x")

# Typical output in this browser tab (on your own machine it is several times faster):
# slow: 0.380s   fast: 0.002s   speedup: 170x

Why this is the right kind of fix:

  • Big-O changed. O(n²) → O(n). The speedup grows with n. At n = 100_000, the slow version is unusable (~5 minutes). The fast version is ~20ms. No micro-optimisation can close a gap that grows with n.
  • One pass. The dict lets you ask "how many previous items would have paired with me?" in O(1). Each item contributes that count to the total, then registers itself for future items to query.
  • Counter is the right tool. It's a dict subclass that returns 0 for missing keys, so you don't need code to handle KeyError. The whole loop is three lines.

The general idea: many O(n²) algorithms over a sequence become O(n) when you build a hash map of complements, prefixes or partial results. Two-sum and many prefix-sum and sliding-window problems are solved this way.

What You Learned

  • Profile first. timeit for snippets, cProfile + pstats for whole scripts, line_profiler for hot lines, tracemalloc for memory.
  • time.perf_counter() for quick timing, never time.time() (NTP can move it backwards).
  • dis.dis(fn) when two equivalent-looking pieces of code disagree on speed.
  • Algorithms first. O(n²) → O(n) with a dict is worth more than any micro-optimisation.
  • Common speedups: comprehensions over for/append, set/dict membership over list, str.join over +=, lru_cache for repeated calls, generators for one-pass streams.
  • Signs of the wrong tool: per-row DataFrame iteration, Python loops over millions of numbers, threading CPU-bound code. Use numpy, multiprocessing, numba, or cython.
  • __slots__ for memory on classes you'll instantiate millions of. weakref for caches that shouldn't keep objects alive.
  • Async vs multiprocessing is workload-dependent. I/O-bound → async. CPU-bound → multiprocessing.

Next: Design Patterns That Fit Python: which GoF patterns are still useful in a language with first-class functions, and which become a single line of code.

Practice this

on practicepython.in

Short exercises that run in your browser and tell you what your code did, as well as whether a test passed.

Found this useful? Share it with a friend who’s learning Python.