Optimization of modulo 7 in `DateTime.DayOfWeek`

[jnyrup]

Description

In Lightning Talk: Saturday Is Coming Faster - Part 1 and Lightning Talk: Saturday Is Coming Faster -P art 2 @cassioneri presents a way to optimize % 7 for C++'s weekday::weekday{year_month_day} function.
The same micro-optimization seems to be applicable for C#'s DateTime.DayOfWeek, DateOnly.DayOfWeek and possibly other places in Calendar.cs and ISOWeek.cs using % 7.

In short: For the range of "days since epoch" between DateTime.MinValue and DateTime.MaxValue we can replace % 7 with this method.

private static uint FastMod7(uint n)
{
    Debug.Assert(n < 178_956_973);
    return 613_566_757 * n >> 29;
}

If we implement this fast path in DayOfWeek2, we can similarly to the talk, proof this works by simply enumerating all days between DateTime.MinValue and DateTime.MaxValue.

public DayOfWeek DayOfWeek2 => (DayOfWeek)FastMod7((uint)(UTicks / TimeSpan.TicksPerDay) + 1);

private static uint FastMod7(uint n)
{
    Debug.Assert(n < 178_956_973);
    return 613_566_757 * n >> 29;
}

for (var ticks = DateTime.MinValue.Ticks; ticks <= DateTime.MaxValue.Ticks; ticks += TimeSpan.TicksPerDay)
{
    var d = new MyDateTime(ticks);
    Debug.Assert(d.DayOfWeek == d.DayOfWeek2);
}

I tried micro benchmarking this and it shows a 5% improvement and a 14 B code size reduction.

BenchmarkDotNet v0.14.1-nightly.20250503.223, Windows 11 (10.0.26100.3775)
Unknown processor
.NET SDK 10.0.100-preview.3.25201.16
  [Host]     : .NET 10.0.0 (10.0.25.17105), X64 RyuJIT AVX-512F+CD+BW+DQ+VL+VBMI
  DefaultJob : .NET 10.0.0 (10.0.25.17105), X64 RyuJIT AVX-512F+CD+BW+DQ+VL+VBMI

Method	Mean	Error	StdDev	Ratio	RatioSD	Code Size
DayOfWeek	0.2111 ns	0.0015 ns	0.0013 ns	1.00	0.01	63 B
DayOfWeek2	0.2010 ns	0.0039 ns	0.0035 ns	0.95	0.02	49 B

asm

.NET 10.0.0 (10.0.25.17105), X64 RyuJIT AVX-512F+CD+BW+DQ+VL+VBMI

; WeekDayBenchmark0.DayOfWeek()
       mov       rdx,[rcx+8]
       mov       rax,3FFFFFFFFFFFFFFF
       and       rdx,rax
       mov       rcx,28B8FFC778816079
       mov       rax,rdx
       mul       rcx
       shr       rdx,25
       lea       ecx,[rdx+1]
       mov       rdx,2492492492492493
       mov       eax,ecx
       mul       rdx
       imul      eax,edx,7
       sub       ecx,eax
       mov       eax,ecx
       ret
; Total bytes of code 63

.NET 10.0.0 (10.0.25.17105), X64 RyuJIT AVX-512F+CD+BW+DQ+VL+VBMI

; WeekDayBenchmark0.DayOfWeek2()
       mov       rdx,[rcx+8]
       mov       rax,3FFFFFFFFFFFFFFF
       and       rdx,rax
       mov       rcx,28B8FFC778816079
       mov       rax,rdx
       mul       rcx
       shr       rdx,25
       inc       edx
       imul      eax,edx,24924925
       shr       eax,1D
       ret
; Total bytes of code 49

Benchmark code

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
using System.Diagnostics;
using System;

BenchmarkRunner.Run<WeekDayBenchmark>();

[DisassemblyDiagnoser]
public class WeekDayBenchmark
{
    public MyDateTime MyDateTime0 { get; set; }

    [GlobalSetup]
    public void GlobalSetup()
    {
        MyDateTime0 = new MyDateTime(DateTime.MaxValue.Ticks);
    }

