[PATCH] riscv: lib: Implement optimized memchr function

[Ivan Orlov]

On 27/03/2024 14:21, Palmer Dabbelt wrote:
> On Mon, 11 Dec 2023 07:25:15 PST (-0800), ivan.orlov at codethink.co.uk wrote:
>> On 11/12/2023 15:08, Andrew Jones wrote:
>>>> As you can see, the new function shows much better results even for
>>>> the small arrays of 256 elements, therefore I believe it could be a
>>>> useful addition to the existing riscv-specific string functions.
>>>
>>> Looks good, but do we want to maintain both this version and a zbb
>>> version? I'd expect a zbb version to be even better.
>>>
>>
>> Hi Andrew,
>>
>> Yes, ZBB analog would be much better, and if we use ZBB operations we
>> could avoid the most part of bit magic happening there.
>>
>>>> +    add t1, x0, a2
>>>
>>> move t1, a2
>>>
>>> and for the remainder of the function s/x0/zero/
>>>
>>
>> Alright, will be fixed in the next version.
>>>> +    sltiu t2, a2, MIN_BORDER
>>>> +    bnez t2, 6f
>>>> +
>>>> +    // get the number of bytes we should iterate before alignment
>>>
>>> I'm not sure, but I think even in assembly we prefer the /* */ comment
>>> format.
>>>
>>>> +    andi t0, a0, SZREG - 1
>>>> +    beqz t0, 4f
>>>> +
>>>> +    # get the SZREG - t0
>>>
>>> I'm 99% sure we don't want to use the # comment syntax.
>>>
>>>> +    xor t0, t0, SZREG - 1
>>>
>>> xori?
>>>
>>
>> Hmm, I'm surprised that it is actually compilable... Yeah, should be 
>> fixed
>>>> +    addi t0, t0, 1
>>>> +
>>>> +    sub a2, a2, t0
>>>
>>> nit: Looks a bit odd to put a blank line above the sub line above,
>>> instead of above the below comment.
>>>
>>>> +    // iterate before alignment
>>>> +1:
>>>> +    beq t0, x0, 4f
>>>> +    lbu t2, 0(a0)
>>>> +    beq t2, a1, 3f
>>>> +    addi t0, t0, -1
>>>
>>> This addi t0... isn't necessary if we do
>>>
>>
>> Yeah, sounds reasonable, we can make it faster
>>>     add t0, a0, t0
>>> 1:
>>>     beq a0, t0, 4f
>>>     ...
>>>     ...
>>>     addi a0, a0, 1
>>>     j 1b
>>>
>>>> +    addi a0, a0, 1
>>>> +    j 1b
>>>> +
>>>> +2:
>>>> +    // found a word. Iterate it until we find the target byte
>>>> +    li t1, SZREG
>>>> +    j 6f
>>>
>>> These instructions seem oddly placed among the rest.
>>>
>>>> +3:
>>>> +    ret
>>>
>>> And this is an odd place to put this ret (after unconditional jump and
>>> in the middle of the function). We can just put a label at the bottom 
>>> ret.
>>>
>>
>> I agree, thanks!
>>>> +
>>>> +4:
>>>> +    // get the count remainder
>>>> +    andi t1, a2, SZREG - 1
>>>> +
>>>> +    // align the count
>>>> +    sub a2, a2, t1
>>>> +
>>>> +    // if we have no words to iterate, iterate the remainder
>>>> +    beqz a2, 6f
>>>> +
>>>> +    // from 0xBA we will get 0xBABABABABABABABA
>>>> +    li t3, REP_01
>>>> +    mul t3, t3, a1
>>>
>>> I don't think we want to implement an optimized assembly function with
>>> mul. We can just use a few shifts and ors.
>>>
>>>     slli    t3, a1, 8
>>>     or    t3, t3, a1
>>>     slli    t4, t3, 16
>>>     or    t3, t4, t3
>>> #if __riscv_xlen == 64
>>>     slli    t4, t3, 32
>>>     or    t3, t4, t3
>>> #endif
>>>
>>
>> Nice point, thanks! Will be optimized :)
>>>> +
>>>> +    add a2, a2, a0
>>>> +
>>>> +    li t4, REP_01
>>>> +    li t5, REP_80
>>>> +
>>>> +5:
>>>> +    REG_L t2, 0(a0)
>>>> +
>>>> +    // after this xor we will get one zero byte in the word if it 
>>>> contains the target byte
>>>> +    xor t2, t2, t3
>>>> +
>>>> +    // word v contains the target byte if (v - 0x01010101) & (~v) & 
>>>> 0x80808080 is positive
>>>
>>> s/is positive/is not zero/
>>>
>>>> +    sub t0, t2, t4
>>>> +
>>>> +    not t2, t2
>>>> +
>>>> +    and t0, t0, t2
>>>> +    and t0, t0, t5
>>>> +
>>>> +    bnez t0, 2b
>>>> +    addi a0, a0, SZREG
>>>> +    bne a0, a2, 5b
>>>> +
>>>> +6:
>>>> +    // iterate the remainder
>>>> +    beq t1, x0, 7f
>>>> +    lbu t4, 0(a0)
>>>> +    beq t4, a1, 3b
>>>> +    addi a0, a0, 1
>>>> +    addi t1, t1, -1
>>>
>>> Same comment as above about being able to drop the addi t1...
>>>
>>>> +    j 6b
>>>> +
>>>> +7:
>>>> +    addi a0, x0, 0
>>>
>>> li a0, 0
>>>
>>>> +    ret
>>>> +SYM_FUNC_END(memchr)
>>>> +SYM_FUNC_ALIAS(__pi_memchr, memchr)
>>>> -- 
>>>> 2.34.1
>>>>
>>>
>>> Thanks,
>>> drew
>>>
>>
>> Thanks a lot for the review!
> 
> Do you have a v2?  Sorry if I lost it.
> 

Hi Palmer,

Sorry for the late reply.

After a few experiments it became clear that we won't get such a large 
performance gain for the xlen=32. Also, I collected some usage 
statistics on the system, and it shown that `memchr` has to iterate more 
than 128 bytes quite infrequently.

Considering this information, it seems to me that such an 
overcomplication of the `memchr` function simply doesn't worth it. So, 
there was no V2 for this patch :(

Sorry, I should've written it earlier.

-- 
Kind regards,
Ivan Orlov