Repository navigation
Keep PyLong "x_divrem" inner loop carry in 64 bits #160872
Description
Feature or enhancement
This is a split issue from #156443, which focus on the improvement of longobject x_divrem inner loop.
The inner loop x_divrem:
/* subtract q*w0[0:size_w] from vk[0:size_w+1] */
zhi = 0;
for (i = 0; i < size_w; ++i) {
/* invariants: -PyLong_BASE <= -q <= zhi <= 0;
-PyLong_BASE * q <= z < PyLong_BASE */
z = (sdigit)vk[i] + zhi - (stwodigits)q * (stwodigits)w0[i];
vk[i] = (digit)z & PyLong_MASK;
zhi = (sdigit)Py_ARITHMETIC_RIGHT_SHIFT(stwodigits, z, PyLong_SHIFT);
}
zhi, the loop-carried borrow in Knuth Algorithm D, was stored as an sdigit (32-bit int) and then widened to 64-bit stwodigits on the next iteration. That extra conversion sat on the critical chain which is strong latency bounded:
ldr w0, [x12, x2, lsl #2]
ldr w1, [x27, x2, lsl #2]
add w0, w3, w0 // critical chain
sxtw x0, w0 // critical chain (32 -> 64)
umsubl x0, w1, w14, x0 // critical chain
and w1, w0, #0x3fffffff
str w1, [x12, x2, lsl #2]
asr x0, x0, #30 // critical chain
mov w3, w0 // critical chain (64 -> 32)
Store zhi as stwodigits instead to save the type conversions. Invaddition, the compiler can then compute vk[i] - q*w0[i] at first and only then add the carried borrow, so this computation no longer depends on zhi:
ldr w4, [x3, x1, lsl #2]
ldr w0, [x28, x1, lsl #2]
umsubl x0, w0, w13, x4
add x2, x0, x2 // critical chain
and w4, w2, #0x3fffffff
str w4, [x3, x1, lsl #2]
asr x2, x2, #30 // critical chain
The loop-carried chain shrinks to two instructions. Knuth invariants are unchanged, so quotients and remainders are the same. The pidigits benchmark improves about 8% on x86-64 and about 12% on AArch64.
The detailed performance data will be pasted later.
Has this already been discussed elsewhere?
No response given
Links to previous discussion of this feature:
No response
Activity
[-]Keep the PyLong x_divrem inner loop carry in 64 bits[/-][+]Keep PyLong "x_divrem" inner loop carry in 64 bits[/+]XiaohongGong commentedon Oct 29, 2026
This instructions inside the loop on X86_64 systems are also saved. Following is the code changed before:
The code is changed after:
Instructions on the critical chain are reduced from 5 to 3.
eendebakpt commentedon Oct 29, 2026
@XiaohongGong Would you like to make a PR? I can confirm a 1.08x gain on pidigits and minor gains for small digit divisions.
XiaohongGong commentedon Oct 30, 2026
Thanks for your test! Yes, I'm preparing the PR now, and will push to github soon~
XiaohongGong commentedon Nov 2, 2026
Performance data is shown in the github PR. Thanks!