lkml.org 
[lkml]   [2022]   [Jul]   [10]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
SubjectRe: [PATCH 2/2] lib/string.c: Optimize memchr()
From
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 “memchr()” 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)
> {
> - 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;

What if p is not aligned to 8 (or 4 on 32-bit targets) bytes? Not all
targets support (efficient) unaligned loads, do they?

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

\
 
 \ /
  Last update: 2022-07-10 22:01    [W:0.126 / U:4.620 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site