Re: [PATCH v3 next 09/10] lib: mul_u64_u64_div_u64() Optimise the divide code

[Nicolas Pitre]

On Wed, 18 Jun 2025, David Laight wrote:

> On Wed, 18 Jun 2025 11:39:20 -0400 (EDT)
> Nicolas Pitre <nico@xxxxxxxxxxx> wrote:
> 
> > > > +		q_digit = n_long / d_msig;  
> > > 
> > > I think you want to do the divide right at the top - maybe even if the
> > > result isn't used!
> > > All the shifts then happen while the divide instruction is in progress
> > > (even without out-of-order execution).  

Well.... testing on my old Intel Core i7-4770R doesn't show a gain.

With your proposed patch as is: ~34ns per call

With my proposed changes: ~31ns per call

With my changes but leaving the divide at the top of the loop: ~32ns per call

> Can you do accurate timings for arm64 or arm32?

On a Broadcom BCM2712 (ARM Cortex-A76):

With your proposed patch as is: ~20 ns per call

With my proposed changes: ~19 ns per call

With my changes but leaving the divide at the top of the loop: ~19 ns per call

Both CPUs have the same max CPU clock rate (2.4 GHz). These are obtained 
with clock_gettime(CLOCK_MONOTONIC) over 56000 calls. There is some 
noise in the results over multiple runs though but still.

I could get cycle measurements on the RPi5 but that requires a kernel 
recompile.

> I've found a 2004 Arm book that includes several I-cache busting
> divide algorithms.
> But I'm sure this pi-5 has hardware divide.

It does.


Nicolas