[issue16061] performance regression in string replace for 3.3
Roundup Robot added the comment: New changeset d396e0716bf4 by Serhiy Storchaka in branch 'default': Issue #16061: Speed up str.replace() for replacing 1-character strings. http://hg.python.org/cpython/rev/d396e0716bf4 -- nosy: +python-dev ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16061 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16061] performance regression in string replace for 3.3
Serhiy Storchaka added the comment: Thanks to Ezio Melotti and Daniel Shahaf for their great help in correcting my clumsy wording. -- resolution: - fixed stage: patch review - committed/rejected status: open - closed ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16061 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16061] performance regression in string replace for 3.3
Serhiy Storchaka added the comment: Here is an updated patch. Some comments added (I will be grateful for help in the improvement of these comments), an implementation moved to stringlib (a new file Objects/stringlib/replace.h added). unicode_2.patch optimizes only too special case and I consider this is not worth the effort. str_replace_1char*.patch cover a wider area and designed to be faster than 3.2 and 3.3 in most cases and not to be significant slower in corner cases. -- Added file: http://bugs.python.org/file29721/str_replace_1char_2.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16061 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16061] performance regression in string replace for 3.3
STINNER Victor added the comment: str_replace_1char_2.patch looks good to me. Just one nit: please add a reference to this issue in the comment (in replace.h). -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16061 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16061] performance regression in string replace for 3.3
Terry J. Reedy added the comment: My experiments last September, before this was filed, showed that str.find (index) had most of the relative slowdown of str.replace. I assumed at that time that .replace used .find or .index to find substrings to replace, so that the fix for .replace would include speeding up .find/index. Looking at the patches, I see that I was wrong; I guess because .replace copies as it goes. I will open a separate issue sometime unless .find gets fixed here. For both .find and .replace, the regression was worse on Windows than on linux, so the patches should be tested on Windows also. If I can get vc++ express 2008 installed and working on my current substitute machine. I will give them a try. -- nosy: +terry.reedy ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16061 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16061] performance regression in string replace for 3.3
STINNER Victor added the comment: How can we move this issu forward? I still prefer unicode_2.patch over str_replace_1char.patch because the code is simpler and so easier to maintain. str_replace_1char.patch has a bug: replace_1char() does not use pos for the latin1 path. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16061 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16061] performance regression in string replace for 3.3
Changes by Jesús Cea Avión j...@jcea.es: -- nosy: +jcea ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16061 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16061] performance regression in string replace for 3.3
Serhiy Storchaka added the comment: str_replace_1char.patch: why not implementing replace_1char_inplace() in stringlib, with one version per character type (UCS1, UCS2, UCS4)? Because there are no benefits to do it. All three versions (UCS1, UCS2, and UCS4) have no any common code. The best implementation used for every kind of strings. For UCS1 it uses fast memchr() (findchar() has some overhead here), for UCS2 it uses findchar(), and for UCS4 it uses a dumb loop, because findchar() will be too ineffective here. I prefer unicode_2.patch algorithm because it's simpler: only one loop (vs two loops for str_replace_1char.patch, with a threshold of 10 different characters). Yes, UCS1-implementation in str_replace_1char.patch is more complicated, but it is faster for more input strings. memchr() is more effective than a simple loop when the replaceable characters are rare. But when they meet often, a simple cycle is more efficient. The attempts counter determines how many characters will be checked before using memchr(). This speeds up the replacement in strings with frequent replacements, but a little slow down the replacement in strings with rare replacements. 10 is a compromise. str_replace_1char.patch speed up not only case when *each* character replaced, but when 1/2, 1/3, 1/5,... characters replaced. Why do you changed your algorithm? Is str_replace_1char.patch algorithm more efficient than unicode_2.patch algorithm? Is the speedup really interesting? You can run benchmarks and compare results. str_replace_1char.patch provides not the best performance, but most stable results for wide sort of strings, and has no regressions comparing with 3.2. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16061 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16061] performance regression in string replace for 3.3
Serhiy Storchaka added the comment: I going speed up other cases for replace(), but for now I have only this patch. Is it good? Should I apply it to 3.3 as there is a 3.3 regression? -- keywords: +3.3regression ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16061 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16061] performance regression in string replace for 3.3
Benjamin Peterson added the comment: As __ap__ says, it would be nice to have a comment. -- nosy: +benjamin.peterson ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16061 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16061] performance regression in string replace for 3.3
Antoine Pitrou added the comment: 64-bit linux results: 3.2 3.3 patch 133 (-28%) 1343 (-93%) 96 1 'a' 'b' 'c' 414 (-9%)704 (-47%) 3752 'a' 'b' 'c' 319 (-8%)491 (-40%) 2933 'a' 'b' 'c' 253 (-7%)384 (-39%) 2354 'a' 'b' 'c' 216 (-8%)320 (-38%) 1995 'a' 'b' 'c' 192 (-9%)278 (-37%) 1756 'a' 'b' 'c' 175 (-10%) 247 (-36%) 1577 'a' 'b' 'c' 162 (-11%) 223 (-35%) 1448 'a' 'b' 'c' 153 (-14%) 204 (-35%) 1329 'a' 'b' 'c' 145 (-15%) 188 (-35%) 12310 'a' 'b' 'c' 108 (-36%) 112 (-38%) 69 20 'a' 'b' 'c' 86 (-59%)53 (-34%)35 50 'a' 'b' 'c' 78 (-71%)31 (-26%)23 100 'a' 'b' 'c' 73 (-84%)12 (+0%) 12 1000 'a' 'b' 'c' 81 (-88%)10 (+0%) 10 1 'a' 'b' 'c' 133 (-23%) 1470 (-93%) 1031 '\u010a' '\u010b' '\u010c' 414 (-10%) 799 (-54%) 3712 '\u010a' '\u010b' '\u010c' 319 (-5%)576 (-47%) 3033 '\u010a' '\u010b' '\u010c' 254 (-1%)461 (-46%) 2514 '\u010a' '\u010b' '\u010c' 216 (+2%)391 (-44%) 2205 '\u010a' '\u010b' '\u010c' 193 (+4%)341 (-41%) 2006 '\u010a' '\u010b' '\u010c' 175 (+5%)303 (-39%) 1847 '\u010a' '\u010b' '\u010c' 163 (+6%)275 (-37%) 1728 '\u010a' '\u010b' '\u010c' 153 (+6%)252 (-36%) 1629 '\u010a' '\u010b' '\u010c' 145 (+7%)235 (-34%) 15510 '\u010a' '\u010b' '\u010c' 108 (-1%)133 (-20%) 10720 '\u010a' '\u010b' '\u010c' 86 (-27%)66 (-5%) 63 50 '\u010a' '\u010b' '\u010c' 79 (-44%)44 (+0%) 44 100 '\u010a' '\u010b' '\u010c' 74 (-66%)24 (+4%) 25 1000 '\u010a' '\u010b' '\u010c' 75 (-71%)22 (+0%) 22 1 '\u010a' '\u010b' '\u010c' 1687 (-91%) 1362 (-89%) 1501 '\U0001000a' '\U0001000b' '\U0001000c' 1146 (-58%) 817 (-41%) 4792 '\U0001000a' '\U0001000b' '\U0001000c' 919 (-61%) 627 (-43%) 3583 '\U0001000a' '\U0001000b' '\U0001000c' 802 (-63%) 521 (-44%) 2944 '\U0001000a' '\U0001000b' '\U0001000c' 729 (-64%) 446 (-42%) 2595 '\U0001000a' '\U0001000b' '\U0001000c' 678 (-65%) 394 (-40%) 2376 '\U0001000a' '\U0001000b' '\U0001000c' 643 (-66%) 350 (-37%) 2207 '\U0001000a' '\U0001000b' '\U0001000c' 617 (-66%) 313 (-34%) 2078 '\U0001000a' '\U0001000b' '\U0001000c' 598 (-67%) 283 (-30%) 1989 '\U0001000a' '\U0001000b' '\U0001000c' 581 (-67%) 258 (-27%) 18910 '\U0001000a' '\U0001000b' '\U0001000c' 511 (-71%) 152 (-3%)14820 '\U0001000a' '\U0001000b' '\U0001000c' 472 (-76%) 89 (+28%)11450 '\U0001000a' '\U0001000b' '\U0001000c' 461 (-78%) 68 (+47%)100100 '\U0001000a' '\U0001000b' '\U0001000c' 452 (-81%) 48 (+81%)87 1000 '\U0001000a' '\U0001000b' '\U0001000c' 452 (-81%) 46 (+85%)85 1 '\U0001000a' '\U0001000b' '\U0001000c' -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16061 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16061] performance regression in string replace for 3.3
Antoine Pitrou added the comment: 64-bit windows results: 3.3 patched 925 (-90%) 97 1 'a' 'b' 'c' 881 (-54%) 4052 'a' 'b' 'c' 623 (-51%) 3083 'a' 'b' 'c' 482 (-48%) 2524 'a' 'b' 'c' 396 (-44%) 2235 'a' 'b' 'c' 344 (-40%) 2086 'a' 'b' 'c' 306 (-38%) 1907 'a' 'b' 'c' 276 (-37%) 1738 'a' 'b' 'c' 254 (-36%) 1629 'a' 'b' 'c' 241 (-35%) 15610 'a' 'b' 'c' 158 (-24%) 12020 'a' 'b' 'c' 107 (-12%) 94 50 'a' 'b' 'c' 87 (+7%) 93 100 'a' 'b' 'c' 70 (+3%) 72 1000 'a' 'b' 'c' 63 (+8%) 68 1 'a' 'b' 'c' 1332 (-92%) 1061 '\u010a' '\u010b' '\u010c' 1137 (-60%) 4592 '\u010a' '\u010b' '\u010c' 836 (-58%) 3473 '\u010a' '\u010b' '\u010c' 660 (-56%) 2884 '\u010a' '\u010b' '\u010c' 567 (-55%) 2565 '\u010a' '\u010b' '\u010c' 503 (-51%) 2456 '\u010a' '\u010b' '\u010c' 455 (-47%) 2427 '\u010a' '\u010b' '\u010c' 414 (-44%) 2318 '\u010a' '\u010b' '\u010c' 387 (-41%) 2279 '\u010a' '\u010b' '\u010c' 365 (-35%) 23710 '\u010a' '\u010b' '\u010c' 256 (-21%) 20120 '\u010a' '\u010b' '\u010c' 185 (-9%)16850 '\u010a' '\u010b' '\u010c' 186 (-19%) 150100 '\u010a' '\u010b' '\u010c' 137 (-1%)1361000 '\u010a' '\u010b' '\u010c' 131 (+3%)1351 '\u010a' '\u010b' '\u010c' 1346 (-88%) 1601 '\U0001000a' '\U0001000b' '\U0001000c' 1247 (-62%) 4692 '\U0001000a' '\U0001000b' '\U0001000c' 965 (-64%) 3523 '\U0001000a' '\U0001000b' '\U0001000c' 845 (-64%) 3034 '\U0001000a' '\U0001000b' '\U0001000c' 720 (-65%) 2515 '\U0001000a' '\U0001000b' '\U0001000c' 655 (-65%) 2306 '\U0001000a' '\U0001000b' '\U0001000c' 604 (-58%) 2567 '\U0001000a' '\U0001000b' '\U0001000c' 570 (-62%) 2148 '\U0001000a' '\U0001000b' '\U0001000c' 546 (-63%) 2039 '\U0001000a' '\U0001000b' '\U0001000c' 515 (-63%) 19010 '\U0001000a' '\U0001000b' '\U0001000c' 404 (-61%) 15720 '\U0001000a' '\U0001000b' '\U0001000c' 339 (-62%) 13050 '\U0001000a' '\U0001000b' '\U0001000c' 308 (-60%) 122100 '\U0001000a' '\U0001000b' '\U0001000c' 284 (-54%) 1301000 '\U0001000a' '\U0001000b' '\U0001000c' 281 (-60%) 1131 '\U0001000a' '\U0001000b' '\U0001000c' -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16061 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16061] performance regression in string replace for 3.3
Serhiy Storchaka added the comment: As __ap__ says, it would be nice to have a comment. Oh, I thought I had already done this. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16061 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16061] performance regression in string replace for 3.3
STINNER Victor added the comment: str_replace_1char.patch: why not implementing replace_1char_inplace() in stringlib, with one version per character type (UCS1, UCS2, UCS4)? I prefer unicode_2.patch algorithm because it's simpler: only one loop (vs two loops for str_replace_1char.patch, with a threshold of 10 different characters). Why do you changed your algorithm? Is str_replace_1char.patch algorithm more efficient than unicode_2.patch algorithm? Is the speedup really interesting? -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16061 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16061] performance regression in string replace for 3.3
Changes by Serhiy Storchaka storch...@gmail.com: -- assignee: - serhiy.storchaka ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16061 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16061] performance regression in string replace for 3.3
Changes by Antoine Pitrou pit...@free.fr: -- stage: needs patch - patch review ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16061 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16061] performance regression in string replace for 3.3
Serhiy Storchaka added the comment:
After much experimentation, I suggest the new patch.
Benchmark results (time of replacing 1 of n character (ch1 to ch2) in 10-
char string).
Py3.2Py3.3patch n ch1 ch2 fill
231 (-13%) 3025 (-93%) 2001 'a' 'b' 'c'
626 (-18%) 2035 (-75%) 5112 'a' 'b' 'c'
444 (-26%) 957 (-66%) 3275 'a' 'b' 'c'
349 (-30%) 530 (-54%) 24310 'a' 'b' 'c'
306 (-40%) 300 (-38%) 18520 'a' 'b' 'c'
280 (-54%) 169 (-23%) 13050 'a' 'b' 'c'
273 (-62%) 123 (-15%) 105100 'a' 'b' 'c'
265 (-70%) 82 (-4%) 79 1000 'a' 'b' 'c'
230 (+4%)3012 (-92%) 2391 '\u010a' '\u010b' '\u010c'
624 (-17%) 1907 (-73%) 5182 '\u010a' '\u010b' '\u010c'
442 (-16%) 962 (-62%) 3705 '\u010a' '\u010b' '\u010c'
347 (-5%)566 (-42%) 33010 '\u010a' '\u010b' '\u010c'
305 (-10%) 357 (-23%) 27520 '\u010a' '\u010b' '\u010c'
285 (-26%) 241 (-12%) 21250 '\u010a' '\u010b' '\u010c'
280 (-33%) 190 (-2%)187100 '\u010a' '\u010b' '\u010c'
263 (-41%) 170 (-8%)1561000 '\u010a' '\u010b' '\u010c'
3355 (-85%) 3309 (-85%) 4981 '\U0001000a' '\U0001000b' '\U0001000c'
2290 (-65%) 2267 (-65%) 8002 '\U0001000a' '\U0001000b' '\U0001000c'
1598 (-62%) 1279 (-52%) 6125 '\U0001000a' '\U0001000b' '\U0001000c'
1313 (-60%) 950 (-45%) 51910 '\U0001000a' '\U0001000b' '\U0001000c'
1195 (-61%) 824 (-44%) 46420 '\U0001000a' '\U0001000b' '\U0001000c'
1055 (-59%) 640 (-32%) 43450 '\U0001000a' '\U0001000b' '\U0001000c'
982 (-55%) 549 (-20%) 439100 '\U0001000a' '\U0001000b' '\U0001000c'
941 (-56%) 473 (-12%) 4171000 '\U0001000a' '\U0001000b' '\U0001000c'
On other platforms other numbers are possible. Especially I'm interested in
the results on Windows and on 64-bit. For the test I used the script
replacebench2.py, and compared the results with the help of script
https://bitbucket.org/storchaka/cpython-stuff/raw/default/bench/bench-diff.py
.
--
Added file: http://bugs.python.org/file27553/str_replace_1char.patch
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue16061
___diff -r 6fb1fb550319 Objects/unicodeobject.c
--- a/Objects/unicodeobject.c Thu Oct 11 18:59:34 2012 -0700
+++ b/Objects/unicodeobject.c Sat Oct 13 20:19:47 2012 +0300
@@ -9881,6 +9881,80 @@
return 0;
}
+static void
+replace_1char_inplace(PyObject *u, Py_ssize_t pos, Py_UCS4 u1, Py_UCS4 u2,
Py_ssize_t maxcount)
+{
+int kind = PyUnicode_KIND(u);
+void *data = PyUnicode_DATA(u);
+Py_ssize_t len = PyUnicode_GET_LENGTH(u);
+if (kind == PyUnicode_1BYTE_KIND) {
+Py_UCS1 *s = (Py_UCS1 *)data;
+Py_UCS1 *end = s + len;
+s += pos;
+*s = u2;
+while (--maxcount ++s != end) {
+if (*s != u1) {
+int attempts = 10;
+while (1) {
+if (++s == end)
+return;
+if (*s == u1)
+break;
+if (!--attempts) {
+s++;
+s = memchr(s, u1, end - s);
+if (s == NULL)
+return;
+break;
+}
+}
+}
+*s = u2;
+}
+}
+else if (kind == PyUnicode_2BYTE_KIND) {
+Py_UCS2 *s = (Py_UCS2 *)data;
+Py_UCS2 *end = s + len;
+s += pos;
+*s = u2;
+while (--maxcount ++s != end) {
+if (*s != u1) {
+int attempts = 10;
+while (1) {
+if (++s == end)
+return;
+if (*s == u1)
+break;
+if (!--attempts) {
+Py_ssize_t i;
+s++;
+i = findchar(s, PyUnicode_2BYTE_KIND, end - s, u1, 1);
+if (i 0)
+return;
+s += i;
+break;
+}
+}
+}
+*s = u2;
+}
+}
+else {
+Py_UCS4 *s = (Py_UCS4 *)data;
+Py_UCS4 *end = s + len;
+s += pos;
+while (1) {
+*s = u2;
+if (!--maxcount)
+return;
+do {
+if (++s == end)
+return;
+} while (*s != u1);
+}
+}
+}
+
static PyObject *
replace(PyObject *self, PyObject *str1,
PyObject *str2, Py_ssize_t maxcount)
@@ -9897,7 +9971,7 @@
Py_ssize_t len1 = PyUnicode_GET_LENGTH(str1);
Py_ssize_t len2 = PyUnicode_GET_LENGTH(str2);
int mayshrink;
-Py_UCS4 maxchar, maxchar_str2;
+Py_UCS4 maxchar, maxchar_str1, maxchar_str2;
if (maxcount 0)
[issue16061] performance regression in string replace for 3.3
Serhiy Storchaka added the comment:
The patch should be completed to optimize also other Unicode kinds.
I'm working on it.
Here are benchmark scripts which I use. First tests regular strings (replace
every n-th char), second tests random strings (replace 1/n of total randomly
distributed chars).
--
Added file: http://bugs.python.org/file27544/replacebench.py
Added file: http://bugs.python.org/file27545/replacebench2.py
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue16061
___import timeit, gc, sys
size = 10
repeats = 10
numbers = 100
gc.disable()
def bench(a, b, c):
for i in list(range(1, 11)) + [20, 50, 100, 1000, 1]:
string = (c * (i - 1) + a) * (size // i)
string += c * (size - len(string))
gc.collect()
best = min(timeit.Timer(text.replace(a, b),
a=%r; b=%r; text=%r % (a, b, string)
).repeat(repeats, numbers))
print('%.0f\t%d %a %a %a' % (best *1e6 / numbers, i, a, b, c))
sys.stdout.flush()
bench('a', 'b', 'c')
bench('\u010a', '\u010b', '\u010c')
bench('\U0001000a', '\U0001000b', '\U0001000c')
import timeit, gc, random, sys
size = 10
repeats = 5
numbers = 100
gc.disable()
def bench(a, b, c):
for i in list(range(1, 11)) + [20, 50, 100, 1000, 1]:
data = list(a * (size // i) + c * (size - size // i))
random.shuffle(data)
string = ''.join(data)
gc.collect()
best = min(timeit.Timer(text.replace(a, b),
a=%r; b=%r; text=%r % (a, b, string)
).repeat(repeats, numbers))
print('%.0f\t%d %a %a %a' % (best *1e6 / numbers, i, a, b, c))
sys.stdout.flush()
bench('a', 'b', 'c')
bench('\u010a', '\u010b', '\u010c')
bench('\U0001000a', '\U0001000b', '\U0001000c')
___
Python-bugs-list mailing list
Unsubscribe:
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16061] performance regression in string replace for 3.3
Antoine Pitrou added the comment: The performance numbers are very nice, but the patch needs a comment about the optimization, IMO. -- nosy: +pitrou ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16061 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16061] performance regression in string replace for 3.3
Serhiy Storchaka added the comment:
I compared performances of the two methods: dummy loop vs find.
You can hybridize them. First just compare chars and if not match then use
memcmp(). This speed up the case of repeated chars.
--
Added file: http://bugs.python.org/file27526/unicode_2.patch
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue16061
___diff -r 9475fc82768e Objects/unicodeobject.c
--- a/Objects/unicodeobject.c Wed Oct 10 08:36:43 2012 -0700
+++ b/Objects/unicodeobject.c Thu Oct 11 11:30:16 2012 +0300
@@ -9881,6 +9881,64 @@
return 0;
}
+static void
+replace_1char(PyObject *self, Py_ssize_t maxcount, Py_ssize_t pos, char *sbuf,
+ Py_UCS4 u1, Py_UCS4 u2, PyObject *u)
+{
+Py_ssize_t index;
+char *src;
+Py_ssize_t len = PyUnicode_GET_LENGTH(self);
+int skind = PyUnicode_KIND(self);
+int rkind = PyUnicode_KIND(u);
+
+if (skind == 1 rkind == 1) {
+char *sdata = PyUnicode_DATA(self);
+char *udata = PyUnicode_DATA(u);
+char *uend = udata + len;
+
+memcpy(udata, sdata, len);
+
+while (udata uend) {
+if (*udata == u1) {
+*udata = u2;
+if (!--maxcount)
+break;
+udata++;
+continue;
+}
+udata++;
+len = uend - udata;
+if (!len)
+break;
+udata = memchr(udata, u1, len);
+if (udata == NULL)
+break;
+*udata = u2;
+if (!--maxcount)
+break;
+udata++;
+}
+}
+else {
+_PyUnicode_FastCopyCharacters(u, 0, self, 0, len);
+PyUnicode_WRITE(rkind, PyUnicode_DATA(u), pos, u2);
+
+index = 0;
+src = sbuf;
+while (--maxcount)
+{
+pos++;
+src += pos * skind;
+len -= pos;
+index += pos;
+pos = findchar(src, skind, len, u1, 1);
+if (pos 0)
+break;
+PyUnicode_WRITE(rkind, PyUnicode_DATA(u), index + pos, u2);
+}
+}
+}
+
static PyObject *
replace(PyObject *self, PyObject *str1,
PyObject *str2, Py_ssize_t maxcount)
@@ -9924,9 +9982,7 @@
if (len1 == 1) {
/* replace characters */
Py_UCS4 u1, u2;
-int rkind;
-Py_ssize_t index, pos;
-char *src;
+Py_ssize_t pos;
u1 = PyUnicode_READ_CHAR(str1, 0);
pos = findchar(sbuf, PyUnicode_KIND(self), slen, u1, 1);
@@ -9936,23 +9992,8 @@
u = PyUnicode_New(slen, maxchar);
if (!u)
goto error;
-_PyUnicode_FastCopyCharacters(u, 0, self, 0, slen);
-rkind = PyUnicode_KIND(u);
-
-PyUnicode_WRITE(rkind, PyUnicode_DATA(u), pos, u2);
-index = 0;
-src = sbuf;
-while (--maxcount)
-{
-pos++;
-src += pos * PyUnicode_KIND(self);
-slen -= pos;
-index += pos;
-pos = findchar(src, PyUnicode_KIND(self), slen, u1, 1);
-if (pos 0)
-break;
-PyUnicode_WRITE(rkind, PyUnicode_DATA(u), index + pos, u2);
-}
+
+replace_1char(self, maxcount, pos, sbuf, u1, u2, u);
}
else {
int rkind = skind;
___
Python-bugs-list mailing list
Unsubscribe:
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16061] performance regression in string replace for 3.3
STINNER Victor added the comment: You can hybridize them. First just compare chars and if not match then use memcmp(). This speed up the case of repeated chars. Oh, you're patch is simple and it's amazing fast! I compare unicode with Python 2.7, 3.2, 3.4 and 3.4 patched, and bytes with 2.7. Using your patch, Python 3.4 is the fastest implemented in most cases. Common platform: CPU model: Intel(R) Core(TM) i5 CPU 661 @ 3.33GHz Bits: int=32, long=32, long long=64, pointer=32 Platform: Linux-3.2.0-31-generic-pae-i686-with-debian-wheezy-sid Platform of campaign 2.7-bytes: Python unicode implementation: UTF-16 Python version: 2.7.3+ (2.7:19d37c8d1882+, Oct 9 2012, 14:37:36) [GCC 4.6.3] CFLAGS: -fno-strict-aliasing -g -O2 -DNDEBUG -g -fwrapv -O3 -Wall -Wstrict-prototypes SCM: hg revision=ad51ed93377c tag=tip branch=default date=2012-10-11 00:11 -0700 Date: 2012-10-11 14:41:49 Platform of campaign 2.7-unicode: Python unicode implementation: UTF-16 Python version: 2.7.3+ (2.7:19d37c8d1882+, Oct 9 2012, 14:37:36) [GCC 4.6.3] CFLAGS: -fno-strict-aliasing -g -O2 -DNDEBUG -g -fwrapv -O3 -Wall -Wstrict-prototypes SCM: hg revision=ad51ed93377c tag=tip branch=default date=2012-10-11 00:11 -0700 Date: 2012-10-11 14:42:55 Platform of campaign 3.2-wide: Python unicode implementation: UCS-4 Python version: 3.2.3+ (3.2:f7615ee43318, Sep 27 2012, 15:00:15) [GCC 4.6.3] CFLAGS: -DNDEBUG -g -fwrapv -O3 -Wall -Wstrict-prototypes SCM: hg revision=ad51ed93377c tag=tip branch=default date=2012-10-11 00:11 -0700 Date: 2012-10-11 14:41:30 Platform of campaign 3.4: Python unicode implementation: PEP 393 Python version: 3.4.0a0 (default:ad51ed93377c, Oct 11 2012, 14:40:51) [GCC 4.6.3] CFLAGS: -Wno-unused-result -DNDEBUG -g -fwrapv -O3 -Wall -Wstrict-prototypes SCM: hg revision=ad51ed93377c tag=tip branch=default date=2012-10-11 00:11 -0700 Date: 2012-10-11 14:40:52 Platform of campaign 3.4-patch: Date: 2012-10-11 14:40:25 Python version: 3.4.0a0 (default:ad51ed93377c+, Oct 11 2012, 14:33:04) [GCC 4.6.3] CFLAGS: -Wno-unused-result -DNDEBUG -g -fwrapv -O3 -Wall -Wstrict-prototypes SCM: hg revision=ad51ed93377c+ tag=tip branch=default date=2012-10-11 00:11 -0700 Python unicode implementation: PEP 393 +-+-+-+-+ Tests | 2.7-bytes | 2.7-unicode | 3.2-wide | 3.4 | 3.4-patch +-+-+-+-+ all | 7.83 ms (+552%) | 2.05 ms (+71%) | 3.45 ms (+188%) | 15 ms (+1152%) | 1.2 ms (*) replace 50% | 4.14 ms (+135%) | 1.76 ms (*) | 3.17 ms (+81%) | 7.76 ms (+342%) | 4.18 ms (+138%) replace 10% | 1.21 ms (*) | 1.52 ms (+26%) | 3.01 ms (+150%) | 2.01 ms (+67%) | 1.23 ms replace 1% | 490 us | 1.55 ms (+217%) | 2.94 ms (+501%) | 589 us (+20%) | 489 us (*) replace 2 chars | 398 us | 1.47 ms (+271%) | 2.89 ms (+632%) | 398 us | 395 us (*) +-+-+-+-+ Total | 14.1 ms (+88%) | 8.34 ms (+11%) | 15.5 ms (+106%) | 25.8 ms (+244%) | 7.49 ms (*) +-+-+-+-+ ** Compare 3.2, 3.4 and 3.4 patched: +-+-+--- Tests | 3.2-wide | 3.4 | 3.4-patch +-+-+--- all | 3.45 ms (*) | 15 ms (+335%) | 1.2 ms (-65%) replace 50% | 3.17 ms (*) | 7.76 ms (+145%) | 4.18 ms (+32%) replace 10% | 3.01 ms (*) | 2.01 ms (-33%) | 1.23 ms (-59%) replace 1% | 2.94 ms (*) | 589 us (-80%) | 489 us (-83%) replace 2 chars | 2.89 ms (*) | 398 us (-86%) | 395 us (-86%) +-+-+--- Total | 15.5 ms (*) | 25.8 ms (+67%) | 7.49 ms (-52%) +-+-+--- The patch should be completed to optimize also other Unicode kinds. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16061 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16061] performance regression in string replace for 3.3
STINNER Victor added the comment: The code is now using the heavily optimized findchar() function. I compared performances of the two methods: dummy loop vs find. Results with a string of 100,000 characters: * Replace 100% (rewrite all characters): find is 12.5x slower than a loop * Replace 50%: find is 3.3x slower * Replace only 2 characters (0.001%): find is 10.4x faster In practice, I bet that the most common case is to replace only a few characters. Replace all characters is a rare usecase. Use attached unicode.patch on Python 3.4 with the following commands to reproduce my benchmark: python -m timeit -s a='a'; b='b'; text=a*10 text.replace(a, b) python -m timeit -s a='a'; b='b'; text=(a+' ')*(10//2) text.replace(a, b) python -m timeit -s a='a'; b='b'; text=a+' '*10+a text.replace(a, b) -- An option is to use the find method, and then switch to the dummy loop method if there are too much characters to replace. I don't know if it's necessary to develop such complex algorithm. It would be better to have a benchmark extracted from a real world application like a template engine. -- keywords: +patch Added file: http://bugs.python.org/file27521/unicode.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16061 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16061] performance regression in string replace for 3.3
Changes by STINNER Victor victor.stin...@gmail.com: -- nosy: +loewis ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16061 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16061] performance regression in string replace for 3.3
Changes by Kushal Das kushal...@gmail.com: -- nosy: +kushaldas ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16061 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16061] performance regression in string replace for 3.3
Thomas Lee added the comment:
My results aren't quite as dramatic as yours, but there does appear to be a
regression:
$ ./python -V
Python 2.7.3+
$ ./python -m timeit -s s = 'b'*1000 s.replace('b', 'a')
10 loops, best of 3: 16.5 usec per loop
$ ./python -V
Python 3.3.0rc3+
$ ./python -m timeit -s s = 'b'*1000 s.replace('b', 'a')
1 loops, best of 3: 22.7 usec per loop
--
nosy: +thomaslee
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue16061
___
___
Python-bugs-list mailing list
Unsubscribe:
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16061] performance regression in string replace for 3.3
STINNER Victor added the comment:
Python 3.3 is 2x faster than Python 3.2 to replace a character with
another if the string only contains the character 3 times. This is not
acceptable, Python 3.3 must be as slow as Python 3.2!
$ python3.2 -m timeit ch='é'; sp=' '*1000; s = ch+sp+ch+sp+ch;
after='à'; s.replace(ch, after)
10 loops, best of 3: 3.62 usec per loop
$ python3.3 -m timeit ch='é'; sp=' '*1000; s = ch+sp+ch+sp+ch;
after='à'; s.replace(ch, after)
100 loops, best of 3: 1.36 usec per loop
$ python3.2 -m timeit ch='€'; sp=' '*1000; s = ch+sp+ch+sp+ch;
after='Ł'; s.replace(ch, after)
10 loops, best of 3: 3.15 usec per loop
$ python3.2 -m timeit ch='€'; sp=' '*1000; s = ch+sp+ch+sp+ch;
after='Ł'; s.replace(ch, after)
100 loops, best of 3: 1.91 usec per loop
More seriously, I changed the algorithm of str.replace(before, after)
when before and after are only one character: changeset c802bfc8acfc.
The code is now using the heavily optimized findchar() function.
PyUnicode_READ() is slow and should be avoided when possible:
PyUnicode_READ() macro is expanded to 2 if, whereas findchar() uses
directly pointer of the right type (Py_UCS1*, Py_UCS2* or Py_UCS4*).
In Python 3.2, the code looks like:
for (i = 0; i u-length; i++) {
if (u-str[i] == u1) {
if (--maxcount 0)
break;
u-str[i] = u2;
}
}
In Python 3.3, the code looks like:
pos = findchar(sbuf, PyUnicode_KIND(self), slen, u1, 1);
if (pos 0)
goto nothing;
...
while (--maxcount)
{
pos++;
src += pos * PyUnicode_KIND(self);
slen -= pos;
index += pos;
pos = findchar(src, PyUnicode_KIND(self), slen, u1, 1);
if (pos 0)
break;
PyUnicode_WRITE(rkind, PyUnicode_DATA(u), index + pos, u2);
}
--
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue16061
___
___
Python-bugs-list mailing list
Unsubscribe:
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16061] performance regression in string replace for 3.3
New submission from Mark Lawrence:
Quoting Steven D'Aprano on c.l.p.
But add a call to replace, and things are very different:
[steve@ando ~]$ python2.7 -m timeit -s s = 'b'*1000 s.replace('b', 'a')
10 loops, best of 3: 9.3 usec per loop
[steve@ando ~]$ python3.2 -m timeit -s s = 'b'*1000 s.replace('b', 'a')
10 loops, best of 3: 5.43 usec per loop
[steve@ando ~]$ python3.3 -m timeit -s s = 'b'*1000 s.replace('b', 'a')
10 loops, best of 3: 18.3 usec per loop
Three times slower, even for pure-ASCII strings. I get comparable results for
Unicode. Notice how slow Python 2.7 is:
[steve@ando ~]$ python2.7 -m timeit -s s = u'你'*1000 s.replace(u'你', u'a')
1 loops, best of 3: 65.6 usec per loop
[steve@ando ~]$ python3.2 -m timeit -s s = '你'*1000 s.replace('你', 'a')
10 loops, best of 3: 2.79 usec per loop
[steve@ando ~]$ python3.3 -m timeit -s s = '你'*1000 s.replace('你', 'a')
1 loops, best of 3: 23.7 usec per loop
Even with the performance regression, it is still over twice as fast as
Python 2.7.
Nevertheless, I think there is something here. The consequences are nowhere
near as dramatic as jmf claims, but it does seem that replace() has taken a
serious performance hit. Perhaps it is unavoidable, but perhaps not.
If anyone else can confirm similar results, I think this should be raised as a
performance regression.
Quoting Serhiy Storchaka in response.
Yes, I confirm, it's a performance regression. It should be avoidable.
Almost any PEP393 performance regression can be avoided. At least for
such corner case. Just no one has yet optimized this case.
--
messages: 171378
nosy: BreamoreBoy
priority: normal
severity: normal
status: open
title: performance regression in string replace for 3.3
type: performance
versions: Python 3.3
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue16061
___
___
Python-bugs-list mailing list
Unsubscribe:
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16061] performance regression in string replace for 3.3
Changes by Serhiy Storchaka storch...@gmail.com: -- components: +Interpreter Core nosy: +storchaka ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16061 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue16061] performance regression in string replace for 3.3
Changes by Ezio Melotti ezio.melo...@gmail.com: -- components: +Unicode nosy: +ezio.melotti, haypo stage: - needs patch versions: +Python 3.4 -Python 3.3 ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue16061 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
