New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Implement fastsearch algorithm for rfind/rindex #51711
Comments
While looking at bpo-7458 I stopped on: /* XXX - create reversefastsearch helper! */ Here is the patch which is just the translation of the same algorithm Note: it supersedes patch for 7458. |
(removed comment which should not be copied) |
Additional test cases for rfind. |
Bench results show the benefit. And attached patch for stringbench tool. |
There's a typo in the patch for stringbench. Updated patch (with rindex tests, too). |
Updated benchmarks. str unicode ========== late match, 100 characters ========== late match, two characters ========== no match, two characters |
Need additional patch for rpartition and rsplit on string, unicode and |
Updated patch with optimization for:
And an optimization was implemented in r46398 but never used because I propose to commit these changes before looking for further improvements. |
Actually, the USE_FLAG macro was removed in r46367 (not 46366). « needforspeed: remove remaining USE_FAST macros; if fastsearch was |
I reupload the patch fixed (sorry). |
Some things:
Thanks for working on this! |
Actually I see different macros which do the same thing: I will consider I can prepare a "all-in-one" patch which fixes all these things. I will remove the "#if 1 /* USE_FAST */". |
STRINGLIB_CMP, as the name implies, should only be used by stringlib.
Well, if STRINGLIB_CMP isn't used anymore, removing it should be part of |
Removing "slow" parts and unnused macros STRINGLIB_CMP and USE_FAST. |
I haven't reviewed the algorithm (I don't know if I will, honestly), but |
New benchmarks (and patch for the benchmark tool). Best improvement is reached with such expression: String (classic): 93.14 ms Unicode (classic): 78.62 ms |
Looking a bit more at the patch: + /* miss: check if previous character is part of pattern */ From what I understand, this should be s[i-m]. Same here: + /* skip: check if previous character is part of pattern */ |
I checked the code, and it is the right thing: Example 1 (fastsearch): s, p = "ABCDEABCF", "BCD" # i = 6 is first candidate, but "BCF" != "BCD" Example 2 (msg97039): s, p = "ABCDBCBCF", "BCB" # i = 6 is first candidate, but "BCF" != "BCB" I've tested many examples to understand and verify the algorithm. |
Indeed, you are right. My bad! |
I will take a last look at it and commit if I see nothing wrong. |
Are there any simple, common cases that are made slower by this patch? |
The benchmark tests show significant improvements in most cases up to 10 And I found no test case which show performance regression (using the Moreover, the very same algorithm is already implemented for |
I've added a version number to stringbench and committed the changes in r77240. |
The main patch has been committed in r77241 (trunk) and r77246 (py3k). |
Thanks Florent!
The original fastsearch implementation has a couple of special cases to make sure it's faster than the original code in all cases. The reason it wasn't implemented for reverse search was more a question of developer time constraints; reverse search isn't nearly as common as forward search, and we had other low-hanging fruit to deal with. (btw, while it's great that someone finally got around to fix this, it wouldn't surprise me if replacing the KMP implementation in SRE with a fastsearch would save as many CPU cycles worldwide as this 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:
bugs.python.org fields:
The text was updated successfully, but these errors were encountered: