Now that Brett has a substantial portion of the benchmark suite running on Py3k, we should see a bit more progress on the PyPy-inspired speed.python.org project (which should make it much easier to catch this kind of regression before it hits a production release).

In this case, as I noted in my earlier comment, I think the 3.3 changes to make_key broke an important single-argument fast path that the re module was previously relying on, thus the major degradation in performance on a cache hit. I haven't looked into setting up the benchmark suite on my own machine though, so we won't know for sure until either I get around to doing that, or someone with it already set up tries the change I suggested above.