linux-kernel - Re: [PATCH 1/5] ARM: findbit: document ARMv5 bit offset calculation

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: <Y1wwoTIjn3dBdLzX@shell.armlinux.org.uk>
Date:   Fri, 28 Oct 2022 20:42:25 +0100
From:   "Russell King (Oracle)" <linux@...linux.org.uk>
To:     Yury Norov <yury.norov@...il.com>
Cc:     Linus Torvalds <torvalds@...ux-foundation.org>,
        Catalin Marinas <catalin.marinas@....com>,
        Mark Rutland <mark.rutland@....com>,
        Will Deacon <will@...nel.org>,
        Linux Kernel Mailing List <linux-kernel@...r.kernel.org>,
        linux-arm-kernel@...ts.infradead.org,
        Alexey Klimov <klimov.linux@...il.com>
Subject: Re: [PATCH 1/5] ARM: findbit: document ARMv5 bit offset calculation

On Fri, Oct 28, 2022 at 11:37:44AM -0700, Yury Norov wrote:
> + Alexey Klimov
> 
> On Fri, Oct 28, 2022 at 06:45:50PM +0100, Russell King (Oracle) wrote:
> > On Fri, Oct 28, 2022 at 10:05:29AM -0700, Linus Torvalds wrote:
> > > On Fri, Oct 28, 2022 at 9:47 AM Russell King (Oracle)
> > > <rmk+kernel@...linux.org.uk> wrote:
> > > >
> > > > Document the ARMv5 bit offset calculation code.
> > > 
> > > Hmm. Don't the generic bitop functions end up using this? We do have a
> > > comment in the code that says
> > > 
> > >  * On ARMv5 and above, the gcc built-ins may rely on the clz instruction
> > >  * and produce optimal inlined code in all cases. On ARMv7 it is even
> > >  * better by also using the rbit instruction.
> > 
> > It's true that the generic code also makes use of the rbit and clz
> > instructions - but in terms of the speed of the functions these only
> > get used once we've found a word that is interesting to locate the
> > bit we want in.
> > 
> > > but that 'may' makes me wonder...
> > > 
> > > IOW, what is it in the hand-written code that doesn't get done by the
> > > generic code these days?
> > 
> > For the _find_first_bit, there isn't much difference in the number
> > of instructions or really what is going on, only the organisation
> > and flow of the code is more inline - but that shouldn't make much
> > of a difference. Yet, there is a definite repeatable measurable
> > difference between the two:
> > 
> > random-filled:
> > arm    : find_first_bit:               17778911 ns,  16448 iterations
> > generic: find_first_bit:               18596622 ns,  16401 iterations
> > 
> > sparse:
> > arm    : find_first_bit:                7301363 ns,    656 iterations
> > generic: find_first_bit:                7589120 ns,    655 iterations
> > 
> > The bigger difference is in the find_next_bit operations, and this
> > likely comes from the arm32 code not having the hassles of the "_and"
> > and other conditionals that the generic code has:
> > 
> > random-filled:
> > arm    : find_next_bit:                 2242618 ns, 163949 iterations
> > generic: find_next_bit:                 2632859 ns, 163743 iterations
> > 
> > sparse:
> > arm    : find_next_bit:                   40078 ns,    656 iterations
> > generic: find_next_bit:                   69943 ns,    655 iterations
> > 
> > find_next_zero_bit show a greater difference:
> > 
> > random-filled:
> > arm    : find_next_zero_bit:            2049129 ns, 163732 iterations
> > generic: find_next_zero_bit:            2844221 ns, 163938 iterations
> > 
> > sparse:
> > arm    : find_next_zero_bit:            3939309 ns, 327025 iterations
> > generic: find_next_zero_bit:            5529553 ns, 327026 iterations
> 
> Those numbers disagree with what Alexey has measured on Odroid board
> for A15 but somewhat in line with what he had for A7:

Considering no one has seen these patches until I've just posted
them, frankly I don't think there's any point me looking at anyone
elses results.

These changes make substantial improvements to the arm32 assembly
code versions.

If you want a like-for-like comparison, then please get Alexey to
test with these patches applied. I am confident that he will confirm
my results.

-- 
RMK's Patch system: https://www.armlinux.org.uk/developer/patches/
FTTP is here! 40Mbps down 10Mbps up. Decent connectivity at last!