This is mostly an RFC patch. It compiles and passes the test suite. A somewhat silly microbenchmark such as

./python -m timeit -s 'import copy; x = dict([(str(x), x) for x in range(10000)]);'  'copy.deepcopy(x)'

runs about 30x faster. In the (2.7 only) application which motivated this, the part of its initialization that does a lot of deepcopying drops from 11s to 3s. That it's so much less is presumably because the application holds on to the deepcopies, so there's much more allocation going on than in the microbenchmark, but I haven't investigated thoroughly. In any case, a 3.5x speedup is also nice.