Ben Joffe's Mersenne weekday trick vs plain %7 in clang, V8, and CPython on M4

Ben Joffe published A faster way to calculate the day-of-the-week on August 17, 2026. Because 7 is a Mersenne number ($2^3-1$), the modulo at the heart of weekday calculation can be replaced with a multiply, an add, and a shift. Rust’s datetime library Jiff adopted the algorithm, and callers like nth_weekday_of_month got about 40% faster.

clang already turns % 7 into a magic-number multiply and shift, the constant-division optimization compilers have done for decades. Can a hand-written bit hack still win? I benchmarked it on an M4 Mac mini to find out.

Short version: 1.6-6.4x faster in clang, Rust, and V8. 3x slower in CPython. And the biggest slowdown I hit had nothing to do with the modulo at all.

Like when I ran Quake III’s fast inverse square root on the M4, I went through the whole thing: exhaustive correctness checks, timings, and the generated code. And since the “a few CPU instructions” premise itself gets shaky on V8 and CPython, I ran the same comparison there too.

How the algorithm works

The input is a day count with January 1, 1970 as day 0 (Rata Die); negative values are dates before 1970. Written the ordinary way, with weekday 0 = Sunday through 6 = Saturday:

uint32_t weekday(int32_t rd) {
    return ((rd % 7) + 11) % 7;
}

C’s % returns a negative remainder for negative dividends, so you add + 11 (4 to align the weekday, 7 to push the remainder positive) and take % 7 again. The standard idiom.

Joffe’s method never computes n % 7 directly. Using the identity n % 7 = floor(n * 8 / 7) % 8, it reinterprets the 7-day cycle as an 8-day cycle where the 8th day is imaginary. A remainder mod 8 is just the low 3 bits, so all that’s left is approximating n * 8 / 7, which one fixed-point constant multiply can do.

If a practical range (±89,434,796 days, about ±245,000 years) is enough, it gets this short:

uint32_t weekday_joffe(int32_t rd) {
    const uint32_t M = 613566757;   // (1 << 32) / 7 + 1
    const uint32_t Z = 0x94920000;  // includes the 1970-epoch weekday offset
    return ((uint32_t)rd * M + Z) >> 29;
}

M is a fixed-point approximation of $2^{32} \cdot \frac{8}{7} \cdot \frac{1}{8}$, and the multiply’s overflow acts as a free “mod $2^{32}$”. The constant Z rotates the output so that the 1970 epoch lands on Thursday. Since the whole computation stays in unsigned 32-bit arithmetic from start to finish, there is no branch for negative dates and no +11 fixup. The top 3 bits are the weekday inside the imaginary 8-day week, and >> 29 extracts them.

The full version, correct across all of int32, adds two terms that compensate for the approximation error:

uint32_t weekday_joffe_full(int32_t rd) {
    const uint32_t M = 613566756;   // (1 << 32) / 7
    const uint32_t Z = 0x95000000;
    const uint32_t a = (uint32_t)rd * M + Z;
    const uint32_t b = (uint32_t)((rd >> 1) + (rd >> 4));
    return (a + b) >> 29;
}

The original article has dozens of variants (8/16/64-bit, ISO weekday with Monday = 1, different epochs), all collected in fast-world-calendars on GitHub. I compared these two against the ordinary code.

Benchmark setup

Everything ran on my M4 Mac mini with the same input data and the same measurement method.

Item	Value
Machine	Mac mini (Apple M4, 10 cores)
Memory	16 GB unified memory
OS	macOS 26.5.2
C	Apple clang 21.0.0, -O2
Rust	rustc 1.92.0, -O
JavaScript	Node.js 25.3.0 (V8 14.1)
Python	CPython 3.14.4
Data	2M uniform random days in ±89,000,000 (200k for Python)
Timing	best of 7 runs, ns/op

I measured throughput (independent values streamed from an array) and latency (each result mixed into the next input, forming a serial chain) separately. Array processing behaves like the throughput number; a single call in isolation feels closer to the latency number.

Before timing anything, the C build checked correctness: all 4.3 billion int32 values against the full version, and the entire documented range (-89,434,796 to 89,522,175) for the limited version. Every implementation agreed. As it happens, the first thing this check caught wasn’t Joffe’s code but my own comparison function: rd + 4 overflows near INT32_MAX, which is undefined behavior. I widened it to int64 and it passed.

