Mercurial > cpython-lru_cache-weakref

annotate Objects/stringlib/replace.h @ 83312:d396e0716bf4

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Issue #16061: Speed up str.replace() for replacing 1-character strings.
author Serhiy Storchaka <storchaka@gmail.com>
date Sat, 13 Apr 2013 22:45:04 +0300
parents
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
83312
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
1 /* stringlib: replace implementation */
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
2
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
3 #ifndef STRINGLIB_FASTSEARCH_H
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
4 #error must include "stringlib/fastsearch.h" before including this module
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
5 #endif
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
6
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
7 Py_LOCAL_INLINE(void)
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
8 STRINGLIB(replace_1char_inplace)(STRINGLIB_CHAR* s, STRINGLIB_CHAR* end,
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
9 Py_UCS4 u1, Py_UCS4 u2, Py_ssize_t maxcount)
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
10 {
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
11 *s = u2;
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
12 while (--maxcount && ++s != end) {
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
13 /* Find the next character to be replaced.
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
14
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
15 If it occurs often, it is faster to scan for it using an inline
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
16 loop. If it occurs seldom, it is faster to scan for it using a
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
17 function call; the overhead of the function call is amortized
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
18 across the many characters that call covers. We start with an
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
19 inline loop and use a heuristic to determine whether to fall back
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
20 to a function call. */
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
21 if (*s != u1) {
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
22 int attempts = 10;
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
23 /* search u1 in a dummy loop */
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
24 while (1) {
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
25 if (++s == end)
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
26 return;
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
27 if (*s == u1)
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
28 break;
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
29 if (!--attempts) {
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
30 /* if u1 was not found for attempts iterations,
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
31 use FASTSEARCH() or memchr() */
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
32 #if STRINGLIB_SIZEOF_CHAR == 1
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
33 s++;
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
34 s = memchr(s, u1, end - s);
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
35 if (s == NULL)
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
36 return;
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
37 #else
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
38 Py_ssize_t i;
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
39 STRINGLIB_CHAR ch1 = (STRINGLIB_CHAR) u1;
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
40 s++;
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
41 i = FASTSEARCH(s, end - s, &ch1, 1, 0, FAST_SEARCH);
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
42 if (i < 0)
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
43 return;
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
44 s += i;
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
45 #endif
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
46 /* restart the dummy loop */
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
47 break;
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
48 }
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
49 }
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
50 }
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
51 *s = u2;
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
52 }
d396e0716bf4 Issue #16061: Speed up str.replace() for replacing 1-character strings.
Serhiy Storchaka <storchaka@gmail.com>
parents:
diff changeset
53 }