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
Simplify find_max_char initialization
  • Loading branch information
@rhpvorderman
rhpvorderman committed Jun 7, 2024
commit fad19a046fcbf071d39b57c56b81b89ee04355e8
7 changes: 2 additions & 5 deletions Objects/stringlib/find_max_char.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -20,16 +20,13 @@ Py_LOCAL_INLINE(Py_UCS4)
STRINGLIB(find_max_char)(const STRINGLIB_CHAR *begin, const STRINGLIB_CHAR *end)
{
const unsigned char *p = (const unsigned char *) begin;
const unsigned char *_begin = (const unsigned char *)begin;
const unsigned char *aligned_start = (const unsigned char *)(
((intptr_t)_begin + (SIZEOF_SIZE_T - 1)) & ~(SIZEOF_SIZE_T - 1));
const unsigned char *_end = (const unsigned char *)end;
const size_t *aligned_end = (const size_t *)((intptr_t)_end & ~(SIZEOF_SIZE_T - 1));
const size_t *aligned_end = (const size_t *)(_end - SIZEOF_SIZE_T);

@eendebakpt eendebakpt Jun 10, 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.

Just checking whether I understand correctly: aligned_end is not aligned, but good enough to serve as the end of the loop over aligned values. To make it really aligned we would need to do something like aligned_end = _Py_SIZE_ROUND_DOWN(_end, SIZEOF_SIZE_T)?

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

Yes that is the gist of it. I tried something similar to _Py_SIZE_ROUND_DOWN and got segfaults so I opted for this simpler tried and true solution. The name aligned_end is probably not the best, but I can't think of a better name now.

@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.

Should be something like

Py_ssize_t n = end - begin;
const STRINGLIB_CHAR *p = begin;
const STRINGLIB_CHAR *aligned_end = begin + _Py_SIZE_ROUND_DOWN(n, ALIGNOF_SIZE_T);

Would be interested in understanding why you got a segfault though.

const size_t *unrolled_end = aligned_end - 3;
unsigned char accumulator = 0;
/* Do not test each character individually, bit use bitwise OR and test
Comment thread
rhpvorderman marked this conversation as resolved.
Outdated
all characters at once. */
while (p < _end && p < aligned_start) {
while (p < _end && !_Py_IS_ALIGNED(p, ALIGNOF_SIZE_T)) {
accumulator |= *p;
p += 1;
}
Expand Down