Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
MIME-Version: 1.0
References: <20220710142822.52539-1-arthurchang09@gmail.com>
 <20220710142822.52539-3-arthurchang09@gmail.com> <3a1b50d2-a7aa-3e89-56fe-5d14ef9da22f@gmail.com>
 <CAD4RrFPihC+8LScC1RJ5GfOsLs4kze0QwALS1ykNH_m89Z1NGg@mail.gmail.com> <48db247e-f6fd-cb4b-7cc5-455bf26bb153@gmail.com>
In-Reply-To: <48db247e-f6fd-cb4b-7cc5-455bf26bb153@gmail.com>
From:   Yu-Jen Chang <arthurchang09@gmail.com>
Date:   Tue, 12 Jul 2022 22:58:32 +0800
Message-ID: <CAD4RrFPfwu4Ascj5tdz8qq2Qgnu5GN2eHjVwMW5AqUa1H7JapA@mail.gmail.com>
Subject: Re: [PATCH 2/2] lib/string.c: Optimize memchr()
To:     Andrey Semashev <andrey.semashev@gmail.com>
Cc:     andy@kernel.org, akinobu.mita@gmail.com,
        Ching-Chun Huang <jserv@ccns.ncku.edu.tw>,
        linux-kernel@vger.kernel.org
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Precedence: bulk

Andrey Semashev <andrey.semashev@gmail.com> =E6=96=BC 2022=E5=B9=B47=E6=9C=
=8811=E6=97=A5 =E9=80=B1=E4=B8=80 =E6=99=9A=E4=B8=8A11:00=E5=AF=AB=E9=81=93=
=EF=BC=9A
>
> On 7/11/22 17:52, Yu-Jen Chang wrote:
> > Andrey Semashev <andrey.semashev@gmail.com> =E6=96=BC 2022=E5=B9=B47=E6=
=9C=8811=E6=97=A5 =E9=80=B1=E4=B8=80 =E5=87=8C=E6=99=A84:01=E5=AF=AB=E9=81=
=93=EF=BC=9A
> >>
> >> On 7/10/22 17:28, Yu-Jen Chang wrote:
> >>> The original version of memchr() is implemented with the byte-wise
> >>> comparing technique, which does not fully use 64-bits or 32-bits
> >>> registers in CPU. We use word-wide comparing so that 8 characters
> >>> can be compared at the same time on CPU. This code is base on
> >>> David Laight's implementation.
> >>>
> >>> We create two files to measure the performance. The first file
> >>> contains on average 10 characters ahead the target character.
> >>> The second file contains at least 1000 characters ahead the
> >>> target character. Our implementation of =E2=80=9Cmemchr()=E2=80=9D is=
 slightly
> >>> better in the first test and nearly 4x faster than the orginal
> >>> implementation in the second test.
> >>>
> >>> Signed-off-by: Yu-Jen Chang <arthurchang09@gmail.com>
> >>> Signed-off-by: Ching-Chun (Jim) Huang <jserv@ccns.ncku.edu.tw>
> >>> ---
> >>>  lib/string.c | 28 +++++++++++++++++++++-------
> >>>  1 file changed, 21 insertions(+), 7 deletions(-)
> >>>
> >>> diff --git a/lib/string.c b/lib/string.c
> >>> index 80469e6c3..8ca965431 100644
> >>> --- a/lib/string.c
> >>> +++ b/lib/string.c
> >>> @@ -905,21 +905,35 @@ EXPORT_SYMBOL(strnstr);
> >>>  #ifndef __HAVE_ARCH_MEMCHR
> >>>  /**
> >>>   * memchr - Find a character in an area of memory.
> >>> - * @s: The memory area
> >>> + * @p: The memory area
> >>>   * @c: The byte to search for
> >>> - * @n: The size of the area.
> >>> + * @length: The size of the area.
> >>>   *
> >>>   * returns the address of the first occurrence of @c, or %NULL
> >>>   * if @c is not found
> >>>   */
> >>> -void *memchr(const void *s, int c, size_t n)
> >>> +void *memchr(const void *p, int c, unsigned long length)
>
> I didn't comment on this initially, but is the change of length type
> intentional? Why?

It is my mistake. I will change the type back to size_t.

>
> >>>  {
> >>> -     const unsigned char *p =3D s;
> >>> -     while (n-- !=3D 0) {
> >>> -             if ((unsigned char)c =3D=3D *p++) {
> >>> -                     return (void *)(p - 1);
> >>> +     u64 mask, val;
> >>> +     const void *end =3D p + length;
> >>> +
> >>> +     c &=3D 0xff;
> >>> +     if (p <=3D end - 8) {
> >>> +             mask =3D c;
> >>> +             MEMCHR_MASK_GEN(mask);
> >>> +
> >>> +             for (; p <=3D end - 8; p +=3D 8) {
> >>> +                     val =3D *(u64 *)p ^ mask;
> >>
> >> What if p is not aligned to 8 (or 4 on 32-bit targets) bytes? Not all
> >> targets support (efficient) unaligned loads, do they?
> >
> > I think it works if p is not aligned to 8 or 4 bytes.
> >
> > Let's say the string is 10 bytes. The for loop here will search the fir=
st
> > 8 bytes. If the target character is in the last 2 bytes, the second for
> > loop will find it. It also work like this on 32-bit machine.
>
> 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.

void *memchr(const void *p, int c, size_t length)
{
    u64 mask, val;
    const void *end =3D p + length;
    c &=3D 0xff;
    while ((long ) p & (sizeof(long) - 1)) {
        if (p >=3D end)
            return NULL;
        if (*(unsigned char *)p =3D=3D c)
            return (void *) p;
        p++;
    }
    if (p <=3D end - 8) {
        mask =3D c;
        MEMCHR_MASK_GEN(mask);

        for (; p <=3D end - 8; p +=3D 8) {
            val =3D *(u64*)p ^ mask;
            if ((val + 0xfefefefefefefeffull)
& (~val & 0x8080808080808080ull))
                break;
        }
    }

    for (; p < end; p++)
        if (*(unsigned char *)p =3D=3D c)
            return (void *)p;

    return NULL;
}

>
> >>
> >>> +                     if ((val + 0xfefefefefefefeffu) &
> >>> +                         (~val & 0x8080808080808080u))
> >>> +                             break;
> >>>               }
> >>>       }
> >>> +
> >>> +     for (; p < end; p++)
> >>> +             if (*(unsigned char *)p =3D=3D c)
> >>> +                     return (void *)p;
> >>> +
> >>>       return NULL;
> >>>  }
> >>>  EXPORT_SYMBOL(memchr);
> >>
>