The full measurement code is at LiltingChannelLabo/2026/08/20/fast-day-of-week-mersenne-benchmark.

Against clang’s magic-number division

Starting with C, I compiled two ordinary versions and two Joffe versions with -O2 and dumped the standalone assembly.

The ordinary ((rd % 7) + 11) % 7 came out at 21 instructions. clang converts the first % 7 into a magic-number multiply (a smull + shift + msub sequence). The second one is even fancier: clang runs value-range analysis, works out that (rd % 7) + 11 fits in 5-17, and picks an 8-bit-wide version of the same multiply (multiply by 37, shift by 8). Both % 7 operations survive, though. Folding them into a single (rd + 11) % 7 would change the result for negative inputs, so clang optimizes the expression as written.

The rem_euclid-style version (take the remainder, add 7 if negative) came out at 14 instructions, with the branch turned into a csel. Joffe’s full version: 8 instructions. The limited version is, constant loads aside, two instructions: madd (multiply-add) and lsr (right shift). That is fewer than the “multiply, add, shift” of the original article, because madd does the multiply and the add in one instruction.

_joffe_narrow:
    mov  w8, #18725             ; M = 613566757 (low)
    movk w8, #9362, lsl #16     ; M (high)
    mov  w9, #-1802371072       ; Z = 0x94920000
    madd w8, w0, w8, w9         ; rd * M + Z
    lsr  w0, w8, #29            ; top 3 bits
    ret

The measurements:

Implementation	Instructions	Throughput (ns/op)	Latency (ns/op)
((rd%7)+11)%7	21	0.379	5.89
rem_euclid style	14	0.320	2.98
Joffe full	8	0.104	1.82
Joffe limited	5	0.059	1.81

The limited version’s 0.059 ns/op works out to roughly 0.26 cycles per element at M4 clock speeds. Same phenomenon as the inverse square root article: the whole loop gets auto-vectorized to NEON (323 vector-register operations in the assembly). The ordinary version gets the same treatment, and the gap is still 6.4x. Even on latency, which is closer to a single isolated call, 3.2x remains.

The compiler does optimize % 7. But what clang preserves is “the result of C’s %”. It has no idea the number is a weekday. A human gets to decide that the epoch offset and the negative-number wraparound can be baked into the constant Z, and that a 7-day week may be treated as an 8-day week. That freedom is the difference between 21 instructions and 5.

I also measured with optimization off (-O0). The magic-number multiply disappears and an actual sdiv division instruction shows up, but the M4’s integer divide is fast: 1.27 ns/op for the ordinary version vs 0.92 for Joffe’s limited version (function-call overhead included), so the gap shrinks to 1.4x. The M4’s integer divide is fast enough that the gap stays this small even without the magic-number multiply.

Reproducing the Jiff swap in Rust

Jiff replaced a code path that used rem_euclid(7) with this trick, so I measured the same three implementations in Rust.

fn naive_rem_euclid(rd: i32) -> u32 {
    ((rd as i64 + 4).rem_euclid(7)) as u32
}

fn joffe_narrow(rd: i32) -> u32 {
    ((rd as u32).wrapping_mul(613_566_757).wrapping_add(0x9492_0000)) >> 29
}

Implementation	Throughput (ns/op)	Latency (ns/op)
rem_euclid(7)	0.307	2.95
((rd%7)+11)%7	0.376	5.92
Joffe limited	0.059	1.58

The numbers are nearly identical to C. rustc and clang both hand code generation to the same LLVM, so at this function size the language makes no difference. If the microbenchmark’s 5.2x throughput and 1.9x latency get diluted to 40% inside real library functions that also unpack date objects and compute month starts, that squares with what Jiff measured.

How far does V8’s JIT go

I wrote the same three implementations in JavaScript.

function naive(rd) {
  return ((rd % 7) + 11) % 7;
}

function naiveBranch(rd) {
  const r = (rd + 4) % 7;
  return r < 0 ? r + 7 : r;
}

function joffe(rd) {
  return ((Math.imul(rd, 613566757) + 0x94920000) | 0) >>> 29;
}

Math.imul gives you the 32-bit multiply with overflow truncation and >>> 29 gives you the unsigned shift, so u32 semantics carry over to JavaScript directly.

The results, measured one function per process (more on why below):

