"you'd be surprised how much cheaper indexing a sequence is relative to dictionary access"

This is a bit off-topic (and I realise that this ticket is closed now), but the difference isn't really all that large:

$ python3.4 -m timeit -s 'seq = list(range(1000)); d = {n:n for n in seq}' 'seq[100]'
10000000 loops, best of 3: 0.0263 usec per loop

$ python3.4 -m timeit -s 'seq = list(range(1000)); d = {n:n for n in seq}' 'd[100]'
10000000 loops, best of 3: 0.0285 usec per Pool

$ python3.4 -m timeit -s 'seq = list(range(1000)); d = {"test%d"%n:n for n in seq}' 'd["test34"]'
10000000 loops, best of 3: 0.0317 usec per loop

Especially hashing strings is usually faster than you might expect, because the hash value is cached and strings that get hashed once tend to get hashed again later.

Note that KeyError doesn't do any exception message formatting on creation. It only includes the bare key, which is pretty quick, especially if the key is already a string.

In comparison, instantiating an exception takes almost three times as long:

$ python3 -m timeit -s 'K=KeyError' 'K("test")'
10000000 loops, best of 3: 0.0779 usec per loop

We once had the case in Cython where dropping the instantiation of StopIteration at the end of generator execution gave a serious performance boost (more than 40% faster for short running generator expressions in the nqueens benchmark), but the same is less likely to apply to IndexError, which normally indicates a bug and not control flow. I lean towards agreeing with Terry that usability beats performance here.