[issue7462] Implement fastsearch algorithm for rfind/rindex

Changes by Ezio Melotti : -- nosy: +ezio.melotti ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.pyt

[issue7462] Implement fastsearch algorithm for rfind/rindex

Fredrik Lundh added the comment: Thanks Florent! > Are there any simple, common cases that are made slower by this patch? 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

[issue7462] Implement fastsearch algorithm for rfind/rindex

Antoine Pitrou added the comment: The main patch has been committed in r77241 (trunk) and r77246 (py3k). I've ommitted the tests you had added for issue7458. Thank you! -- resolution: -> fixed stage: commit review -> committed/rejected status: open -> closed __

[issue7462] Implement fastsearch algorithm for rfind/rindex

Antoine Pitrou added the comment: I've added a version number to stringbench and committed the changes in r77240. -- ___ Python tracker ___ __

[issue7462] Implement fastsearch algorithm for rfind/rindex

Florent Xicluna added the comment: The benchmark tests show significant improvements in most cases up to 10 times faster. And I found no test case which show performance regression (using the "stringbench" benchmark from GvR, and additional tests). Moreover, the very same algorithm is already

[issue7462] Implement fastsearch algorithm for rfind/rindex

Raymond Hettinger added the comment: Are there any simple, common cases that are made slower by this patch? IIRC, that was the reason this wasn't implemented previously. -- nosy: +rhettinger ___ Python tracker ___

[issue7462] Implement fastsearch algorithm for rfind/rindex

Antoine Pitrou added the comment: I will take a last look at it and commit if I see nothing wrong. -- assignee: -> pitrou priority: -> normal stage: patch review -> commit review versions: -Python 2.6, Python 3.1 ___ Python tracker

[issue7462] Implement fastsearch algorithm for rfind/rindex

Antoine Pitrou added the comment: > I checked the code, and it is the right thing: Indeed, you are right. My bad! -- ___ Python tracker ___ _

[issue7462] Implement fastsearch algorithm for rfind/rindex

Florent Xicluna added the comment: I checked the code, and it is the right thing: Example 1 (fastsearch): s, p = "ABCDEABCF", "BCD" s.rfind(p) # i = 6 is first candidate, but "BCF" != "BCD" # then s[i-1] = "A" is not part of pattern # so we skip 3 chars: next loop is i = 2 # etc... Example

[issue7462] Implement fastsearch algorithm for rfind/rindex

