Why are uncompiled, repeatedly used regexes so much slower in Python 3?
Question: When answering [this question](http://stackoverflow.com/q/14755882/20670) (and
having read [this answer](http://stackoverflow.com/a/452143/20670) to a
similar question), I thought that I knew how Python caches regexes.

But then I thought I'd test it, comparing two scenarios:

  1. a single compilation of a simple regex, then 10 applications of that compiled regex.
  2. 10 applications of an uncompiled regex (where I would have expected slightly worse performance because the regex would have to be compiled once, then cached, and then looked up in the cache 9 times).

However, the results were staggering (in Python 3.3):

    
    
    >>> import timeit
    >>> timeit.timeit(setup="import re", 
    ... stmt='r=re.compile(r"\w+")\nfor i in range(10):\n r.search("  jkdhf  ")')
    18.547793477671938
    >>> timeit.timeit(setup="import re", 
    ... stmt='for i in range(10):\n re.search(r"\w+","  jkdhf  ")')
    106.47892003890324
    

That's over 5.7 times slower! In Python 2.7, there is still an increase by a
factor of 2.5, which is also more than I would have expected.

Has caching of regexes changed between Python 2 and 3? [The
docs](http://docs.python.org/dev/library/re.html#re.compile) don't seem to
suggest that.


Answer: The code _has_ changed.

In Python 2.7, the cache is a simple dictionary; if more than `_MAXCACHE`
items are stored in it, the whole the cache is cleared before storing a new
item. A cache lookup only takes building a simple key and testing the
dictionary, see the [2.7 implementation of
`_compile()`](http://hg.python.org/cpython/file/2.7/Lib/re.py#l226)

In Python 3.x, the cache has been replaced by the
[`@functools.lru_cache(maxsize=500, typed=True)`
decorator](http://docs.python.org/3/library/functools.html#functools.lru_cache).
This decorator does _much_ more work and includes a thread-lock, adjusting the
cache LRU queue and maintaining the cache statistics (accessible via
`re._compile.cache_info()`). See the [3.3 implementation of
`_compile()`](http://hg.python.org/cpython/file/3.3/Lib/re.py#l264) and of
[`functools.lru_cache()`](http://hg.python.org/cpython/file/3.3/Lib/functools.py#l174).

Others have noticed the same slowdown, and filed [issue
16389](http://bugs.python.org/issue16389) in the Python bugtracker. I'd expect
3.4 to be a lot faster again; either the `lru_cache` implementation is
improved or the `re` module will move to a custom cache again.

Update: With [revision
4b4dddd670d0](http://hg.python.org/cpython/rev/4b4dddd670d0) the cache change
has been reverted back to the simple version found in 3.1. Python versions
3.2.4 and 3.3.1 include that revision.