    [Benchmark(Baseline = true)]
    public DayOfWeek DayOfWeek() => MyDateTime0.DayOfWeek;

    [Benchmark]
    public DayOfWeek DayOfWeek2() => MyDateTime0.DayOfWeek2;
}

public readonly partial struct MyDateTime
{
    private const ulong TicksMask = 0x3FFFFFFFFFFFFFFF;

    internal readonly ulong _dateData;

    public MyDateTime(long ticks)
    {
        _dateData = (ulong)ticks;
    }

    private ulong UTicks => _dateData & TicksMask;

    public DayOfWeek DayOfWeek => (DayOfWeek)(((uint)(UTicks / TimeSpan.TicksPerDay) + 1) % 7);

    public DayOfWeek DayOfWeek2 => (DayOfWeek)FastMod7((uint)(UTicks / TimeSpan.TicksPerDay) + 1);

    private static uint FastMod7(uint n)
    {
        Debug.Assert(n < 178_956_973);
        return 613_566_757 * n >> 29;
    }
}

Is this something that would be worth pursuing in the BCL or is it either not worth the complexity, should be handled by the JIT or something else?

[tarekgh]

@jnyrup thanks for pointing at that. Are you interested in submitting a PR? doing quick search, here are the places can be updated.

System.Private.CoreLib\src\System\DateOnly.cs:        public DayOfWeek DayOfWeek => (DayOfWeek)((_dayNumber + 1) % 7);
System.Private.CoreLib\src\System\DateTime.cs:        public DayOfWeek DayOfWeek => (DayOfWeek)(((uint)(UTicks / TimeSpan.TicksPerDay) + 1) % 7);
System.Private.CoreLib\src\System\Globalization\Calendar.cs:            int dayForJan1 = (int)GetDayOfWeek(time) - (dayOfYear % 7);
System.Private.CoreLib\src\System\Globalization\Calendar.cs:            int offset = (dayForJan1 - firstDayOfWeek + 14) % 7;
System.Private.CoreLib\src\System\Globalization\Calendar.cs:            dayForJan1 = (int)GetDayOfWeek(time) - (dayOfYear % 7);
System.Private.CoreLib\src\System\Globalization\Calendar.cs:            offset = (firstDayOfWeek - dayForJan1 + 14) % 7;
System.Private.CoreLib\src\System\Globalization\Calendar.cs:            int dayOfWeekOfFirstOfYear = (int)GetDayOfWeek(MinSupportedDateTime) - dayOfYear % 7;
System.Private.CoreLib\src\System\Globalization\Calendar.cs:            int offset = (firstDayOfWeek + 7 - dayOfWeekOfFirstOfYear) % 7;
System.Private.CoreLib\src\System\Globalization\Calendar.cs:            int dayOfWeekOfFirstOfPreviousYear = dayOfWeekOfFirstOfYear - 1 - (daysInYearBeforeMinSupportedYear % 7);
System.Private.CoreLib\src\System\Globalization\Calendar.cs:            int daysInInitialPartialWeek = (firstDayOfWeek - dayOfWeekOfFirstOfPreviousYear + 14) % 7;
System.Private.CoreLib\src\System\Globalization\ISOWeek.cs:                return (y + (y / 4) - cent + cent / 4) % 7;

[tannergooding]

This likely isn't something that can be easily handled by the JIT due to the required range knowledge.

However, it's notably also only saving around 2 cycles (changing out a 3+1 cycle imul+sub for a 1+1 cycle shr+inc), for code that is more magic and less understandable.

The benchmark notably also gave more standard deviation and couldn't accurately measure the difference. It's reporting both as take 1 cycle on a 5GHz computer, so you likely need to modify the benchmark code to be more comprehensive and such that it takes considerably more time than the accuracy of the underlying hardware timer (you need to be spending at least 100-300ns per iteration for realistic measurements, as that is roughly what the underlying high performance counter API for the OS will return).

