Optimized implementation for uN::{gather,scatter}_bits #149663
Merged
+176
−40
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This comment has been minimized.
This comment has been minimized.
9549004 to
2c752af
Compare
This comment has been minimized.
This comment has been minimized.
2c752af to
ac7e6c6
Compare
Contributor
Author
|
Do take this with a grain of salt, since I authored the benchmarks with this in mind. In particular, since the new implementation doesn't have any input-dependent control-flow, it is easily vectorized which all of these benchmarks allow for. Benchmarked locally on an
|
Collaborator
|
rustbot has assigned @Mark-Simulacrum. Use |
okaneco
reviewed
Dec 8, 2025
Contributor
There was a problem hiding this comment.
Nice work.
I noticed spot-checking some random constant masks that this implementation and the HD implementation flip-flop on which has more instructions, but it's only a small difference count. On simpler masks, they seem to optimize similarly.
The dynamic mask output is a drastic improvement with this by a quarter/third reduction of instructions for gather and scatter.
alive2 showing that this implementation and the current implementation appear to be equivalent functions
gather - https://alive2.llvm.org/ce/z/wKxY2Z
scatter - https://alive2.llvm.org/ce/z/_98DbY
scratchpad for the LLVM IR output - https://rust.godbolt.org/z/brbePx44T
4 tasks
Member
|
@bors r+ rollup |
Collaborator
JonathanBrouwer
added a commit
to JonathanBrouwer/rust
that referenced
this pull request
Dec 28, 2025
… r=Mark-Simulacrum
Optimized implementation for uN::{gather,scatter}_bits
Feature gate: #![feature(uint_gather_scatter_bits)]
Tracking issue: rust-lang#149069
Accepted ACP: rust-lang/libs-team#695
Implements the methods using the parallel suffix strategy mentioned in the ACP discussion. The referenced source material provides C implementations, though this PR makes improvements over those, cutting the instruction count by a third:
https://rust.godbolt.org/z/rn5naYnK4 (this PR)
https://c.godbolt.org/z/WzYd5WbsY (Hacker's delight)
This was initially based on the code for `gather_bits` that `@okaneco` provided in rust-lang/libs-team#695 (comment) . I wanted to understand how it worked, and later on noticed some opportunities for improvement, which eventually led to this PR.
This was referenced Dec 28, 2025
bors
added a commit
that referenced
this pull request
Dec 28, 2025
…uwer Rollup of 8 pull requests Successful merges: - #148321 (parser/lexer: bump to Unicode 17, use faster unicode-ident) - #149540 (std: sys: fs: uefi: Implement readdir) - #149582 (Implement `Duration::div_duration_{floor,ceil}`) - #149663 (Optimized implementation for uN::{gather,scatter}_bits) - #149667 (Fix ICE by rejecting const blocks in patterns during AST lowering (closes #148138)) - #149947 (add several older crashtests) - #150011 (Add more `unbounded_sh[lr]` examples) - #150411 (refactor `destructure_const`) r? `@ghost` `@rustbot` modify labels: rollup
rust-timer
added a commit
that referenced
this pull request
Dec 29, 2025
Rollup merge of #149663 - quaternic:gather-scatter-bits-opt, r=Mark-Simulacrum Optimized implementation for uN::{gather,scatter}_bits Feature gate: #![feature(uint_gather_scatter_bits)] Tracking issue: #149069 Accepted ACP: rust-lang/libs-team#695 Implements the methods using the parallel suffix strategy mentioned in the ACP discussion. The referenced source material provides C implementations, though this PR makes improvements over those, cutting the instruction count by a third: https://rust.godbolt.org/z/rn5naYnK4 (this PR) https://c.godbolt.org/z/WzYd5WbsY (Hacker's delight) This was initially based on the code for `gather_bits` that ``@okaneco`` provided in rust-lang/libs-team#695 (comment) . I wanted to understand how it worked, and later on noticed some opportunities for improvement, which eventually led to this PR.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
6 participants
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
Feature gate: #![feature(uint_gather_scatter_bits)]
Tracking issue: #149069
Accepted ACP: rust-lang/libs-team#695
Implements the methods using the parallel suffix strategy mentioned in the ACP discussion. The referenced source material provides C implementations, though this PR makes improvements over those, cutting the instruction count by a third:
https://rust.godbolt.org/z/rn5naYnK4 (this PR)
https://c.godbolt.org/z/WzYd5WbsY (Hacker's delight)
This was initially based on the code for
gather_bitsthat @okaneco provided in rust-lang/libs-team#695 (comment) . I wanted to understand how it worked, and later on noticed some opportunities for improvement, which eventually led to this PR.