Fredrik Lundh fred...@effbot.org 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
Changes by Ezio Melotti ezio.melo...@gmail.com:
--
nosy: +ezio.melotti
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue7462
___
___
Python-bugs-list
Antoine Pitrou pit...@free.fr added the comment:
I've added a version number to stringbench and committed the changes in r77240.
--
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue7462
___
Antoine Pitrou pit...@free.fr 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
Florent Xicluna la...@yahoo.fr 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...
Antoine Pitrou pit...@free.fr added the comment:
I checked the code, and it is the right thing:
Indeed, you are right. My bad!
--
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue7462
___
Antoine Pitrou pit...@free.fr 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
Raymond Hettinger rhettin...@users.sourceforge.net 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
Florent Xicluna la...@yahoo.fr 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
Antoine Pitrou pit...@free.fr 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:
Florent Xicluna la...@yahoo.fr 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
Florent Xicluna la...@yahoo.fr 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
Changes by Florent Xicluna la...@yahoo.fr:
Removed file: http://bugs.python.org/file15507/fastsearch_rfind.patch
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue7462
___
Changes by Florent Xicluna la...@yahoo.fr:
Removed file: http://bugs.python.org/file15644/fastsearch_rfind_v2.patch
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue7462
___
Florent Xicluna la...@yahoo.fr added the comment:
I reupload the patch fixed (sorry).
--
Added file: http://bugs.python.org/file15647/issue7462_fastsearch_v2.diff
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue7462
Antoine Pitrou pit...@free.fr 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
Florent Xicluna la...@yahoo.fr 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
Florent Xicluna la...@yahoo.fr 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 rep...@bugs.python.org
Changes by Florent Xicluna la...@yahoo.fr:
Removed file: http://bugs.python.org/file15647/issue7462_fastsearch_v2.diff
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue7462
___
Antoine Pitrou pit...@free.fr 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
Changes by Florent Xicluna la...@yahoo.fr:
Removed file: http://bugs.python.org/file15637/stringbench_rfind_rindex.diff
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue7462
___
Changes by Florent Xicluna la...@yahoo.fr:
Added file:
http://bugs.python.org/file15652/stringbench_fixes_and_additions.diff
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue7462
___
Changes by Florent Xicluna la...@yahoo.fr:
Removed file:
http://bugs.python.org/file15652/stringbench_fixes_and_additions.diff
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue7462
___
Changes by Florent Xicluna la...@yahoo.fr:
Added file:
http://bugs.python.org/file15654/stringbench_fixes_and_additions_v2.diff
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue7462
___
Changes by Florent Xicluna la...@yahoo.fr:
Removed file:
http://bugs.python.org/file15654/stringbench_fixes_and_additions_v2.diff
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue7462
___
Changes by Florent Xicluna la...@yahoo.fr:
Added file:
http://bugs.python.org/file15655/stringbench_fixes_and_additions_v3.diff
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue7462
___
Florent Xicluna la...@yahoo.fr 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
Changes by Florent Xicluna la...@yahoo.fr:
Removed file: http://bugs.python.org/file15638/bench_rfind_algorithms_v2.diff
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue7462
___
Changes by Florent Xicluna la...@yahoo.fr:
Added file: http://bugs.python.org/file15636/bench_rfind_algorithms.diff
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue7462
___
Florent Xicluna la...@yahoo.fr 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
Changes by Florent Xicluna la...@yahoo.fr:
Removed file: http://bugs.python.org/file15635/stringbench_rfind.diff
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue7462
___
Florent Xicluna la...@yahoo.fr 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)
Changes by Florent Xicluna la...@yahoo.fr:
Removed file: http://bugs.python.org/file15636/bench_rfind_algorithms.diff
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue7462
___
Florent Xicluna la...@yahoo.fr added the comment:
Need additional patch for rpartition and rsplit on string, unicode and
bytearray objects.
--
stage: patch review - needs patch
___
Python tracker rep...@bugs.python.org
New submission from flox la...@yahoo.fr:
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
flox la...@yahoo.fr added the comment:
(removed comment which should not be copied)
--
Added file: http://bugs.python.org/file15507/fastsearch_rfind.patch
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue7462
Changes by flox la...@yahoo.fr:
Removed file: http://bugs.python.org/file15505/fastsearch_rfind.patch
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue7462
___
37 matches
Mail list logo
