Implement fastsearch algorithm for rfind/rindex

[florentx]

BPO	7462
Nosy	@rhettinger, @pitrou, @ezio-melotti, @florentx
Files	issue7462_string_tests.diff: Patch, apply to trunk issue7462_fastsearch_v3.diff: Patch, apply to trunk stringbench_fixes_and_additions_v3.diff: Patch for sandbox/trunk/stringbench/ bench_rfind_algorithms_v3.diff: Benchmark Results (including rpartition and rsplit)

^{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:

assignee = 'https://github.com/pitrou'
closed_at = <Date 2010-01-02.21:42:27.021>
created_at = <Date 2009-12-08.22:46:43.272>
labels = ['interpreter-core', 'performance']
title = 'Implement fastsearch algorithm for rfind/rindex'
updated_at = <Date 2010-01-04.09:26:26.641>
user = 'https://github.com/florentx'

bugs.python.org fields:

activity = <Date 2010-01-04.09:26:26.641>
actor = 'ezio.melotti'
assignee = 'pitrou'
closed = True
closed_date = <Date 2010-01-02.21:42:27.021>
closer = 'pitrou'
components = ['Interpreter Core']
creation = <Date 2009-12-08.22:46:43.272>
creator = 'flox'
dependencies = []
files = ['15634', '15648', '15655', '15656']
hgrepos = []
issue_num = 7462
keywords = ['patch']
message_count = 25.0
messages = ['96157', '96163', '96724', '96725', '96726', '96727', '96729', '96738', '96739', '96743', '96747', '96748', '96749', '96750', '96757', '96771', '97039', '97084', '97087', '97103', '97105', '97106', '97146', '97148', '97200']
nosy_count = 5.0
nosy_names = ['effbot', 'rhettinger', 'pitrou', 'ezio.melotti', 'flox']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue7462'
versions = ['Python 2.7', 'Python 3.2']

[florentx]

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
already implemented for "find/index".
http://effbot.org/zone/stringlib.htm

Note: it supersedes patch for 7458.

[florentx]

(removed comment which should not be copied)

[florentx]

Additional test cases for rfind.

[florentx]

Bench results show the benefit.

And attached patch for stringbench tool.

[florentx]

There's a typo in the patch for stringbench.

Updated patch (with rindex tests, too).

[florentx]

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)

[florentx]

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

[florentx]

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)

[florentx]

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

[florentx]

I reupload the patch fixed (sorry).

[pitrou]

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!

[florentx]

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 */".

[pitrou]

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.