Skip to content

Commit 7108bdf

Browse files
goldsteinngoldsteinn
authored
gh-93033: Use wmemchr in stringlib (GH-93034)
Generally comparable perf for the "good" case where memchr doesn't return any collisions (false matches on lower byte) but clearly faster with collisions.
1 parent f7fabae commit 7108bdf

11 files changed

+39
-14
lines changed

‎Misc/NEWS.d/next/Library/2022-05-22-23-46-18.gh-issue-93033.wZfiL-.rst

+1
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
Search in some strings (platform dependent i.e [U+0xFFFF, U+0x0100] on Windows or [U+0xFFFFFFFF, U+0x00010000] on Linux 64-bit) are now up to 10 times faster.

‎Objects/bytearrayobject.c

+1
Original file line numberDiff line numberDiff line change
@@ -1096,6 +1096,7 @@ bytearray_dealloc(PyByteArrayObject *self)
10961096
#define STRINGLIB_ISSPACE Py_ISSPACE
10971097
#define STRINGLIB_ISLINEBREAK(x) ((x == '\n') || (x == '\r'))
10981098
#define STRINGLIB_CHECK_EXACT PyByteArray_CheckExact
1099+
#define STRINGLIB_FAST_MEMCHR memchr
10991100
#define STRINGLIB_MUTABLE 1
11001101

11011102
#include "stringlib/fastsearch.h"

‎Objects/bytes_methods.c

+1
Original file line numberDiff line numberDiff line change
@@ -431,6 +431,7 @@ _Py_bytes_maketrans(Py_buffer *frm, Py_buffer *to)
431431
#define STRINGLIB(F) stringlib_##F
432432
#define STRINGLIB_CHAR char
433433
#define STRINGLIB_SIZEOF_CHAR 1
434+
#define STRINGLIB_FAST_MEMCHR memchr
434435

435436
#include "stringlib/fastsearch.h"
436437
#include "stringlib/count.h"

‎Objects/stringlib/asciilib.h

+1
Original file line numberDiff line numberDiff line change
@@ -21,6 +21,7 @@
2121
#define STRINGLIB_CHECK PyUnicode_Check
2222
#define STRINGLIB_CHECK_EXACT PyUnicode_CheckExact
2323
#define STRINGLIB_MUTABLE 0
24+
#define STRINGLIB_FAST_MEMCHR memchr
2425

2526
#define STRINGLIB_TOSTR PyObject_Str
2627
#define STRINGLIB_TOASCII PyObject_ASCII

‎Objects/stringlib/fastsearch.h

+22-12
Original file line numberDiff line numberDiff line change
@@ -39,7 +39,7 @@
3939
#define STRINGLIB_BLOOM(mask, ch) \
4040
((mask & (1UL << ((ch) & (STRINGLIB_BLOOM_WIDTH -1)))))
4141

42-
#if STRINGLIB_SIZEOF_CHAR == 1
42+
#ifdef STRINGLIB_FAST_MEMCHR
4343
# define MEMCHR_CUT_OFF 15
4444
#else
4545
# define MEMCHR_CUT_OFF 40
@@ -53,8 +53,8 @@ STRINGLIB(find_char)(const STRINGLIB_CHAR* s, Py_ssize_t n, STRINGLIB_CHAR ch)
5353
p = s;
5454
e = s + n;
5555
if (n > MEMCHR_CUT_OFF) {
56-
#if STRINGLIB_SIZEOF_CHAR == 1
57-
p = memchr(s, ch, n);
56+
#ifdef STRINGLIB_FAST_MEMCHR
57+
p = STRINGLIB_FAST_MEMCHR(s, ch, n);
5858
if (p != NULL)
5959
return (p - s);
6060
return -1;
@@ -102,16 +102,26 @@ STRINGLIB(find_char)(const STRINGLIB_CHAR* s, Py_ssize_t n, STRINGLIB_CHAR ch)
102102
return -1;
103103
}
104104

105+
#undef MEMCHR_CUT_OFF
106+
107+
#if STRINGLIB_SIZEOF_CHAR == 1
108+
# define MEMRCHR_CUT_OFF 15
109+
#else
110+
# define MEMRCHR_CUT_OFF 40
111+
#endif
112+
113+
105114
Py_LOCAL_INLINE(Py_ssize_t)
106115
STRINGLIB(rfind_char)(const STRINGLIB_CHAR* s, Py_ssize_t n, STRINGLIB_CHAR ch)
107116
{
108117
const STRINGLIB_CHAR *p;
109118
#ifdef HAVE_MEMRCHR
110-
/* memrchr() is a GNU extension, available since glibc 2.1.91.
111-
it doesn't seem as optimized as memchr(), but is still quite
112-
faster than our hand-written loop below */
119+
/* memrchr() is a GNU extension, available since glibc 2.1.91. it
120+
doesn't seem as optimized as memchr(), but is still quite
121+
faster than our hand-written loop below. There is no wmemrchr
122+
for 4-byte chars. */
113123

114-
if (n > MEMCHR_CUT_OFF) {
124+
if (n > MEMRCHR_CUT_OFF) {
115125
#if STRINGLIB_SIZEOF_CHAR == 1
116126
p = memrchr(s, ch, n);
117127
if (p != NULL)
@@ -139,19 +149,19 @@ STRINGLIB(rfind_char)(const STRINGLIB_CHAR* s, Py_ssize_t n, STRINGLIB_CHAR ch)
139149
if (*p == ch)
140150
return n;
141151
/* False positive */
142-
if (n1 - n > MEMCHR_CUT_OFF)
152+
if (n1 - n > MEMRCHR_CUT_OFF)
143153
continue;
144-
if (n <= MEMCHR_CUT_OFF)
154+
if (n <= MEMRCHR_CUT_OFF)
145155
break;
146-
s1 = p - MEMCHR_CUT_OFF;
156+
s1 = p - MEMRCHR_CUT_OFF;
147157
while (p > s1) {
148158
p--;
149159
if (*p == ch)
150160
return (p - s);
151161
}
152162
n = p - s;
153163
}
154-
while (n > MEMCHR_CUT_OFF);
164+
while (n > MEMRCHR_CUT_OFF);
155165
}
156166
#endif
157167
}
@@ -165,7 +175,7 @@ STRINGLIB(rfind_char)(const STRINGLIB_CHAR* s, Py_ssize_t n, STRINGLIB_CHAR ch)
165175
return -1;
166176
}
167177

