The code for dict_equal() in Objects/dictobject.c currently loops over the key/value pairs in self and uses PyDict_GetItem() to check for the corresponding key/value pair in the other dictionary.  This causes an unnecessary call to PyObject_Hash().

Instead, the code should loop over the key/value/hash triplets in self and do a direct lookup in the other dictionary with " ep = (otherdict->ma_lookup)(otherdict, key, hash)".   The reuses the known hash value for the key; thereby avoiding the potentially slow call to PyObject_Hash().

See _PyDict_Contains() for an example of how to do a lookup when the hash value is already known.

Note, the optimized path should be used only when PyDict_CheckExact() is true.

Here is a simple patch.

> Note, the optimized path should be used only when PyDict_CheckExact() is true.

Actually this is not needed. dict_equal() uses the same code for dict subclasses.

The patch looks good to me.

And here is a synthetic microbenchmark:

$ ./python -m timeit -s "n=10**3; k=2; a={(i,)*k:i for i in range(n)}; b={(i,)*k:i for i in range(n)}"  "a == b"

Vanilla: 251 usec per loop
Patched: 195 usec per loop

$ ./python -m timeit -s "n=10**3; k=2; a={(i,)*k:i for i in range(n)}; b=dict(a)"  "a == b"

Vanilla: 116 usec per loop
Patched: 58.6 usec per loop

The use of tuple keys is quite common.

The patch looks correct.  If the tests pass, go ahead and apply it.

New changeset d12785ecca72 by Antoine Pitrou in branch 'default':
Issue #16562: Optimize dict equality testing.
http://hg.python.org/cpython/rev/d12785ecca72

> The patch looks correct.  If the tests pass, go ahead and apply it.

Done.