Improve performances of fnmatch.translate
#122288
Comments
The current implementation does this to minimise string concatenation, i.e. it defers |
|
Thanks for noticing this. I think there are two things to consider: Calling My benchmarks show that Now, there is one case where the new algorithm might be slower. This is when you only have a single character in the pending list of characters to escape, namely Here the performances are almost identical, and this is what I would have expected. I've also added a comment: # Handling '?' one at a time seems to more efficient
# even if there are consecutive '?' that could have
# been written directly.The reason why it's more efficient is because the fast path is actually rarer than the slow path. So, looping over the consecutive '?' is heuristically less efficient. The same analysis could be applied to the case of consecutive One reason is that using an inner |
|
Thank you very much for the explanation! Q: could the cost of diff --git a/Lib/fnmatch.py b/Lib/fnmatch.py
index 73acb1fe8d4..dc9bf122e39 100644
--- a/Lib/fnmatch.py
+++ b/Lib/fnmatch.py
@@ -149,11 +149,14 @@ def _translate(pat, STAR, QUESTION_MARK):
stuff = '\\' + stuff
add(f'[{stuff}]')
else:
- add(re.escape(c))
+ add(_escape_char(c))
assert i == n
return res
+_escape_char = functools.lru_cache(maxsize=32768)(re.escape)
+
+
def _join_translated_parts(inp, STAR):
# Deal with STARs.
res = [] |
|
It could be, I didn't check this alternative. Also, we could simply make it faster by a simple dictionary lookup because the implementation is private and we're supposed to have only strings being passed. Alternatively, we could inline the escaping directly. I'll try your suggestion today. |
|
Huh, so your approach is actually the best (the cache is cleared before each benchmark but since there are many iterations for each row, the first call which caches the result is probably negligible). There are significant performance gains for each runs. I totally forgot about having the possibility of caching |
|
I'll also update the C implementation. I discovered two other optimizations that I could on the C side but I think the C implementation is not that worth it unless you want a x3 improvement (here we are roughly x1.75, but I think we can go up to x2.8-x3.5 in C). EDIT: We eventually were able to gain a factor 6 improvement but since the maintaince cost is high (I would be the one responsible for it probably and I should confess that I'd prefer maintining the Python implementation), I decided to give up on the C implementation. |
Improve performance of this function by a factor of 1.7x. Co-authored-by: Barney Gale <barney.gale@gmail.com>
|
Closing since completed. |
…122289) Improve performance of this function by a factor of 1.7x. Co-authored-by: Barney Gale <barney.gale@gmail.com>
Uh oh!
There was an error while loading. Please reload this page.
Feature or enhancement
Proposal:
I implemented
fnmatch.translateandfnmatch.filterin C in #121446 but the performances forfnmatch.filterare less pronounced than those infnmatch.translate. While I believe that the factor 2x improvement brought by the C implementation is worthwhile forfnmatch.translate, this comes at a high maintenance cost. Instead, I translated (no pun intended) the implementation in Python and obtained the following timings (PGO build):It's not as good as the benchmarks reported in #121445, but I think this could be considered. Note that the improvements are brought by a new (but equivalent) algorithm during the translation phase. Currently, the translation algorithm does:
re.escape(c)for every non-special character (i.e, not for groups beginning by?*[).Our (Barney and me) implementation instead does the following:
re.escapeso that the lookup is faster.That way, I can easily merge parts during the second phase (technically, it'd be possible to do it in one phase but two passes makes it clearer).
Has this already been discussed elsewhere?
No response given
Links to previous discussion of this feature:
No response
Linked PRs
fnmatch.translate#122289The text was updated successfully, but these errors were encountered: