Skip to content

gh-120196: Faster ascii_decode and find_max_char implementations #120212

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Closed
rhpvorderman wants to merge 24 commits into from
Closed

gh-120196: Faster ascii_decode and find_max_char implementations #120212

Show file tree
Hide file tree
Changes from 1 commit
Commits
Show all changes
24 commits
Select commit Hold shift + click to select a range
a54bf86
Write an unrolled version of find_max_char
rhpvorderman Jun 5, 2024
71ff457
Unroll 8 characters rather than 4 to improve vectorization in find_ma…
rhpvorderman Jun 7, 2024
98a6449
Bigger chunk ascii decoding
rhpvorderman Jun 7, 2024
10527c6
Fix whitespace issues
rhpvorderman Jun 7, 2024
f0f4139
Fix compiler warnings
rhpvorderman Jun 7, 2024
849a068
Prevent re-read of same value
rhpvorderman Jun 7, 2024
fad19a0
Simplify find_max_char initialization
rhpvorderman Jun 7, 2024
f04bb2c
Add missing increments
rhpvorderman Jun 7, 2024
cd0fc5e
Add blurb
rhpvorderman Jun 7, 2024
8f0fd56
Replace unroll_end with unrolled_end
rhpvorderman Jun 7, 2024
37aee7a
Reword burb
rhpvorderman Jun 11, 2024
a6fc417
Update Objects/stringlib/find_max_char.h
rhpvorderman Jun 11, 2024
104ca62
Merge branch 'main' into MICROOPTIMIZATIONS
rhpvorderman Jun 12, 2024
d465517
Merge branch 'main' into MICROOPTIMIZATIONS
rhpvorderman Jun 14, 2024
1ce308e
Reuse find_max_char for bytes objects
rhpvorderman Jun 14, 2024
48f1e84
Simplify the find_max_char function by loading unaligned
rhpvorderman Jun 14, 2024
21de804
Allow optimized unaligned loads and simplify ascii_decode
rhpvorderman Jun 14, 2024
1ec2113
Add loop for more optimal assembly
rhpvorderman Jun 14, 2024
0258ae0
Also perform an unalgined load at the end
rhpvorderman Jun 14, 2024
ec76b74
Fix compiler warning
rhpvorderman Jun 14, 2024
845eb4e
Revert "Reuse find_max_char for bytes objects"
rhpvorderman Jun 14, 2024
f8cc68d
Merge branch 'main' into MICROOPTIMIZATIONS
rhpvorderman Jun 17, 2024
89ab2c9
Improve comments
rhpvorderman Jun 17, 2024
002b7ec
Merge branch 'main' into MICROOPTIMIZATIONS
rhpvorderman Sep 10, 2024
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Next Next commit
Fix whitespace issues
  • Loading branch information
@rhpvorderman
rhpvorderman committed Jun 7, 2024
commit 10527c647f6b6a2d8642815f0dbcc913d2326e32
4 changes: 2 additions & 2 deletions Objects/stringlib/find_max_char.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -40,7 +40,7 @@ STRINGLIB(find_max_char)(const STRINGLIB_CHAR *begin, const STRINGLIB_CHAR *end)
}

/* On 64-bit platforms with 128-bit vectors (x86-64, arm64) the
compiler can load 4 size_t values into two 16-byte vectors and do a
compiler can load 4 size_t values into two 16-byte vectors and do a
vector bitwise OR. */
const size_t *_p = (const size_t *)p;
while (_p < unrolled_end) {
Expand Down Expand Up @@ -98,7 +98,7 @@ STRINGLIB(find_max_char)(const STRINGLIB_CHAR *begin, const STRINGLIB_CHAR *end)
max_char = MAX_CHAR_ASCII;
mask = MASK_ASCII;
while (p < unrolled_end) {
/* Loading 8 values at once allows platforms that have 16-byte vectors
/* Loading 8 values at once allows platforms that have 16-byte vectors
to do a vector load and vector bitwise OR. */
STRINGLIB_CHAR bits = p[0] | p[1] | p[2] | p[3] | p[4] | p[5] | p[6] | p[7];

@picnixz picnixz Jun 13, 2024

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

and here, you would have some #if arch == ... to choose between 4 or 8 values.

@picnixz picnixz Jun 13, 2024

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I feel that those vector load could be macros, for clarity purposes. It would then be optimized by the compiler but having them as macros might be helpful for future work.

@vstinner vstinner Jun 14, 2024

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I would to not have a macro, the code is good as it is.

if (bits & mask) {
Expand Down
6 changes: 3 additions & 3 deletions Objects/unicodeobject.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -4700,7 +4700,7 @@ static Py_ssize_t
ascii_decode(const char *start, const char *end, Py_UCS1 *dest)
{
const char *p = start;
Py_ssize_t length = end - start;
Py_ssize_t length = end - start;
const char *size_t_end = end - SIZEOF_SIZE_T;
const char *unroll_end = end - (4 * SIZEOF_SIZE_T);
Comment thread
rhpvorderman marked this conversation as resolved.
Outdated

Expand All @@ -4714,7 +4714,7 @@ ascii_decode(const char *start, const char *end, Py_UCS1 *dest)
const char *_p = p;
Py_UCS1 * q = dest;
while (_p <= unroll_end) {
const size_t *restrict __p = (const size_t *)_p;
const size_t *restrict __p = (const size_t *)_p;

@eendebakpt eendebakpt Jun 7, 2024

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Is the restrict keyword and the assignment to value0, ..., value3 required for the compiler? If not, then this code can be written more compact.

@rhpvorderman rhpvorderman Jun 7, 2024

Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

In general I think the compiler can judge from the function that no writes happen in either __p or _q so pointer aliasing is not problematic. But I'd rather make this explicit rather than relying on the compiler to deduce this. MSVC and Clang do this scalarly despite the hint. GCC correctly vectorizes the load store and does not need the hint. I cannot judge all possible compilers out there. I think it is more likely that clang and MSVC will do the correct thing in the future with the hint than without it.

It would only save the restrict keyword as the (size_t *) cast is still needed, as that makes the rest of the code more readable. Are the 8 characters extra width that problematic?

size_t value = __p[0] | __p[1] | __p[2] | __p[3];
if (if value & ASCII_CHAR_MASK) {
break;
Expand Down Expand Up @@ -4751,7 +4751,7 @@ ascii_decode(const char *start, const char *end, Py_UCS1 *dest)
/* Help allocation */
const char *_p = p;
while (_p <= unroll_end) {
const size_t *restrict __p = (const size_t *)_p;
const size_t *restrict __p = (const size_t *)_p;
size_t value = __p[0] | __p[1] | __p[2] | __p[3];
if (if value & ASCII_CHAR_MASK) {
break;
Expand Down