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.

LGTM.

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?

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

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.

> 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.

> 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.

Why not OrderedDict.popitem(last=False)?

This has gotten crazy.  I withdraw the suggestion.

> Why not OrderedDict.popitem(last=False)?

Yes, this should work. Here is a patch.

Serhiy, your patch doesn't seem to apply cleanly. Also, it's perhaps worth opening the issue if you'd like to continue working on it.

It is applied cleanly on the default branch. I don't think there is a need to open a new issue. The last patch implements the original Raymond's intention, but taking into account all comments: drops the oldest item, doesn't depend on implementation details of dict, thread-safe.

I would rather not introduce an OrderedDict dependency to the re module while other implementations are using the pure python version or where the OD implementation is in flux.  This is a barely worth it proposal, so we should either make a modest, minimalistic change or just drop it.   Really, its too bad that the regex got contorted in a way that precluded the use of the lru_cache (DEBUG isn't the central feature of regex and is only minimally useful).

The re module now depends on the enum module, and the latter already depends on OrderedDict. Thus the patch doesn't introduce new dependency. Python implementation of OrderedDict doesn't override __getitem__ and therefore don't slow down the common case. I considered all this.

In contrary, Python implementation of lru_cache slows down the code (that is why using it was dropped in the past). But I did not object to this because re.sub() is less used than re.match() or re.search() and already is much slower.

Can't we redesign the function to reuse @functools.lru_cache(_MAXCACHE) but take care of the debug flag? For example, split the function in smaller parts.

This is unlikely possible with current API of lru_cache. Testing flags before looking up in a cache adds an overhead.

re_cache_ordered_dict_popitem.patch: LGTM, it can be pushed to the default branch.

--

"This is unlikely possible with current API of lru_cache. Testing flags before looking up in a cache adds an overhead."

Oh wait, I looked at the code and this case is complex because the function depends on the current locale if the LOCALE flag is set... A lookup in the the cache requires to get the current locale, but not if the LOCALE flag is not set... It seems too complex for @lru_cache().

LGTM for re_cache_ordered_dict_popitem.patch

New changeset 114454e9f6addbcb364e9a37102c8131ae2da1dd by Serhiy Storchaka in branch 'master':
bpo-28293: Don't completely dump the regex cache when full. (#3768)
https://github.com/python/cpython/commit/114454e9f6addbcb364e9a37102c8131ae2da1dd

Thank you for your reviews.

Currently the caching logic is simpler, it no longer depends on the LOCALE flag and the current locale. But it still is too complex for lru_cache. It needs a way to bypass caching based on arguments or result.