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

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
Also perform an unalgined load at the end
  • Loading branch information
@rhpvorderman
rhpvorderman committed Jun 14, 2024
commit 0258ae0b47b5b0efa9d44f435bd3475e09a9763a
16 changes: 12 additions & 4 deletions Objects/stringlib/find_max_char.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -23,7 +23,7 @@ STRINGLIB(find_max_char)(const STRINGLIB_CHAR *begin, const STRINGLIB_CHAR *end)
const unsigned char *restrict p = (const unsigned char *) begin;
const unsigned char *_end = (const unsigned char *)end;
const unsigned char *size_t_end = _end - SIZEOF_SIZE_T;
const unsigned char *unrolled_end = _end - 4 * SIZEOF_SIZE_T;
const unsigned char *unrolled_end = _end - (4 * SIZEOF_SIZE_T - 1);
while (p < unrolled_end) {

@vstinner vstinner Sep 10, 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 prefer to start processing bytes until we reach an address aligned of SIZEOF_SIZE_T, and then use size_t* pointers instead of memcpy().

@rhpvorderman rhpvorderman Sep 11, 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.

Ok, good to know thanks. I will close another PR that simplifies the code by using this technique to allow unaligned loads:
#123895

/* Test chunks of 32 as more granularity limits compiler optimization */

@vstinner vstinner Jun 17, 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.

32 what? the number of bytes depend on size_t size in bytes.

@rhpvorderman rhpvorderman Jun 17, 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.

Whoops, will write a better comment. This is a "programmer talking to self" one.

const size_t *restrict _p = (const size_t *)p;
Expand All @@ -50,9 +50,17 @@ STRINGLIB(find_max_char)(const STRINGLIB_CHAR *begin, const STRINGLIB_CHAR *end)
accumulator |= value;
p += SIZEOF_SIZE_T;
}
while (p < end) {
accumulator |= *p;
p += 1;
if (size_t_end >= begin) {
/* Do unaligned size_t load rather than loading bytes individually. */
size_t value;
memcpy(&value, size_t_end, SIZEOF_SIZE_T);
accumulator |= value;
} else {
/* Fallback for smaller than size_t strings. */
while (p < end) {
accumulator |= *p;
p += 1;
}
}
if (accumulator & UCS1_ASCII_CHAR_MASK) {
return 255;
Expand Down