Skip to content
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

Jump to bottom

Constant mod over chars can use a cheaper FastMod #111492

Open
MihaZupan opened this issue Jan 16, 2025 · 1 comment · May be fixed by #111535
Open

Constant mod over chars can use a cheaper FastMod #111492

MihaZupan opened this issue Jan 16, 2025 · 1 comment · May be fixed by #111535
Assignees
@MihaZupan
Labels
area-CodeGen-coreclr CLR JIT compiler in src/coreclr/src/jit and related components such as SuperPMI help wanted [up-for-grabs] Good issue for external contributors in-pr There is an active PR which will close this issue when it is merged
Milestone
Future

Comments

@MihaZupan
Copy link
Member

#101001 added a faster variant of FastMod that SearchValues now uses when it knows that the value and divisor are both < 2^16 (i.e. chars).
Instead of

runtime/src/libraries/System.Private.CoreLib/src/System/Collections/HashHelpers.cs

Line 107 in e71d737

uint highbits = (uint)(((((multiplier * value) >> 32) + 1) * divisor) >> 32);

we can use

runtime/src/libraries/System.Private.CoreLib/src/System/SearchValues/ProbabilisticMapState.cs

Line 223 in e71d737

ulong result = ((ulong)(multiplier * value) * divisor) >> 32;

Is it worth teaching the JIT to do something similar when it knows that values are in range?

int Mod1(char c) => c % 42;
int Mod2(char c) => (int)(((ulong)(102261127u * c) * 42) >> 32);
Test.Mod1(Char)
    L0000: movzx eax, cx
    L0003: mov ecx, eax
    L0005: shr ecx, 1
    L0007: imul rcx, 0x30c30c31
    L000e: shr rcx, 0x22
    L0012: imul ecx, 0x2a
    L0015: sub eax, ecx
    L0017: ret

Test.Mod2(Char)
    L0000: movzx eax, cx
    L0003: imul eax, 0x6186187
    L0009: imul rax, 0x2a
    L000d: shr rax, 0x20
    L0011: ret

sharplab
@MihaZupan MihaZupan added the area-CodeGen-coreclr CLR JIT compiler in src/coreclr/src/jit and related components such as SuperPMI label Jan 16, 2025
@dotnet-policy-service dotnet-policy-service bot added the untriaged New issue has not been triaged by the area owner label Jan 16, 2025
@dotnet-policy-service Dotnet Policy Service
Copy link
Contributor

Tagging subscribers to this area: @JulieLeeMSFT, @jakobbotsch
See info in area-owners.md if you want to be subscribed.

@EgorBo EgorBo added the help wanted [up-for-grabs] Good issue for external contributors label Jan 16, 2025
@EgorBo EgorBo added this to the Future milestone Jan 16, 2025
@EgorBo EgorBo removed the untriaged New issue has not been triaged by the area owner label Jan 16, 2025
@MihaZupan MihaZupan self-assigned this Jan 17, 2025
@MihaZupan MihaZupan linked a pull request Jan 17, 2025 that will close this issue
Open
@dotnet-policy-service dotnet-policy-service bot added in-pr There is an active PR which will close this issue when it is merged labels Jan 17, 2025
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@MihaZupan MihaZupan

Labels
area-CodeGen-coreclr CLR JIT compiler in src/coreclr/src/jit and related components such as SuperPMI help wanted [up-for-grabs] Good issue for external contributors in-pr There is an active PR which will close this issue when it is merged
Projects
None yet
Milestone
Future
Development

Successfully merging a pull request may close this issue.

JIT: Use faster mod for uint16 values MihaZupan/runtime
2 participants
@EgorBo @MihaZupan