How does Python's regex pattern caching work?

Question

From the Python docs for re.compile():

Note The compiled versions of the most recent patterns passed to re.match(), re.search() or re.compile() are cached, so programs that use only a few regular expressions at a time needn’t worry about compiling regular expressions.

However, in my testing, this assertion doesn't seem to hold up. When timing the following snippets that use the same pattern repeatedly, the compiled version is still substantially faster than the uncompiled one (which should supposedly be cached).

Is there something I am missing here that explains the time difference?

import timeit

setup = """
import re
pattern = "p.a.t.t.e.r.n"
target = "p1a2t3t4e5r6n"
r = re.compile(pattern)
"""

print "compiled:", \
    min(timeit.Timer("r.search(target)", setup).repeat(3, 5000000))
print "uncompiled:", \
    min(timeit.Timer("re.search(pattern, target)", setup).repeat(3, 5000000))

Results:

compiled: 2.26673030059
uncompiled: 6.15612802627

Please don't use timeit like that. Just use standard parameters. Even if the results are valid, it's harder to judge if the approach is sound. — , Sep 20 '12 at 13:56
Sorry, what does the standard approach look like? I basically just copied [this question](http://stackoverflow.com/questions/8220801/how-to-use-timeit-correctly). — verdesmarald, Sep 20 '12 at 13:58
No, you didn't. The answers over there have setup code which runs once (in your case, compiling) and a *single* statement. Looping is left to timeit, either by specifying large numbers in the `repeat` (often just the default, `3` and `1000000`) call or by using the command line interface (`python -m timeit`) which loops long enough but not too long automatically. The `from __main__ import ...` trick is indeed useful. — , Sep 20 '12 at 14:04
@delnan Updated, is that a better way? (Note in this case the results are the same, luckily for me.) — verdesmarald, Sep 20 '12 at 14:25
Yes, better. Now on to the next potential flaw in the benchmark ;) — , Sep 20 '12 at 14:26

mgilson · Accepted Answer · 2018-09-13T14:31:17.173

Here's the (CPython) implementation of re.search:

def search(pattern, string, flags=0):
    """Scan through string looking for a match to the pattern, returning
    a match object, or None if no match was found."""
    return _compile(pattern, flags).search(string)

and here is re.compile:

def compile(pattern, flags=0):
    "Compile a regular expression pattern, returning a pattern object."
    return _compile(pattern, flags)

which relies on re._compile:

def _compile(*key):
    # internal: compile pattern
    cachekey = (type(key[0]),) + key
    p = _cache.get(cachekey)            #_cache is a dict.   
    if p is not None:
        return p
    pattern, flags = key
    if isinstance(pattern, _pattern_type):
        if flags:
            raise ValueError('Cannot process flags argument with a compiled pattern')
        return pattern 
    if not sre_compile.isstring(pattern):
        raise TypeError, "first argument must be string or compiled pattern"
    try:
        p = sre_compile.compile(pattern, flags)
    except error, v:
        raise error, v # invalid expression
    if len(_cache) >= _MAXCACHE:
        _cache.clear()
    _cache[cachekey] = p
    return p

So you can see that as long as the regex is already in the dictionary, the only extra work involved is the lookup in the dictionary (which involves creating a few temporary tuples, a few extra function calls ...).

Update In the good ole' days (the code copied above), the cache used to be completely invalidated when it got too big. These days, the cache cycles -- dropping the oldest items first. This implementation relies on the ordering of python dictionaries (which was an implementation detail until python3.7). In Cpython before python3.6, this would have dropped an arbitrary value out of the cache (which is arguably still better than invalidating the whole cache)

Implying it is all overhead from the extra function call and `cachekey = (type(key[0]),) + key, p = _cache.get(cachekey)`? — verdesmarald, Sep 20 '12 at 14:01
`re.search` has to do that, plus an extra function call (`re._compile`). But that's pretty much all ... Perhaps your regex is simple (and optimized enough by `_compile`) that those small things in python become a significant portion of your computation. Also note that if you have more than `100` regular expressions (`_MAXCACHE`), your cache gets cleared and you need to start over, but that shouldn't be hitting you in this case. — mgilson, Sep 20 '12 at 14:04
Seems like it is just the little things adding up. Trying it with more complex patterns/longer input strings, `.search` is still slower, but the difference stays constant at ~4s over 5M calls. So I guess the take-away is that there is a small overhead, and the advice "programs that use only a few regular expressions at a time needn't worry about compiling regular expressions" is perhaps not entirely accurate if you are doing **a lot** of searching (but most of the time it's not worth it). — verdesmarald, Sep 20 '12 at 14:41
Note that in the most recent version of python, this cache has become a least-recently-added 512 item cache: https://github.com/python/cpython/blob/e42b705188271da108de42b55d9344642170aa2b/Lib/re.py#L270 — Olivier Le Floch, Sep 12 '18 at 22:48

How does Python's regex pattern caching work?

1 Answers1