168-
#undef MEMCHR_CUT_OFF
178+
#undef MEMRCHR_CUT_OFF
169179

170180
/* Change to a 1 to see logging comments walk through the algorithm. */
171181
#if 0 && STRINGLIB_SIZEOF_CHAR == 1

‎Objects/stringlib/replace.h

+2-2
Original file line numberDiff line numberDiff line change
@@ -29,9 +29,9 @@ STRINGLIB(replace_1char_inplace)(STRINGLIB_CHAR* s, STRINGLIB_CHAR* end,
2929
if (!--attempts) {
3030
/* if u1 was not found for attempts iterations,
3131
use FASTSEARCH() or memchr() */
32-
#if STRINGLIB_SIZEOF_CHAR == 1
32+
#ifdef STRINGLIB_FAST_MEMCHR
3333
s++;
34-
s = memchr(s, u1, end - s);
34+
s = STRINGLIB_FAST_MEMCHR(s, u1, end - s);
3535
if (s == NULL)
3636
return;
3737
#else

‎Objects/stringlib/stringdefs.h

+1
Original file line numberDiff line numberDiff line change
@@ -24,4 +24,5 @@
2424
#define STRINGLIB_CHECK_EXACT PyBytes_CheckExact
2525
#define STRINGLIB_TOSTR PyObject_Str
2626
#define STRINGLIB_TOASCII PyObject_Repr
27+
#define STRINGLIB_FAST_MEMCHR memchr
2728
#endif /* !STRINGLIB_STRINGDEFS_H */

‎Objects/stringlib/ucs1lib.h

+1
Original file line numberDiff line numberDiff line change
@@ -20,6 +20,7 @@
2020
#define STRINGLIB_NEW _PyUnicode_FromUCS1
2121
#define STRINGLIB_CHECK PyUnicode_Check
2222
#define STRINGLIB_CHECK_EXACT PyUnicode_CheckExact
23+
#define STRINGLIB_FAST_MEMCHR memchr
2324
#define STRINGLIB_MUTABLE 0
2425

2526
#define STRINGLIB_TOSTR PyObject_Str

‎Objects/stringlib/ucs2lib.h

+4
Original file line numberDiff line numberDiff line change
@@ -21,6 +21,10 @@
2121
#define STRINGLIB_CHECK PyUnicode_Check
2222
#define STRINGLIB_CHECK_EXACT PyUnicode_CheckExact
2323
#define STRINGLIB_MUTABLE 0
24+
#if SIZEOF_WCHAR_T == 2
25+
#define STRINGLIB_FAST_MEMCHR(s, c, n) \
26+
(Py_UCS2 *)wmemchr((const wchar_t *)(s), c, n)
27+
#endif
2428

2529
#define STRINGLIB_TOSTR PyObject_Str
2630
#define STRINGLIB_TOASCII PyObject_ASCII

‎Objects/stringlib/ucs4lib.h

+4
Original file line numberDiff line numberDiff line change
@@ -21,6 +21,10 @@
2121
#define STRINGLIB_CHECK PyUnicode_Check
2222
#define STRINGLIB_CHECK_EXACT PyUnicode_CheckExact
2323
#define STRINGLIB_MUTABLE 0
24+
#if SIZEOF_WCHAR_T == 4
25+
#define STRINGLIB_FAST_MEMCHR(s, c, n) \
26+
(Py_UCS4 *)wmemchr((const wchar_t *)(s), c, n)
27+
#endif
2428

2529
#define STRINGLIB_TOSTR PyObject_Str
2630
#define STRINGLIB_TOASCII PyObject_ASCII

‎Objects/stringlib/undef.h

+1
Original file line numberDiff line numberDiff line change
@@ -8,3 +8,4 @@
88
#undef STRINGLIB_NEW
99
#undef STRINGLIB_IS_UNICODE
1010
#undef STRINGLIB_MUTABLE
11+
#undef STRINGLIB_FAST_MEMCHR

0 commit comments

Comments
 (0)