Re: [PATCH 2/2] lib/string.c: Optimize memchr()
From: Andrey Semashev
Date: Wed Jul 13 2022 - 06:02:57 EST
On 7/13/22 12:49, Andrey Semashev wrote:
> On 7/13/22 12:39, David Laight wrote:
>> From: Yu-Jen Chang
>>> Sent: 12 July 2022 15:59
>> ...
>>>> I think you're missing the point. Loads at unaligned addresses may not
>>>> be allowed by hardware using conventional load instructions or may be
>>>> inefficient. Given that this memchr implementation is used as a fallback
>>>> when no hardware-specific version is available, you should be
>>>> conservative wrt. hardware capabilities and behavior. You should
>>>> probably have a pre-alignment loop.
>>>
>>> Got it. I add pre-alignment loop. It aligns the address to 8 or 4bytes.
>>
>> That should be predicated on !HAS_EFFICIENT_UNALIGNED_ACCESS.
>>
>> ...
>>> for (; p <= end - 8; p += 8) {
>>> val = *(u64*)p ^ mask;
>>> if ((val + 0xfefefefefefefeffull)
>>> & (~val & 0x8080808080808080ull))
>>> break;
>>
>> I would add a couple of comments, like:
>> // Convert to check for zero byte.
>> // Standard check for a zero byte in a word.
>> (But not the big 4 line explanation you had.
>>
>> It is also worth looking at how that code compiles
>> on 32bit arch that don't have a carry flag.
>> That is everything based on MIPS, including riscv.
>
> It may be worth looking at how glibc does it:
>
> https://sourceware.org/git/?p=glibc.git;a=blob;f=string/memchr.c;h=422bcd0cd646ea46711a57fa3cbdb8a3329fc302;hb=refs/heads/release/2.35/master#l46
>
> They do use 32-bit words on 32-bit targets and 64-bit on 64-bit ones. I
> think memchr in the kernel should follow this.
Also, if by chance this optimization is aimed for x86-64, it may be
worth adding an arch-specific version that uses ERMS.