Antoine Pitrou added the comment: Looking a bit more at the patch: +/* miss: check if previous character is part of pattern */ +if (!(mask & (1 << (s[i-1] & 0x1F >From what I understand, this should be s[i-m]. Same here: +/* skip: check if p

[issue7462] Implement fastsearch algorithm for rfind/rindex

Changes by Florent Xicluna : Removed file: http://bugs.python.org/file15638/bench_rfind_algorithms_v2.diff ___ Python tracker ___ ___ Python-bu

[issue7462] Implement fastsearch algorithm for rfind/rindex

Florent Xicluna added the comment: New benchmarks (and patch for the benchmark tool). Best improvement is reached with such expression: s="ABC"*33; (s+"E"+("D"+s)*500).rfind(s+"E") (*100) String (classic): 93.14 ms String (fast): 8.78 ms Unicode (classic): 78.62 ms Unicode (fast): 9

[issue7462] Implement fastsearch algorithm for rfind/rindex

Changes by Florent Xicluna : Added file: http://bugs.python.org/file15655/stringbench_fixes_and_additions_v3.diff ___ Python tracker ___ ___ P

[issue7462] Implement fastsearch algorithm for rfind/rindex

Changes by Florent Xicluna : Removed file: http://bugs.python.org/file15654/stringbench_fixes_and_additions_v2.diff ___ Python tracker ___ ___

[issue7462] Implement fastsearch algorithm for rfind/rindex

Changes by Florent Xicluna : Added file: http://bugs.python.org/file15654/stringbench_fixes_and_additions_v2.diff ___ Python tracker ___ ___ P

[issue7462] Implement fastsearch algorithm for rfind/rindex

Changes by Florent Xicluna : Removed file: http://bugs.python.org/file15652/stringbench_fixes_and_additions.diff ___ Python tracker ___ ___ Py

[issue7462] Implement fastsearch algorithm for rfind/rindex

Changes by Florent Xicluna : Added file: http://bugs.python.org/file15652/stringbench_fixes_and_additions.diff ___ Python tracker ___ ___ Pyth

[issue7462] Implement fastsearch algorithm for rfind/rindex

Changes by Florent Xicluna : Removed file: http://bugs.python.org/file15637/stringbench_rfind_rindex.diff ___ Python tracker ___ ___ Python-bug

[issue7462] Implement fastsearch algorithm for rfind/rindex

Antoine Pitrou added the comment: I haven't reviewed the algorithm (I don't know if I will, honestly), but at least on the principle this looks good. Fredrik, do you want to take a look? -- nosy: +effbot ___ Python tracker

[issue7462] Implement fastsearch algorithm for rfind/rindex

Changes by Florent Xicluna : Removed file: http://bugs.python.org/file15647/issue7462_fastsearch_v2.diff ___ Python tracker ___ ___ Python-bugs

[issue7462] Implement fastsearch algorithm for rfind/rindex

Florent Xicluna added the comment: Removing "slow" parts and unnused macros STRINGLIB_CMP and USE_FAST. -- Added file: http://bugs.python.org/file15648/issue7462_fastsearch_v3.diff ___ Python tracker __

[issue7462] Implement fastsearch algorithm for rfind/rindex

Antoine Pitrou added the comment: > Actually I see different macros which do the same thing: I will consider > reusing STRINGLIB_CMP to re-define PyUNICODE_MATCH and PySTRING_MATCH > (or create aliases if they have the same signature). STRINGLIB_CMP, as the name implies, should only be used by

[issue7462] Implement fastsearch algorithm for rfind/rindex

Florent Xicluna added the comment: Actually I see different macros which do the same thing: I will consider reusing STRINGLIB_CMP to re-define PyUNICODE_MATCH and PySTRING_MATCH (or create aliases if they have the same signature). I can prepare a "all-in-one" patch which fixes all these things.

[issue7462] Implement fastsearch algorithm for rfind/rindex

Antoine Pitrou added the comment: Some things: - is STRINGLIB_CMP still used? if not, it should be removed (use grep :-)) - please don't use "#if 1" - if USE_FAST isn't used anymore, it should be remove as well - did you check that rpartition, split and friends were sped up by the patch? Thanks

[issue7462] Implement fastsearch algorithm for rfind/rindex

Florent Xicluna added the comment: I reupload the patch fixed (sorry). -- Added file: http://bugs.python.org/file15647/issue7462_fastsearch_v2.diff ___ Python tracker ___ ___

[issue7462] Implement fastsearch algorithm for rfind/rindex

Changes by Florent Xicluna : Removed file: http://bugs.python.org/file15644/fastsearch_rfind_v2.patch ___ Python tracker ___ ___ Python-bugs-li

[issue7462] Implement fastsearch algorithm for rfind/rindex

Changes by Florent Xicluna : Removed file: http://bugs.python.org/file15507/fastsearch_rfind.patch ___ Python tracker ___ ___ Python-bugs-list

[issue7462] Implement fastsearch algorithm for rfind/rindex

Florent Xicluna added the comment: Actually, the USE_FLAG macro was removed in r46367 (not 46366). « needforspeed: remove remaining USE_FAST macros; if fastsearch was broken, someone would have noticed by now ;-) » -- ___ Python tracker

[issue7462] Implement fastsearch algorithm for rfind/rindex

Florent Xicluna added the comment: Updated patch with optimization for: * rfind * rindex * rsplit * rpartition And an optimization was implemented in r46398 but never used because "#define USE_FAST" was removed 2 hours before: r46366. ==> I changed this to activate optimization on "S.split"

[issue7462] Implement fastsearch algorithm for rfind/rindex

Florent Xicluna added the comment: Need additional patch for rpartition and rsplit on string, unicode and bytearray objects. -- stage: patch review -> needs patch ___ Python tracker

[issue7462] Implement fastsearch algorithm for rfind/rindex

Changes by Florent Xicluna : Removed file: http://bugs.python.org/file15636/bench_rfind_algorithms.diff ___ Python tracker ___ ___ Python-bugs-

[issue7462] Implement fastsearch algorithm for rfind/rindex

Florent Xicluna added the comment: Updated benchmarks. strunicode (ms) (ms) == late match, 100 characters s="ABC"*33; ("E"+s+("D"+s)*500).rfind("E"+s) 32.89 15.65 rfind (classic) 32.81 15.63 rindex (classic) 11.77 13.27 rfind (fastsearch) 11.78 13

[issue7462] Implement fastsearch algorithm for rfind/rindex

Changes by Florent Xicluna : Removed file: http://bugs.python.org/file15635/stringbench_rfind.diff ___ Python tracker ___ ___ Python-bugs-list

[issue7462] Implement fastsearch algorithm for rfind/rindex

Florent Xicluna added the comment: There's a typo in the patch for stringbench. Updated patch (with rindex tests, too). -- Added file: http://bugs.python.org/file15637/stringbench_rfind_rindex.diff ___ Python tracker

[issue7462] Implement fastsearch algorithm for rfind/rindex

Changes by Florent Xicluna : Added file: http://bugs.python.org/file15636/bench_rfind_algorithms.diff ___ Python tracker ___ ___ Python-bugs-li

[issue7462] Implement fastsearch algorithm for rfind/rindex

Florent Xicluna added the comment: Bench results show the benefit. And attached patch for stringbench tool. -- Added file: http://bugs.python.org/file15635/stringbench_rfind.diff ___ Python tracker ___

[issue7462] Implement fastsearch algorithm for rfind/rindex

Florent Xicluna added the comment: Additional test cases for rfind. -- Added file: http://bugs.python.org/file15634/issue7462_string_tests.diff ___ Python tracker ___ ___

[issue7462] Implement fastsearch algorithm for rfind/rindex

Changes by flox : Removed file: http://bugs.python.org/file15505/fastsearch_rfind.patch ___ Python tracker ___ ___ Python-bugs-list mailing lis

[issue7462] Implement fastsearch algorithm for rfind/rindex

flox added the comment: (removed comment which should not be copied) -- Added file: http://bugs.python.org/file15507/fastsearch_rfind.patch ___ Python tracker ___ ___

[issue7462] Implement fastsearch algorithm for rfind/rindex

New submission from flox : While looking at issue7458 I stopped on: /* XXX - create reversefastsearch helper! */ Here is the patch which is just the translation of the same algorithm already implemented for "find/index". http://effbot.org/zone/stringlib.htm Note: it supersedes patch for 7458