Constant mod over chars can use a cheaper FastMod

Open
#111,492 1 comment 4 reactions 1 assignee View on GitHub

@MihaZupan is already working on this.

Since Jan 17, 2025.

Assessment

This issue has not been assessed yet.

Description

area-CodeGen-coreclr help wanted in-pr

#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
https://github.com/dotnet/runtime/blob/e71d737628c7b807aa12755dabe4eca40c40da7e/src/libraries/System.Private.CoreLib/src/System/Collections/HashHelpers.cs#L107
we can use
https://github.com/dotnet/runtime/blob/e71d737628c7b807aa12755dabe4eca40c40da7e/src/libraries/System.Private.CoreLib/src/System/SearchValues/ProbabilisticMapState.cs#L223

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

Dominant language
C#
Stars
18.3k
Forks
5.6k
PR metrics pending

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from dotnet/runtime

All issues in dotnet/runtime

Similar issues

More C# issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.