linux-kernel - Re: [PATCH v3 next 09/10] lib: mul_u64_u64_div

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <0143891q-ssp6-83on-4o61-nrp2qn3678o1@syhkavp.arg>
Date: Wed, 18 Jun 2025 16:12:49 -0400 (EDT)
From: Nicolas Pitre <nico@...xnic.net>
To: David Laight <david.laight.linux@...il.com>
cc: Andrew Morton <akpm@...ux-foundation.org>, linux-kernel@...r.kernel.org, 
    u.kleine-koenig@...libre.com, Oleg Nesterov <oleg@...hat.com>, 
    Peter Zijlstra <peterz@...radead.org>, 
    Biju Das <biju.das.jz@...renesas.com>
Subject: Re: [PATCH v3 next 09/10] lib: mul_u64_u64_div_u64() Optimise the
 divide code

On Wed, 18 Jun 2025, David Laight wrote:

> On Wed, 18 Jun 2025 11:39:20 -0400 (EDT)
> Nicolas Pitre <nico@...xnic.net> 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