Switched to if d in memo: return memo[d] as suggested. Drops the sentinel, and the test no longer touches memo.

Microbenchmark (5M lookups): d in memo is ~6 ns faster on a hit and ~22 ns on a miss than memo.get(d, None); full deepcopy is within noise.

d in memo is ~6 ns faster on a hit and ~22 ns on a miss than memo.get(d, None)

Faster in both cases? Did you measure purely d in memo and memo.get(d, None)? Or did you include the other differences as well?

The earlier numbers included the surrounding statements. Measuring just the lookup, each returning the value (best of 5 runs of 10M):

                                  hit (present)   miss (absent)
memo.get(d, None)                    51 ns           60 ns
memo[d] if d in memo else None       55 ns           49 ns

So d in memo is about 4 ns slower on a hit and 11 ns faster on a miss. In deepcopy each object is looked up once, so misses are the common case, and full deepcopy timings are within noise either way.

Ok if the surrounding stuff was properly included, then that's good. This new comparison for "just the lookup" is not, it's missing the is not None check in an if-context and the store/load of y.

Anyway, I agree that misses are probably the common case, and I'm not surprised if full deepcopy timings are within noise either way, as deepcopy is rather slow.