Python Performance: Profile First, Then Fix Data Structures

Quick answer: Measure before you change anything. The wins that matter are 100–100,000× and they come from data structures and algorithms, not from tweaking syntax: a set membership test took 27 ns where the same test on a list took 5.16 ms (about 190,000×), collapsing a 252 ms duplicate scan into 0.32 ms (about 780×), and a memoryview slice beat copying a 1 MB bytes object by 146–167×. Micro-optimisation is the last 2%, and usually the wrong place to spend an afternoon.

Part 13 of our Python series — Module 3, the deep dive. Previous: concurrency. Start at Module 1.

The order of operations

Work down this list and stop when the numbers are good enough:

• Algorithm and data structure — O(n²) → O(n) is orders of magnitude.
• Memory layout — objects you never allocate cost nothing.
• Fewer I/O and network round-trips — batching beats every local tweak.
• Caching — do not compute the same thing twice.
• Interpreter micro-tuning — the last percent, and the only thing most tutorials talk about.

Amdahl’s law explains the ordering: if a step is 5% of runtime, making it infinitely fast saves 5%. Profiling tells you which step that is.

Profile with a real profile

python -m cProfile -s cumtime slowscript.py | head -20

Read tottime (time inside the function itself) to find hot code and cumtime (including everything it calls) to find the expensive subsystem. You can also profile in-process and get a clean table:

import cProfile, pstats, io

def workload():
    hot = sum(i * i for i in range(200_000))
    return hot, len(set(range(50_000)))

profiler = cProfile.Profile()
profiler.enable()
workload()
profiler.disable()

stats = io.StringIO()
pstats.Stats(profiler, stream=stats).sort_stats("tottime").print_stats(5)
print(stats.getvalue())

Three caveats a professional knows: cProfile measures Python-level calls and can miss time inside C functions it cannot instrument; it adds overhead that distorts very tight loops; and it will happily show you a function that is called a million times for 0.4 s while the real cost sits in a single requests.get. For wall-clock line-by-line detail, line_profiler or pyinstrument are the usual next step.

For start-up time, skip the profiler entirely:

python -X importtime -c "import yourpackage"   # per-module import cost, microseconds

Data structures: where the real money is

This is the table to internalise. All numbers measured on CPython 3.14, 1,000,000-element containers:

The reason is almost always hashing. A dict or set lookup hashes the key, masks it to a slot, and compares — constant time regardless of size. A list scan compares element by element until it finds a match, so the average cost grows with the list. That is exactly why the if x not in out dedupe pattern is quadratic and why it becomes unusable somewhere around 50,000 items:

items = list(range(5_000)) * 4          # 20,000 items, 5,000 unique

slow = []
for x in items:
    if x not in slow:                   # scans the growing output list
        slow.append(x)

fast = list(dict.fromkeys(items))       # hash-based, order-preserving
assert slow == fast

dict.fromkeys preserves insertion order and removes duplicates in one pass — the idiomatic dedupe. set(items) is even cheaper but loses order. Both turn an O(n²) loop into O(n).

Same lesson for sorted data: if you search a sorted list more than a handful of times, use bisect (O(log n)) or load it into a dict/set once.

Memory: the numbers that change designs

Measured on 1,000,000 ints, on CPython 3.14. Two columns matter: sys.getsizeof shows the container’s own bytes, tracemalloc shows everything actually allocated including the boxed integer objects.

Three design consequences:

• Do not materialise what you can stream. A generator holding 1M values occupies about 200 bytes because it stores a frame, not the values. Wrap long pipelines (sum(process(x) for x in rows)) in generators by default; convert to a list only when you genuinely need random access or repeated iteration.
• Numeric arrays beat lists when all elements share a type. array("l") halves the container and eliminates the boxed objects entirely, which is where the 90% total-allocation saving comes from. numpy.ndarray goes further by adding vectorised operations on top of the same unboxed layout.
• __slots__, array, and generators all trade flexibility for footprint. Profile memory with tracemalloc before choosing.

sys.getsizeof measures one object’s own bytes; tracemalloc measures allocations, which is what you want when the object graph is nested. Use both — the object-model article shows a case where getsizeof reports an identical 48 bytes for two classes whose peak allocations differ by 31%.

Zero-copy with memoryview

Slicing a bytes object copies. memoryview gives you a window onto the same buffer:

data = b"x" * 1_000_000
copy = data[500_000:]          # allocates 500 KB
view = memoryview(data)[500_000:]   # allocates nothing

print(len(copy), len(view), view.obj is data)   # 500000 500000 True

This matters exactly where it hurts: binary parsing, socket buffers, image data, and reading a large file in chunks. memoryview also supports cast and slice without reallocating, and it is the reason struct.unpack_from(mv, offset) scales where struct.unpack(data[offset:]) does not.

When Python itself is too slow

After algorithms, data structures, and caching are done, one of these:

Note the order: most “Python is slow” problems are actually list-scan-in-a-loop problems, and they disappear at step 1. Reach for NumPy before you reach for a new language.

Complete executable example

# perf_lab.py -- profile, then measure the four wins that actually matter
import cProfile
import io
import pstats
import sys
import timeit
import tracemalloc
from array import array


def section(title):
    print("\n" + title)
    print("=" * len(title))


items = list(range(5_000)) * 4          # 20,000 items, 5,000 unique


def dedupe_slow(data):
    out = []
    for x in data:
        if x not in out:                # O(n^2): scans the growing list
            out.append(x)
    return out


def dedupe_fast(data):
    return list(dict.fromkeys(data))    # O(n): hashes each element once


def profiled():
    return dedupe_slow(items)


section("1. Profile first: tottime tells you where the work is")
profiler = cProfile.Profile()
profiler.enable()
profiled()
profiler.disable()
stream = io.StringIO()
pstats.Stats(profiler, stream=stream).sort_stats("tottime").print_stats(3)
print(stream.getvalue().strip())

section("2. Algorithmic fix: O(n^2) scan versus O(n) hash pass")
slow = timeit.timeit(lambda: dedupe_slow(items), number=1)
fast = timeit.timeit(lambda: dedupe_fast(items), number=1)
print(f"list scan       {slow * 1000:9.2f} ms")
print(f"dict.fromkeys   {fast * 1000:9.3f} ms   ({slow / fast:,.0f}x faster)")
assert dedupe_slow(items) == dedupe_fast(items)
assert slow / fast > 50

section("3. Membership: the worst case for a list")
numbers = list(range(1_000_000))
as_set = set(numbers)
set_reps, list_reps = 100_000, 100          # a list scan is ~200,000x slower: use few reps
set_time = timeit.timeit(lambda: 999_999 in as_set, number=set_reps) / set_reps
list_time = timeit.timeit(lambda: 999_999 in numbers, number=list_reps) / list_reps
print(f"set   {set_time * 1e9:9.0f} ns per lookup")
print(f"list  {list_time * 1e6:9.3f} us per lookup (worst case: value at the end)")
print(f"ratio: {list_time / set_time:,.0f}x")
assert set_time < list_time / 100

section("4. Memory: list, array, and generator for 1,000,000 values")
tracemalloc.start()
boxed = list(range(1_000_000))
list_peak = tracemalloc.get_traced_memory()[1]
tracemalloc.stop()
del boxed

tracemalloc.start()
compact = array("l", range(1_000_000))
array_peak = tracemalloc.get_traced_memory()[1]
tracemalloc.stop()
del compact

generator = (i for i in range(1_000_000))
gen_size = sys.getsizeof(generator)

print(f"list of 1M ints   {list_peak / 1024 / 1024:8.2f} MiB")
print(f"array('l') 1M     {array_peak / 1024 / 1024:8.2f} MiB  "
      f"({100 * (1 - array_peak / list_peak):.0f}% smaller)")
print(f"generator         {gen_size:8d} bytes, constant")
assert array_peak < list_peak * 0.6 and gen_size < 1000

section("5. Zero-copy: slicing bytes versus a memoryview")
data = b"x" * 1_000_000
view = memoryview(data)
reps = 20_000
copy_time = timeit.timeit(lambda: data[:500_000], number=reps)
view_time = timeit.timeit(lambda: view[:500_000], number=reps)
print(f"bytes slice      {copy_time * 1000:8.2f} ms   (allocates 500 KB each time)")
print(f"memoryview slice {view_time * 1000:8.2f} ms   ({copy_time / view_time:,.0f}x faster)")
assert view[0] == data[0] and len(view) == len(data)
assert copy_time / view_time > 10

print("\nAll performance-lab assertions passed.")

Line by line: the profile runs the slow implementation so you can see dedupe_slow occupy the top of the table — that is the moment profiling earns its keep; items is 20,000 elements with only 5,000 unique values, which is what makes the list scan quadratic; section 3 measures the worst case for a list (the value sits at the end), runs the list 1,000× fewer repetitions than the set, and divides both totals by their repetition counts so the two columns are comparable; tracemalloc brackets only the allocation of interest and stops before the next one, so the peaks do not contaminate each other; the generator’s size is measured with getsizeof, because it never allocates its elements at all; and every claim in the article is asserted, so the script fails on a machine where the numbers do not hold.

Common mistakes

• Optimising by intuition. The function you think is slow rarely is. Profile.
• Using a list for membership testing in a loop — the single most common accidental O(n²).
• sum([x for x in ...]) instead of sum(x for x in ...) — the brackets build a full list first.
• Copying big buffers while parsing. Slice with memoryview, not bytes[i:j].
• Micro-tuning before algorithm choice. Changing for to a comprehension is a 20% win; fixing an O(n²) is a 580–780× win.
• Not re-measuring after the change. Keep the timeit harness around; the fix that helps on your laptop may not help on the server.

Key takeaways and challenge

• Profile before changing anything: cProfile for functions, -X importtime for start-up.
• Hash-based containers turn O(n) scans into O(1): about 190,000× on the worst-case membership test.
• dict.fromkeys dedupes in one ordered pass — about 780× over the list-scan version at 20,000 items.
• Generators are effectively free to hold (~200 bytes); array cuts total allocation by 90% on 1M ints; memoryview avoids copies entirely (146–167×).
• After algorithms and data layout, use caching, then processes, then NumPy — and only then micro-tune.

Challenge: profile a script of your own and rank its functions by tottime. For the top entry, ask three questions in order — is there a hash-based structure that removes the scanning, is anything being materialised that could be a generator, and is the same value computed twice? Apply the first fix that applies and re-measure. Then post the before/after timeit numbers, because that habit is what separates guessing from engineering.

Want a review of your own performance work? Ampersand Academy runs one-to-one Python training, including profiling sessions on real projects.