linux-kernel - RE: [PATCH] riscv: lib: Optimize 'strlen' function

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] [day] [month] [year] [list]

Date: Mon, 18 Dec 2023 10:12:00 +0000
From: David Laight <David.Laight@...LAB.COM>
To: 'Ivan Orlov' <ivan.orlov0322@...il.com>, "paul.walmsley@...ive.com"
	<paul.walmsley@...ive.com>, "palmer@...belt.com" <palmer@...belt.com>,
	"aou@...s.berkeley.edu" <aou@...s.berkeley.edu>
CC: "conor.dooley@...rochip.com" <conor.dooley@...rochip.com>,
	"ajones@...tanamicro.com" <ajones@...tanamicro.com>, "samuel@...lland.org"
	<samuel@...lland.org>, "alexghiti@...osinc.com" <alexghiti@...osinc.com>,
	"linux-riscv@...ts.infradead.org" <linux-riscv@...ts.infradead.org>,
	"linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>,
	"skhan@...uxfoundation.org" <skhan@...uxfoundation.org>
Subject: RE: [PATCH] riscv: lib: Optimize 'strlen' function

From: Ivan Orlov 
> Sent: 18 December 2023 10:03
> 
> On 12/18/23 09:20, David Laight wrote:
> > From: Ivan Orlov
> >> Sent: 18 December 2023 01:42
> >>
> >> On 12/17/23 17:00, David Laight wrote:
> >>> I'd also guess that pretty much all the calls in-kernel are short.
> >>> You might try counting as: histogram[ilog2(strlen_result)]++
> >>> and seeing what it shows for some workload.
> >>> I bet you (a beer if I see you!) that you won't see many over 1k.
> >>
> >> Hi David,
> >>
> >> Here is the statistics for strlen result:
> >>
> >> [  223.169575] Calls count for 2^0: 6150
> >> [  223.173293] Calls count for 2^1: 184852
> >> [  223.177142] Calls count for 2^2: 313896
> >> [  223.180990] Calls count for 2^3: 185844
> >> [  223.184881] Calls count for 2^4: 87868
> >> [  223.188660] Calls count for 2^5: 9916
> >> [  223.192368] Calls count for 2^6: 1865
> >> [  223.196062] Calls count for 2^7: 0
> >> [  223.199483] Calls count for 2^8: 0
> >> [  223.202952] Calls count for 2^9: 0
> >> ...
> >>
> >> Looks like I've just lost a beer :)
> >>
> >> Considering this statistics, I'd say implementing the word-oriented
> >> strlen is an overcomplication - we wouldn't get any performance gain and
> >> it just doesn't worth it.
> >
> > And the 32bit version is about half the speed of the 64bit one.
> >
> > Of course, the fast way to do strlen is add a custom instruction!
> >
> >> I simplified your code a little bit, it looks like the alignment there
> >> is unnecessary: QEMU test shows the same performance independently from
> >> alignment. Tests on the board gave the same result (perhaps because the
> >> CPU on the board has 2 DDR channels?)
> >
> > The alignment is there because it can overread the string end
> > by one byte - and that mustn't cross a page boundary.
> > So you either have to mark the second load as 'may fault return
> > zero' or just not do it.
> >
> > If the data isn't in cache the cache load will dominate.
> > The DDR channels only affect cache load times.
> > Get a TLB miss and add a few thousand more clocks!
> >
> 
> Ah, right, sounds reasonable...
> 
> Overall, I believe your solution is better and it would be more fair if
> you send it as a patch :) Here is benchmark results for your version vs
> the original (the old) one on the Starfive VisionFive2 RISC-V board:

You might want to try reading 4 bytes before checking any.
It might be quicker on your cpu.
It is hard guessing what is best across multiple implementation.
(For testing I'd not worry about falling off the page.)

I'll let you do the patch, I don't even have a toolchain, never mind
anything to test it on.

	David

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)