Don't completely dump the regex cache when full

[rhettinger]

BPO	28293
Nosy	@warsaw, @rhettinger, @vstinner, @ezio-melotti, @methane, @serhiy-storchaka, @zhangyangyu
PRs	bpo-28293: The regex cache no longer completely dump when full. #3768
Files	re_cache_pop.diff re_cache_del_first.patch re_cache_ordered_dict_del_first.patch re_cache_ordered_dict_popitem.patch

^{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 2017-09-26.16:58:08.958>
created_at = <Date 2016-09-28.04:49:29.801>
labels = ['expert-regex', '3.7', 'library', 'performance']
title = "Don't completely dump the regex cache when full"
updated_at = <Date 2017-09-26.16:58:08.957>
user = 'https://github.com/rhettinger'

bugs.python.org fields:

activity = <Date 2017-09-26.16:58:08.957>
actor = 'serhiy.storchaka'
assignee = 'serhiy.storchaka'
closed = True
closed_date = <Date 2017-09-26.16:58:08.958>
closer = 'serhiy.storchaka'
components = ['Library (Lib)', 'Regular Expressions']
creation = <Date 2016-09-28.04:49:29.801>
creator = 'rhettinger'
dependencies = []
files = ['44852', '44853', '44854', '44855']
hgrepos = []
issue_num = 28293
keywords = ['patch']
message_count = 20.0
messages = ['277580', '277582', '277583', '277585', '277586', '277587', '277588', '277589', '277590', '277591', '277620', '277667', '277677', '277682', '278885', '278920', '278937', '283983', '303054', '303055']
nosy_count = 9.0
nosy_names = ['barry', 'rhettinger', 'vstinner', 'ezio.melotti', 'mrabarnett', 'methane', 'SilentGhost', 'serhiy.storchaka', 'xiang.zhang']
pr_nums = ['3768']
priority = 'low'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue28293'
versions = ['Python 3.7']

[rhettinger]

When the regex cache gets filled, it is cleared in its entirety. Instead, it only needs to evict one arbitrary entry. This will save the us from having to rebuild and recache frequently used regexes.

[serhiy-storchaka]

LGTM.

[zhangyangyu]

But with the compact dict implementation, popitem is not going to evict an arbitrary entry but always the last one. Will this cause two interchangeably used regexes always need to recompile?

[serhiy-storchaka]

Nice catch! Here is a patch that deletes the first key.

[rhettinger]

Perhaps: _cache.pop(next(iter(_cache)))

The for-loop version indirect about what it is trying to do and relies on an obscure quirk of exactly when it is an error to mutate while iterating.

I do like that the side-effect of the compact dict is that is lets us choose the oldest entry to evict.

[serhiy-storchaka]

Perhaps: _cache.pop(next(iter(_cache)))

This can raise KeyError if the cache is cleared in other thread. And it is a little slower.

I remember why I didn't propose this idea earlier. This depends on the ordering of dict. But this is implementation detail, and in other Python implementation this can cause recompiling two interchangeably used regexes. No, this no longer LGTM.

Maybe use OrderedDict? But this adds heavy dependency to the re module.

Yet one idea: use two caches. Look first in the one cache, then in the other. When the first cache full, clear the second cache and swap caches.

[serhiy-storchaka]

Maybe use OrderedDict? But this adds heavy dependency to the re module.

We can use the same trick as in the enum module. Here is a patch.

[zhangyangyu]

Why not OrderedDict.popitem(last=False)?

[rhettinger]

This has gotten crazy. I withdraw the suggestion.