Skip to content

Commit df25f25

Browse files
eendebakptclaude
andcommitted
pythongh-158451: Speed up the pre-pass of str.join()
Compute the maximum character and whether memcpy() can be used from the OR of the item kinds and the AND of their ASCII flags after the pre-pass, instead of per item. Count one separator per item and subtract the extra one after the loop. Add tests for separators and items of mixed kinds. Co-Authored-By: Claude Fable 5.1 <[email protected]>
1 parent e19dc47 commit df25f25

2 files changed

Lines changed: 38 additions & 18 deletions

File tree

‎Lib/test/test_str.py‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -566,6 +566,18 @@ def __str__(self): return self.sval
566566
self.checkequalnofix('a b c d', ' ', 'join', ['a', 'b', 'c', 'd'])
567567
self.checkequalnofix('abcd', '', 'join', ('a', 'b', 'c', 'd'))
568568
self.checkequalnofix('w x y z', ' ', 'join', string_tests.Sequence('wxyz'))
569+
# mixed kinds of the separator and the items
570+
self.checkequalnofix('a\xe9b', '\xe9', 'join', ['a', 'b'])
571+
self.checkequalnofix('a\u20acb', '\u20ac', 'join', ['a', 'b'])
572+
self.checkequalnofix('a\xe9', '', 'join', ['a', '\xe9'])
573+
self.checkequalnofix('\u20ac\xe9', '', 'join', ['\u20ac', '\xe9'])
574+
self.checkequalnofix('\xe9-\u20ac-\U0001f600', '-', 'join',
575+
['\xe9', '\u20ac', '\U0001f600'])
576+
self.checkequalnofix('\U0001f600-a', '-', 'join', ['\U0001f600', 'a'])
577+
# a single item which is a str subclass is copied
578+
class S(str): pass
579+
for s in 'a', '\xe9', '\u20ac', '\U0001f600':
580+
self.checkequalnofix(s, '-', 'join', [S(s)])
569581
self.checkraises(TypeError, ' ', 'join', ['1', '2', MyWrapper('foo')])
570582
self.checkraises(TypeError, ' ', 'join', ['1', '2', '3', bytes()])
571583
self.checkraises(TypeError, ' ', 'join', [1, 2, 3])

‎Objects/unicodeobject.c‎

Lines changed: 26 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -10457,10 +10457,10 @@ _PyUnicode_JoinArray(PyObject *separator, PyObject *const *items, Py_ssize_t seq
1045710457
PyObject *item;
1045810458
Py_ssize_t sz, i, res_offset;
1045910459
Py_UCS4 maxchar;
10460-
Py_UCS4 item_maxchar;
10460+
/* kinds is the bitwise OR of the PyUnicode_KIND() values (1, 2, 4). */
10461+
unsigned int kinds = 0, all_ascii = 1;
1046110462
int use_memcpy;
1046210463
unsigned char *res_data = NULL, *sep_data = NULL;
10463-
PyObject *last_obj;
1046410464
int kind = 0;
1046510465

1046610466
/* If empty sequence, return u"". */
@@ -10469,14 +10469,12 @@ _PyUnicode_JoinArray(PyObject *separator, PyObject *const *items, Py_ssize_t seq
1046910469
}
1047010470

1047110471
/* If singleton sequence with an exact Unicode, return that. */
10472-
last_obj = NULL;
1047310472
if (seqlen == 1) {
1047410473
if (PyUnicode_CheckExact(items[0])) {
1047510474
res = items[0];
1047610475
return Py_NewRef(res);
1047710476
}
1047810477
seplen = 0;
10479-
maxchar = 0;
1048010478
}
1048110479
else {
1048210480
/* Set up sep and seplen */
@@ -10486,7 +10484,6 @@ _PyUnicode_JoinArray(PyObject *separator, PyObject *const *items, Py_ssize_t seq
1048610484
if (!sep)
1048710485
goto onError;
1048810486
seplen = 1;
10489-
maxchar = 32;
1049010487
}
1049110488
else {
1049210489
if (!PyUnicode_Check(separator)) {
@@ -10498,12 +10495,12 @@ _PyUnicode_JoinArray(PyObject *separator, PyObject *const *items, Py_ssize_t seq
1049810495
}
1049910496
sep = separator;
1050010497
seplen = PyUnicode_GET_LENGTH(separator);
10501-
maxchar = PyUnicode_MAX_CHAR_VALUE(separator);
1050210498
/* inc refcount to keep this code path symmetric with the
1050310499
above case of a blank separator */
1050410500
Py_INCREF(sep);
1050510501
}
10506-
last_obj = sep;
10502+
kinds = PyUnicode_KIND(sep);
10503+
all_ascii = PyUnicode_IS_ASCII(sep);
1050710504
}
1050810505

1050910506
/* There are at least two things to join, or else we have a subclass
@@ -10527,23 +10524,34 @@ _PyUnicode_JoinArray(PyObject *separator, PyObject *const *items, Py_ssize_t seq
1052710524
i, Py_TYPE(item)->tp_name);
1052810525
goto onError;
1052910526
}
10530-
add_sz = PyUnicode_GET_LENGTH(item);
10531-
item_maxchar = PyUnicode_MAX_CHAR_VALUE(item);
10532-
maxchar = Py_MAX(maxchar, item_maxchar);
10533-
if (i != 0) {
10534-
add_sz += seplen;
10535-
}
10527+
/* Count one separator per item; the extra one is removed below. */
10528+
add_sz = (size_t)PyUnicode_GET_LENGTH(item) + (size_t)seplen;
10529+
kinds |= PyUnicode_KIND(item);
10530+
all_ascii &= PyUnicode_IS_ASCII(item);
1053610531
if (add_sz > (size_t)(PY_SSIZE_T_MAX - sz)) {
1053710532
PyErr_SetString(PyExc_OverflowError,
1053810533
"join() result is too long for a Python string");
1053910534
goto onError;
1054010535
}
1054110536
sz += add_sz;
10542-
if (use_memcpy && last_obj != NULL) {
10543-
if (PyUnicode_KIND(last_obj) != PyUnicode_KIND(item))
10544-
use_memcpy = 0;
10545-
}
10546-
last_obj = item;
10537+
}
10538+
sz -= seplen;
10539+
/* memcpy() can be used if the separator and all items have the same
10540+
kind: the result then has that kind too. */
10541+
if (kinds & (kinds - 1)) {
10542+
use_memcpy = 0;
10543+
}
10544+
if (all_ascii) {
10545+
maxchar = 0x7f;
10546+
}
10547+
else if (kinds & PyUnicode_4BYTE_KIND) {
10548+
maxchar = MAX_UNICODE;
10549+
}
10550+
else if (kinds & PyUnicode_2BYTE_KIND) {
10551+
maxchar = 0xffff;
10552+
}
10553+
else {
10554+
maxchar = 0xff;
1054710555
}
1054810556

1054910557
res = PyUnicode_New(sz, maxchar);

0 commit comments

Comments
 (0)