homepage

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.

(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
 (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.40 rindex (fastsearch)
 ========== late match, two characters
 4.34 2.36 ("C"+"AB"*300).rfind("CA") (classic)
 4.44 2.36 ("C"+"AB"*300).rindex("CA") (classic)
 2.10 2.31 ("C"+"AB"*300).rfind("CA") (fastsearch)
 2.10 2.32 ("C"+"AB"*300).rindex("CA") (fastsearch)
 ========== no match, two characters
 14.12 13.46 ("AB"*1000).rfind("BC") (classic)
 7.67 8.26 ("AB"*1000).rfind("BC") (fastsearch)

Need additional patch for rpartition and rsplit on string, unicode and
bytearray objects.

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" too.
I propose to commit these changes before looking for further improvements.
(I plan to refactor some functions and macro to Objects/stringlib)

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 ;-) »

I reupload the patch fixed (sorry).

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 for working on this!

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.
But don't you think we should do this incrementally, i.e. commit the
current patch before refactoring more code?
I will remove the "#if 1 /* USE_FAST */".

> 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 stringlib.
(anything which doesn't start with Py* shouldn't be exported in the
official include files)
> But don't you think we should do this incrementally, i.e. commit the
> current patch before refactoring more code?
Well, if STRINGLIB_CMP isn't used anymore, removing it should be part of
the current issue. There's no reason to leave dead code in the source
tree. I agree that further cleanups can be part of another issue.

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
at least on the principle this looks good.
Fredrik, do you want to take a look?

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

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 previous character is part of pattern */
+ if (!(mask & (1 << (s[i-1] & 0x1F))))

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 2 (msg97039):
s, p = "ABCDBCBCF", "BCB"
s.rfind(p)
# i = 6 is first candidate, but "BCF" != "BCB"
# then s[i-m] = "D" is not part of pattern
# so we skip 3 chars: next loop is i = 2.. and it fails!
I've tested many examples to understand and verify the algorithm.

> I checked the code, and it is the right thing:
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? 
IIRC, that was the reason this wasn't implemented previously.

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 implemented for
find/index/partition.

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).
I've ommitted the tests you had added for issue7458.
Thank you!

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 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 :)