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;
Message-ID: <75e3bb4f88fa43097540f3e2023df8388def5719.camel@perches.com>
Subject: Re: [PATCH 2/2] lib/string.c: Optimize memchr()
From:   Joe Perches <joe@perches.com>
To:     Yu-Jen Chang <arthurchang09@gmail.com>, andy@kernel.org,
        akinobu.mita@gmail.com
Cc:     jserv@ccns.ncku.edu.tw, linux-kernel@vger.kernel.org
Date:   Sun, 10 Jul 2022 08:16:17 -0700
In-Reply-To: <20220710142822.52539-3-arthurchang09@gmail.com>
References: <20220710142822.52539-1-arthurchang09@gmail.com>
         <20220710142822.52539-3-arthurchang09@gmail.com>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 8BIT
User-Agent: Evolution 3.44.1-0ubuntu1 
MIME-Version: 1.0
Precedence: bulk

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 “memchr()” is slightly
> 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

> 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 = s;
> -	while (n-- != 0) {
> -        	if ((unsigned char)c == *p++) {
> -			return (void *)(p - 1);
> +	u64 mask, val;
> +	const void *end = p + length;
> +
> +	c &= 0xff;
> +	if (p <= end - 8) {
> +		mask = c;
> +		MEMCHR_MASK_GEN(mask);
> +
> +		for (; p <= end - 8; p += 8) {
> +			val = *(u64 *)p ^ mask;
> +			if ((val + 0xfefefefefefefeffu) &
> +			    (~val & 0x8080808080808080u))

here.