Implementation	Throughput (ns/op)	Latency (ns/op)
((rd%7)+11)%7	0.90	5.67
branch fixup (rd+4)%7	34.0	39.4
Joffe limited	0.58	1.35

To see how the plain % 7 manages 0.90 ns/op, I dumped V8’s optimized code with --print-opt-code: smull and msub sit right where the % 7 is. TurboFan does the same magic-number division the compilers do. My assumption that a JIT would just emit a divide was wrong. Joffe’s version still won: 1.6x on throughput, 4.2x on latency. This V8 code showed no NEON auto-vectorization, so the vectorization bonus that C enjoyed is absent and the gap is smaller than in C.

Only the branch version is drastically slow

In the middle row of the table, the branch-fixup version alone takes 34 ns/op, 37x the plain version for the same computation.

The cause is JavaScript’s -0. (rd + 4) % 7 returns -0 whenever rd + 4 is a negative multiple of 7. JavaScript numbers are all doubles per the spec, so 0 and -0 exist as distinct values. V8 stores small integers in a pointer-embedded representation called Smi, but -0 cannot be a Smi and has to live as a heap double. Every time a -0 shows up in code optimized under the assumption of integers, the type feedback breaks and a deoptimization (deopt: throwing away the optimized code and starting over) fires. --trace-deopt showed it deoptimizing and reoptimizing over and over.

To narrow it down, I fed the same function different input data:

Input data	Throughput (ns/op)
Mixed signs (-0 occurs)	34.0
Positive only	1.32
Negative included, -0 cases excluded	3.28

Values that produce -0 are only about 7% of the input, yet the deopts they trigger slow the whole thing down 25x. In JavaScript, the “add 7 if negative” idiom ported from C slowed things down by two orders of magnitude more than the modulo style itself.

The numbers change with the order of functions

One more problem showed up before the results did, in how I measured. At first I benchmarked all four implementations in one file, and got 0.9 ns/op for plain %7 and 3.9 ns/op for Joffe’s version. Swapping the order of the functions turned plain %7 into 41 ns/op.

Run several functions through one shared benchmark loop and the call site’s type feedback goes polymorphic: later functions never get inlined, or the optimized code built for an earlier function gets deoptimized wholesale. A 4x difference I had been chasing as a constant-encoding effect also vanished when I changed the order. With multiple functions passed through a shared loop like this, the results depend on measurement order. Every number in the table above was re-measured with one process per function.

The same comparison in CPython

Finally, CPython. Python’s % always returns a non-negative result for a positive modulus, so no negative-number fixup code is needed in the first place.

def naive(rd):
    return (rd + 4) % 7

def joffe(rd):
    return ((rd * 613566757 + 2492596224) & 0xFFFFFFFF) >> 29

Python ints are arbitrary-precision, so u32 overflow has to be reproduced by hand with an & 0xFFFFFFFF mask, and the hand-written version ends up with more operations, not fewer.

Implementation	ns/op (function call)	ns/op (inline loop)
(rd + 4) % 7	27.1	18.9
Joffe limited	70.8	63.1

The hand-written version is more than 3x slower. In CPython, % and * are not single CPU instructions but operations on PyLong objects, each costing several to tens of nanoseconds. The ordinary version is 2 operations; the hand-written one is 4, and rd * 613566757 produces 56-bit values that push the bignum into more digits. The whole idea of shaving CPU instructions does not apply in CPython; the operation count translates directly into the speed difference.

CPython 3.14 does have an experimental JIT, but my Python was built without it.

Speed ratios across the runtimes

The four runtimes side by side:

Runtime	Joffe vs ordinary code	% 7 optimization
clang -O2	3.2-6.4x faster	converted to multiply and shift
rustc -O	1.9-5.2x faster	converted to multiply and shift
V8 (TurboFan)	1.6-4.2x faster	converted to multiply and shift
CPython 3.14	0.3x (3x slower)	none (not applicable to begin with)

Compilers and JITs alike had long since optimized % 7 on its own, and the hand-written version was still 1.6-6.4x faster. The margin comes from decisions no runtime is allowed to make: the input is a day count within ±a few hundred thousand years, the epoch may be shifted, and a 7-day week may be treated as an 8-day one, all baked into the constants. CPython went the other way: the operation count grew from two to four, and it got slower by that amount.