A more comprehensive benchmark should give a better measurement of the differences, but there's still the consideration of how that can impact maintainability of the code long term for something that's saving less cycles than a branch mispredict or L1 cache (non-missed) access and is extremely unlikely to be the bottleneck in a real app.

-- CC. @EgorBo, @jkotas since I think this touches a bit around the realm of "unsafe" code. It's not memory unsafe, but it is an optimization that relies on certain invariants in the code for a very minor perf increase

[jkotas]

We have other existing places in DateTime code that depend on similar tricks, e.g.:

runtime/src/libraries/System.Private.CoreLib/src/System/DateTime.cs

Lines 1355 to 1374 in 86949c2

	private static void GetDate(ulong dateData, out int year, out int month, out int day)
	{
	// y100 = number of whole 100-year periods since 3/1/0000
	// r1 = (day number within 100-year period) * 4
	(uint y100, uint r1) = Math.DivRem(((uint)((dateData & TicksMask) / TicksPer6Hours) | 3U) + 1224, DaysPer400Years);
	ulong u2 = Math.BigMul(EafMultiplier, r1 | 3U);
	uint daySinceMarch1 = (uint)u2 / EafDivider;
	uint n3 = 2141 * daySinceMarch1 + 197913;
	year = (int)(100 * y100 + (uint)(u2 >> 32));
	// compute month and day
	month = (int)(n3 >> 16);
	day = (ushort)n3 / 2141 + 1;
	// rollover December 31
	if (daySinceMarch1 >= March1BasedDayOfNewYear)
	{
	++year;
	month -= 12;
	}
	}

I do not see a problem with it as long as long we have sufficient test coverage. These tricks do not invalidate type or memory safety that the unsafe code is concerned with.

[cassioneri]

@tannergooding :

This likely isn't something that can be easily handled by the JIT due to the required range knowledge.

You're right that the exact optimisation shown in my talk doesn't work for all uint values so the JIT can't use it as it is. However, as I mention therein, we can increase the range of applicability by using a similar constant with more bits. For 64-bits, that is, using the ulong constant ceil(2^64 / 7), the optimisation works for all uint values. Indeed, here is an exhaustive test:

https://godbolt.org/z/oEMrxKfY5

(It takes just a few seconds to run.) I could calculate the sharp upper bound for the range of validity but I'm a bit lazy right now 😬. It certainly doesn't cover the whole range of ulong values.

However, it's notably also only saving around 2 cycles (changing out a 3+1 cycle imul+sub for a 1+1 cycle shr+inc),

I disagree that we're replacing imul + sub with shr + inc. As you can see in the same link above, the instructions to get n % 7 are:

       mov      rdx, 0x2492492492492493
       mov      eax, edi
       mul      rdx:rax, rdx
       imul     eax, edx, 7
       sub      edi, eax
       mov      eax, edi

whereas for the optimised version they are:

       mov      eax, edi
       mov      rcx, 0x2492492492492493
       imul     rax, rcx
       shr      rax, 61

Notice that we save one mul amongst other instructions. I hope this helps.

[tannergooding]

I disagree that we're replacing imul + sub with shr + inc. As you can see in the same link above, the instructions to get n % 7 are:

Register to register moves are not fixed, they are dependent on inlining, surrounding code, and other factors. They are also zero-cost and handled by the register renamer on most CPUs from the past 20ish plus years

Immediate to register moves are likewise optimized and often elided by the CPU

The instructions here with real cost are mul, Imul, sub, and shr; which comprise the difference between the two. The example just above is for 64-bit and so the codegen is slightly different from 32-bit

A more comprehensive benchmark is needed, at minimum, because the numbers given in the original post aren’t accurate. They cannot be accurate because they are showing less than a cycle for the entire operation and less than a cycle of difference between them.

[tannergooding]

Noting that inaccurate measurements are not your fault here, it’s a known issue I’ve got tracked against BDN as dotnet/BenchmarkDotNet#1802

This has to do both with how it tries to measure empty method overhead and due to general imprecision introduced by measuring very small methods, which leads to inherent noise.

You really need to have larger test cases for accurate measurement of the relative change involved