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> <75e3bb4f88fa43097540f3e2023df8388def5719.camel@perches.com>
In-Reply-To: <75e3bb4f88fa43097540f3e2023df8388def5719.camel@perches.com>
From:   Yu-Jen Chang <arthurchang09@gmail.com>
Date:   Mon, 11 Jul 2022 22:50:19 +0800
Message-ID: <CAD4RrFPbT=R7rYZhN=9JFtTnaupVjrU3F+JN+Yuxzw2ns_AHBw@mail.gmail.com>
Subject: Re: [PATCH 2/2] lib/string.c: Optimize memchr()
To:     Joe Perches <joe@perches.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

Joe Perches <joe@perches.com> =E6=96=BC 2022=E5=B9=B47=E6=9C=8810=E6=97=A5 =
=E9=80=B1=E6=97=A5 =E6=99=9A=E4=B8=8A11:16=E5=AF=AB=E9=81=93=EF=BC=9A
>
> On Sun, 2022-07-10 at 22:28 +0800, 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 s=
lightly
> > better in the first test and nearly 4x faster than the orginal
> > implementation in the second test.
>
> It seems you did not test this with 32bit compilers as
> there are 64 bit constants without ull

Yeah, it is better to add ull at the end of the constant. I test with
32-bit compiler and it works. The compiler will use two or more
instruction to reach the same result.

See https://godbolt.org/z/svbj18foP

>
> > diff --git 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)
> >  {
> > -     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;
> > +                     if ((val + 0xfefefefefefefeffu) &
> > +                         (~val & 0x8080808080808080u))
>
> here.
>