Repository navigation
Improve performances of fnmatch.translate #122288
Description
Feature or enhancement
Proposal:
I implemented fnmatch.translate and fnmatch.filter in C in #121446 but the performances for fnmatch.filter are less pronounced than those in fnmatch.translate. While I believe that the factor 2x improvement brought by the C implementation is worthwhile for fnmatch.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):
+------------------------------------------+-----------------------+-----------------------+
| Benchmark | fnmatch-translate-ref | fnmatch-translate-py |
+==========================================+=======================+=======================+
| abc/[!]b-ac-z9-1]/def/\*?/*/**c/?*[][!] | 6.09 us | 3.99 us: 1.53x faster |
+------------------------------------------+-----------------------+-----------------------+
| !abc/[!]b-ac-z9-1]/def/\*?/*/**c/?*[][!] | 6.39 us | 4.07 us: 1.57x faster |
+------------------------------------------+-----------------------+-----------------------+
| a**?**cd**?**??k*** | 2.24 us | 1.51 us: 1.49x faster |
+------------------------------------------+-----------------------+-----------------------+
| a/**/b/**/c | 1.97 us | 1.12 us: 1.76x faster |
+------------------------------------------+-----------------------+-----------------------+
| man/man1/bash.1 | 3.00 us | 1.21 us: 2.48x faster |
+------------------------------------------+-----------------------+-----------------------+
| a*b*c*d*e*f*g*h*i*j*k*l*m*n*o** | 5.40 us | 3.33 us: 1.62x faster |
+------------------------------------------+-----------------------+-----------------------+
| Geometric mean | (ref) | 1.71x faster |
+------------------------------------------+-----------------------+-----------------------+
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:
- Do not compress consecutive '*' into 1 within the same loop iteration.
- Use a sentinel to indicate a wildcard instead.
- Add to a list
re.escape(c)for every non-special character (i.e, not for groups beginning by?*[). - In a second phase, merge the groups delimited by the sentinels in order to produce the final regex.
Our (Barney and me) implementation instead does the following:
- Cache
re.escapeso that the lookup is faster. - Remember the positions of '*' in the above split instead of using a sentinel object.
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
Activity
barneygale commentedon Aug 14, 2024
The current implementation does this to minimise string concatenation, i.e. it defers
join()ing until its unavoidable. This should be faster, so I'm surprised you're getting different results! It's quite possible I've misunderstood your patch though?picnixz commentedon Aug 15, 2024
Thanks for noticing this. I think there are two things to consider:
Calling
re.escape(c)at every loop iteration (most of the time we don't have*?[but rather "normal" characters to be escaped) is probably more costly. You have a call toisinstanceand a call tostr.translate. By looking at the implementation ofstr.translate, each timestr.translateis called, a writer is allocated on the heap, so it slows down the entire algorithm at every call. In particular, if I need to successively callres.append(re.escape(c))a lot of time (which is what happens in practice), then it's probably faster to dores.append(re.escape(''.join(x)))orres.extend(re.escape(c) for c in x).My benchmarks show that
res.append(re.escape(''.join(x)))is faster thanres.extend(re.escape(c) for c in x). I suspect this is clearly because of the overhead ofre.escape.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
x = [c]. You can see that the improvements are less pronounced for the casea**?**cd**?**??k***but still faster. I've added an other case to illustrate an extreme case:Here the performances are almost identical, and this is what I would have expected. I've also added a comment:
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
*so I compared two implementations (the one in the PR and the one where I keep the treatment of*by not advancing the index in theif c == '*'but guarding theadd(STAR)with anotherif). Benchmarks suggested that using a while to skip over successive*is slightly faster for the other cases (the casea*b*c*d*e*f*g*h*i*j*k*l*m*n*o**is obvisouly slower with a while loop but not that much):One reason is that using an inner
whilesaves a check on whether we need to push the pending characters or not and that we can jump faster to the next character that is not*.barneygale commentedon Aug 16, 2024
Thank you very much for the explanation!
Q: could the cost of
re.escape()be ameliorated with anlru_cache()instead? e.g.:picnixz commentedon Aug 17, 2024
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.
picnixz commentedon Aug 17, 2024
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
re.escape.I'll try to even reduce the memory cost by simply inlining(no need to have that much micro-optimization; it will be hard to maintain so let's keep your solution)re.escape.picnixz commentedon Aug 17, 2024
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.
gh-122288: Improve performances of `fnmatch.translate` (#122289)
picnixz commentedon Nov 27, 2024
Closing since completed.
pythongh-122288: Improve performances of `fnmatch.translate` (python#…