Sets vs tuples: A better comparison

Sets vs tuples: A better comparison

MP 179: I missed something last time!

In the last post, I compared two lookups. One used a tuple, and one used a set:

# Check membership in a tuple:
if operation not in ("read", "modify", "write"):
    raise ValueError(f"Illegal operation: {operation}")

# Check membership in a set:
if operation not in {"read", "modify", "write"}:
    raise ValueError(f"Illegal operation: {operation}")

I ran some simple benchmarks that looked like this:

$ uv run python -m timeit "operation='read'; valid = operation in ('read', 'modify', 'write')"
20000000 loops, best of 5: 10.4 nsec per loop

Based on these simple results, I came to the conclusion that set and tuple lookups are quite comparable as far as performance goes, for small collections of items.

I'm always a little hesitant to write about performance, because I know there's often more nuance than people realize. I got this one wrong! When running these benchmarks, I only ever checked whether the first item in the collection exists. I never ran the benchmarks looking for the second item, or the third item.

I assumed that looking for items other than the first one would perform quite similar to the benchmarks I ran, unless the set or tuple was much larger. A reader named Wadim commented on the last post, pointing out that these results don't hold as soon as you check for any operation other than "read" in the given example.

This is an important enough point that it's worth taking a second look at the comparison.

A closer look: tuples

Let's rerun those benchmarks, but this time we'll check for each item in the tuple. I'm also adding one more element to the tuple, so we can have a little more data to work with:

$ python3.15 -m timeit "operation='read'; valid = operation in ('read', 'modify', 'write', 'delete')"
20000000 loops, best of 5: 11.4 nsec per loop

$ python3.15 -m timeit "operation='modify'; valid = operation in ('read', 'modify', 'write', 'delete')"
20000000 loops, best of 5: 17.4 nsec per loop

$ python3.15 -m timeit "operation='write'; valid = operation in ('read', 'modify', 'write', 'delete')"
10000000 loops, best of 5: 22.6 nsec per loop

$ python3.15 -m timeit "operation='delete'; valid = operation in ('read', 'modify', 'write', 'delete')"
10000000 loops, best of 5: 30.6 nsec per loop

The lookup time increases when the item we're looking for appears later in the tuple: 11.4 ns, 17.4 ns, 22.6 ns, and 30.6 ns. This happens because for each lookup, Python compares the target value against each value in the tuple until it finds the item we're asking about, or reaches the end of the tuple.

Let's run one more check against the tuple. Let's look for an item that doesn't appear in the collection:

$ python3.15 -m timeit "operation='create'; valid = operation in ('read', 'modify', 'write', 'delete')"
10000000 loops, best of 5: 38.7 nsec per loop

This check, at 38.7 ns, takes longer than looking for the last item in the tuple. Python is running the comparison against every item in the tuple, and then finding that it's not present in the tuple.

Tuple lookup is an O(n) operation, which means the time it takes to execute the operation can increase linearly with the number of elements in the tuple. That's exactly what we're seeing here. I knew this could happen, but I thought n would need to be much larger to see this effect.

A closer look: sets

Now let's run the same set of comparisons against a set:

$ python3.15 -m timeit "operation='read'; valid = operation in {'read', 'modify', 'write', 'delete'}" 
20000000 loops, best of 5: 12.7 nsec per loop

$ python3.15 -m timeit "operation='modify'; valid = operation in {'read', 'modify', 'write', 'delete'}"
20000000 loops, best of 5: 11.9 nsec per loop

$ python3.15 -m timeit "operation='write'; valid = operation in {'read', 'modify', 'write', 'delete'}"
20000000 loops, best of 5: 12.1 nsec per loop

$ python3.15 -m timeit "operation='delete'; valid = operation in {'read', 'modify', 'write', 'delete'}"
20000000 loops, best of 5: 11.9 nsec per loop

$ python3.15 -m timeit "operation='create'; valid = operation in {'read', 'modify', 'write', 'delete'}"
20000000 loops, best of 5: 11.8 nsec per loop

Every lookup takes about 12 nanoseconds, even for the element that doesn't exist in the set.

Set lookup is an O(1) operation on average, which means execution time is usually constant; it doesn't usually change depending on how many items are in the set. Internally, sets are implemented as hash tables. When we ask if an element is in a set, Python takes a hash of the element we're asking about, uses that hash to look up the value, and returns True if it's able to find the element and False if it's not. It doesn't usually have to look at any other elements in the set.

Why do I keep saying usually? A hash collision occurs when two or more elements have the same hash. If this occurs when looking up an element, Python has to do a little more work to find the exact element it's looking for. Hash collisions are not common in most situations, which makes set lookups efficient in most cases.

Conclusions

Benchmarking and profiling is hard! But it's a good thing to do, because it challenges your assumptions and understandings about performance and the underlying implementation.