re._compiled_typed's lru_cache causes significant degradation of the mako_v2 bench

[pjenvey]

BPO	16389
Nosy	@warsaw, @brettcannon, @rhettinger, @terryjreedy, @jcea, @ncoghlan, @pitrou, @pjenvey, @ezio-melotti, @asvetlov, @serhiy-storchaka
Files	re_compile_cache.patch issue16389.diff

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/serhiy-storchaka'
closed_at = <Date 2013-04-06.05:29:33.531>
created_at = <Date 2012-11-02.18:23:35.015>
labels = ['library', 'performance']
title = "re._compiled_typed's lru_cache causes significant degradation of the mako_v2 bench"
updated_at = <Date 2013-04-06.05:29:33.530>
user = 'https://github.com/pjenvey'

bugs.python.org fields:

activity = <Date 2013-04-06.05:29:33.530>
actor = 'serhiy.storchaka'
assignee = 'serhiy.storchaka'
closed = True
closed_date = <Date 2013-04-06.05:29:33.531>
closer = 'serhiy.storchaka'
components = ['Library (Lib)']
creation = <Date 2012-11-02.18:23:35.015>
creator = 'pjenvey'
dependencies = []
files = ['27877', '27895']
hgrepos = []
issue_num = 16389
keywords = ['patch', '3.2regression', '3.3regression']
message_count = 27.0
messages = ['174550', '174559', '174563', '174566', '174567', '174570', '174598', '174599', '174626', '174630', '174638', '174772', '174918', '174924', '174927', '174993', '175037', '181601', '182192', '182199', '183856', '183857', '183913', '183917', '183967', '183968', '184353']
nosy_count = 15.0
nosy_names = ['barry', 'brett.cannon', 'rhettinger', 'terry.reedy', 'jcea', 'ncoghlan', 'pitrou', 'pjenvey', 'ezio.melotti', 'zzzeek', 'asvetlov', 'python-dev', 'sbt', 'serhiy.storchaka', 'bdkearns']
pr_nums = []
priority = 'high'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue16389'
versions = ['Python 3.2', 'Python 3.3', 'Python 3.4']

[pjenvey]

bpo-9396 replaced a few caches in the stdlib w/ lru_cache, this made the mako_v2 benchmark on Python 3 almost 3x slower than 2.7

The benchmark results are good now that Mako was changed to cache the re itself, but the problem still stands that lru_cache seems to hurt the perf of inline res compared to 2.7. The fix for Mako did not affect the 2.7 benchmark numbers

See more info here:

http://mail.python.org/pipermail/python-dev/2012-November/122521.html

[pitrou]

lru_cache() seems to use a complicated make_key() function, which is invoked on each cache hit. The LRU logic is probably on the slow side too, compared to a hand-coded logic which would favour lookup cost over insertion / eviction cost.

[brettcannon]

Would be interesting to know what speed difference would occur if the statistics gathering was optional and turned off.

As for _make_key(), I wonder if (args, tuple(sorted(kwd.items()))) as a key would be any faster as a tuple's hash is derived from its contents and not the tuple itself (if I remember correctly). You could even special case when len(kwds) == 0 to skip the sorted(kwd.items()) overhead if it is worth it performance-wise.

[brettcannon]

Ditching the statistics only sped up regex_compile by 2%.

[pitrou]

Ditching the statistics only sped up regex_compile by 2%.

Does explicit compiling even go through the cache?
Regardless, the issue here is with performance of cache hits, not cache
misses. By construction, you cache something which is costly to compute,
so the overhead of a cache miss won't be very noticeable.

[brettcannon]

re.compile() calls _compile() which has the lru_cache decorator so it will trigger it. But you make a good point, Antoine, that it's the hit overhead here that we care about as long as misses don't get worse as the calculation of is to be cached should overwhelm anything the LRU does.

With a simplified _make_key() I can get regex_compile w/ cache clearing turned off to be 1.28x faster by making it be::

 if not typed:
 if len(kwds) == 0:
 return args, ()
 else:
 return args, tuple(sorted(kwds.items()))
 else:
 if len(kwds) == 0:
 return (tuple((type(arg), arg) for arg in args), ())
 else:
 return (tuple((type(arg), arg) for arg in args),
 tuple((type(v), (k, v)) for k, v in kwds.items()))

That might not be the fastest way to handle keyword arguments (since regex_compile w/ caching and leaving out the len(kwds) trick out becomes 1.13x slower), but at least for the common case of positional arguments it seems faster and the code is easier to read IMO.

[ncoghlan]

Did you try moving the existing single-argument fast path to before the main if statement in _make_key? That is:

 if not kwds and len(args) == 1:
 key = args[0]
 key_type = type(key)
 if key_type in fasttypes:
 if typed:
 return key, key_type
 return key

Such a special case is already present, but it's *after* a lot of the other processing *and* it doesn't fire when typed==True.

So instead of the simple 2-tuple creation above, you instead do the relatively wasteful:

args + tuple(type(v) for v in args)

[ezio-melotti]

re.compile() calls _compile() which has the lru_cache decorator so it
will trigger it.

What's the point of using the lru_cache for compiled regexes?
Unless I'm missing something, re.compile() should just return the compiled regex without going though lru_cache and needlessly wasting time and cache's slots.

[zzzeek]

in response to ezio, I poked around the source here, since I've never been sure if re.compile() cached its result or not. It seems to be the case in 2.7 and 3.2 also - 2.7 uses a local caching scheme and 3.2 uses functools.lru_cache, yet we don't see as much of a slowdown with 3.2.

so it seems like the caching behavior is precedent here, but I would revert re.py's caching scheme to the one used in 2.7 if the functools.lru_cache can't be sped up very significantly. ideally lru_cache would be native.

also does python include any kind of benchmarking unit tests ? over in SQLA we have an approach that fails if the call-counts of various functions, as measured by cProfile, fall outside of a known range. it's caught many issues like these for me.

[ncoghlan]

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.

[serhiy-storchaka]

This is not only 3.3 regression, this is also 3.2 regression. 3.1, 3.2 and 3.3 have different caching implementation.

Mikrobenchmark:
$ ./python -m timeit -s "import re" "re.match('', '')"

Results:
3.1: 2.61 usec per loop
3.2: 5.77 usec per loop
3.3: 11.8 usec per loop

[serhiy-storchaka]

Here is a patch which reverts 3.1 implementation (and adds some optimization).

Microbenchmark:
$ ./python -m timeit -s "import re" "re._compile('', 0)"

Results:
3.1: 1.45 usec per loop
3.2: 4.45 usec per loop
3.3: 9.91 usec per loop
3.4patched: 0.89 usec per loop

[ezio-melotti]

Attached a proof of concept that removes the caching for re.compile, as suggested in msg174599.