[issue16389] re._compiled_typed's lru_cache causes significant degradation of the mako_v2 bench
Changes by Serhiy Storchaka storch...@gmail.com: -- resolution: - fixed stage: test needed - committed/rejected status: open - closed ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16389 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16389] re._compiled_typed's lru_cache causes significant degradation of the mako_v2 bench
Roundup Robot added the comment: New changeset 6951d7b8d3ad by Serhiy Storchaka in branch '3.2': Issue #16389: Fixed an issue number in previos commit. http://hg.python.org/cpython/rev/6951d7b8d3ad New changeset 7b737011d822 by Serhiy Storchaka in branch '3.3': Issue #16389: Fixed an issue number in previos commit. http://hg.python.org/cpython/rev/7b737011d822 New changeset 6898e1afc216 by Serhiy Storchaka in branch 'default': Issue #16389: Fixed an issue number in previos commit. http://hg.python.org/cpython/rev/6898e1afc216 -- nosy: +python-dev ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16389 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16389] re._compiled_typed's lru_cache causes significant degradation of the mako_v2 bench
Serhiy Storchaka added the comment: Raymond, actually my patch reverts 3.1 logic. lru_cache used since 3.2. There are no any additional re cache tests in 3.2 or 3.1. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16389 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16389] re._compiled_typed's lru_cache causes significant degradation of the mako_v2 bench
Richard Oudkerk added the comment: Which does give me a thought - perhaps lru_cache in 3.4 could accept a key argument that is called as key(*args, **kwds) to derive the cache key? (that would be a separate issue, of course) Agreed. I suggested the same in an earlier post. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16389 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16389] re._compiled_typed's lru_cache causes significant degradation of the mako_v2 bench
Nick Coghlan added the comment: Raymond's plan sounds good to me. We may also want to tweak the 3.3 lru_cache docs to note the trade-offs involved in using it. Perhaps something like: As a general purpose cache, lru_cache needs to be quite pessimistic in deriving non-conflicting keys from the supplied arguments. When caching the results of CPU-bound calculations, the cost of deriving non-conflicting keys may need be assessed against the typical cost of the underlying calculation. Which does give me a thought - perhaps lru_cache in 3.4 could accept a key argument that is called as key(*args, **kwds) to derive the cache key? (that would be a separate issue, of course) -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16389 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16389] re._compiled_typed's lru_cache causes significant degradation of the mako_v2 bench
Raymond Hettinger added the comment: Serhiy, please go ahead an apply your patch. Be sure to restore the re cache tests that existed in Py3.2 as well. Thank you. -- assignee: rhettinger - serhiy.storchaka priority: normal - high stage: needs patch - test needed ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16389 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16389] re._compiled_typed's lru_cache causes significant degradation of the mako_v2 bench
Raymond Hettinger added the comment: A few thoughts: * The LRU cache was originally intended for IO bound calls not for tight, frequently computationally bound calls like re.compile. * The Py3.3 version of lru_cache() favors size optimizations (i.e. it uses only one dictionary instead of the two used by OrderedDict and keyword arguments are flattened into a single list instead of a nested structure). Also, the 3.3 version assures that __hash__ is not called more than one for a given key (this change helps objects that have a slow hash function and it helps solve a reentrancy problem with recursive cached function calls). The cost of these changes is that _make_key is slower than it was before. * I had hoped to get in a C version of _make_key before Py3.3 went out but I didn't have time. Going forward, the lru_cache() will likely have a C-implementation that is blindingly fast. * For the re module, it might make sense to return to custom logic in the re modue that implements size limited caching without the overhead of 1) LRU logic, 2) general purpose argument handling, 3) reentrancy or locking logic, and 4) without statistics tracking. -- assignee: - rhettinger ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16389 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16389] re._compiled_typed's lru_cache causes significant degradation of the mako_v2 bench
Raymond Hettinger added the comment: Until the lru_cache can be sped-up significantly, I recommend just accepting Serhiy's patch to go back to 3.2 logic in the regex module. In the meantime, I'll continue to work on improving speed of _make_key(). -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16389 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16389] re._compiled_typed's lru_cache causes significant degradation of the mako_v2 bench
Changes by Brian Kearns bdkea...@gmail.com: -- nosy: +brian.kearns ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16389 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16389] re._compiled_typed's lru_cache causes significant degradation of the mako_v2 bench
Terry J. Reedy added the comment: Since switching from a simple custom cache to the generalized lru cache made a major slowdown, I think the change should be reverted. A dict + either occasional clearing or a circular queue and a first-in, first-out discipline is quite sufficient. There is no need for the extra complexity of a last-used, first out discipline. -- nosy: +terry.reedy ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16389 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16389] re._compiled_typed's lru_cache causes significant degradation of the mako_v2 bench
Ezio Melotti added the comment: For 3.4 #14373 might solve the issue. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16389 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16389] re._compiled_typed's lru_cache causes significant degradation of the mako_v2 bench
Changes by Andrew Svetlov andrew.svet...@gmail.com: -- nosy: +asvetlov ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16389 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16389] re._compiled_typed's lru_cache causes significant degradation of the mako_v2 bench
Serhiy Storchaka added the comment: Maybe lru_cache() should have a key argument so you can specify a specialized key function. It would be interesting to look at the microbenchmarking results. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16389 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16389] re._compiled_typed's lru_cache causes significant degradation of the mako_v2 bench
Changes by Jesús Cea Avión j...@jcea.es: -- nosy: +jcea ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16389 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16389] re._compiled_typed's lru_cache causes significant degradation of the mako_v2 bench
Serhiy Storchaka added the comment: I think the lru_cache should be kept if possible (i.e. I'm -0.5 on your patch). This patch is only to show the upper level to which should be sought. I tried to optimize lru_cache(), but got only 15%. I'm afraid that serious optimization is impossible without rewriting lru_cache() on C. 2) avoid using it for regular expressions compiled with re.compile; I do not see how it can significantly affect performance. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16389 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16389] re._compiled_typed's lru_cache causes significant degradation of the mako_v2 bench
Richard Oudkerk added the comment: Maybe lru_cache() should have a key argument so you can specify a specialized key function. So you might have def _compile_key(args, kwds, typed): return args @functools.lru_cache(maxsize=500, key=_compile_key) def _compile(pattern, flags): ... -- nosy: +sbt ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16389 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16389] re._compiled_typed's lru_cache causes significant degradation of the mako_v2 bench
Ezio Melotti added the comment: Attached a proof of concept that removes the caching for re.compile, as suggested in msg174599. -- Added file: http://bugs.python.org/file27895/issue16389.diff ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16389 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16389] re._compiled_typed's lru_cache causes significant degradation of the mako_v2 bench
Serhiy Storchaka added the comment: Ezio, I agree with you, but I think this should be a separate issue. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16389 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16389] re._compiled_typed's lru_cache causes significant degradation of the mako_v2 bench
Ezio Melotti added the comment: I think the lru_cache should be kept if possible (i.e. I'm -0.5 on your patch). If this result in a slowdown (as the mako_v2 benchmark indicates), then there are two options: 1) optimize lru_cache; 2) avoid using it for regular expressions compiled with re.compile; Both the changes should improve the performances. This issue is about the re module, so I think it's ok to cover any changes to the re module here, and improvements to lru_cache (e.g. a faster make_key) should be moved to a new issue. If this is not enough to restore the performances we might decide to go back to a custom cache instead of using lru_cache. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16389 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16389] re._compiled_typed's lru_cache causes significant degradation of the mako_v2 bench
Serhiy Storchaka added the comment: 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 -- keywords: +patch Added file: http://bugs.python.org/file27877/re_compile_cache.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16389 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16389] re._compiled_typed's lru_cache causes significant degradation of the mako_v2 bench
mike bayer added the comment: 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. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16389 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16389] re._compiled_typed's lru_cache causes significant degradation of the mako_v2 bench
Nick Coghlan added the comment: 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. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16389 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16389] re._compiled_typed's lru_cache causes significant degradation of the mako_v2 bench
Serhiy Storchaka added the comment: 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 -- keywords: +3.2regression nosy: +serhiy.storchaka ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16389 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16389] re._compiled_typed's lru_cache causes significant degradation of the mako_v2 bench
New submission from Philip Jenvey: #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 -- components: Library (Lib) messages: 174550 nosy: brett.cannon, ncoghlan, pjenvey, rhettinger, zzzeek priority: normal severity: normal status: open title: re._compiled_typed's lru_cache causes significant degradation of the mako_v2 bench type: performance versions: Python 3.2, Python 3.3 ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16389 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16389] re._compiled_typed's lru_cache causes significant degradation of the mako_v2 bench
Changes by Ezio Melotti ezio.melo...@gmail.com: -- keywords: +3.3regression nosy: +ezio.melotti ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16389 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16389] re._compiled_typed's lru_cache causes significant degradation of the mako_v2 bench
Changes by Antoine Pitrou pit...@free.fr: -- stage: - needs patch versions: +Python 3.4 ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16389 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16389] re._compiled_typed's lru_cache causes significant degradation of the mako_v2 bench
Antoine Pitrou added the comment: 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. -- nosy: +pitrou ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16389 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16389] re._compiled_typed's lru_cache causes significant degradation of the mako_v2 bench
Brett Cannon added the comment: 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. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16389 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16389] re._compiled_typed's lru_cache causes significant degradation of the mako_v2 bench
Brett Cannon added the comment: Ditching the statistics only sped up regex_compile by 2%. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16389 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16389] re._compiled_typed's lru_cache causes significant degradation of the mako_v2 bench
Antoine Pitrou added the comment: 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. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16389 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16389] re._compiled_typed's lru_cache causes significant degradation of the mako_v2 bench
Brett Cannon added the comment: 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. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16389 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16389] re._compiled_typed's lru_cache causes significant degradation of the mako_v2 bench
Changes by Barry A. Warsaw ba...@python.org: -- nosy: +barry ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16389 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16389] re._compiled_typed's lru_cache causes significant degradation of the mako_v2 bench
Nick Coghlan added the comment: 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) -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16389 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com