Optimize memchr()

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.

lib/string.c +5 -7

@@ -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;

Quoted 6 lines

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.

Quoted 6 lines

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

lib/string.c

Quoted 2 lines

lib/string.c +0 -0

[]

Quoted 22 lines

lib/string.c +5 -7

@@ -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;

lib/string.c EXPORT_SYMBOL(strnstr); · line 928

Quoted 10 lines

lib/string.c +10 -0

+
+     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.

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 <[email protected]>

Signed-off-by Ching-Chun (Jim) Huang <[email protected]>

---
 lib/string.c | 28 +++++++++++++++++++++-------
 1 file changed, 21 insertions(+), 7 deletions(-)

lib/string.c +3 -7

index 80469e6c3..8ca965431 100644
@@ -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);

lib/string.c +8 -0

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

Quoted 48 lines

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 <[email protected]>

Signed-off-by Ching-Chun (Jim) Huang <[email protected]>

---
 lib/string.c | 28 +++++++++++++++++++++-------
 1 file changed, 21 insertions(+), 7 deletions(-)

lib/string.c +8 -7

index 80469e6c3..8ca965431 100644
@@ -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) {

lib/string.c EXPORT_SYMBOL(strnstr); · line 926

Quoted 5 lines

lib/string.c +5 -0

+             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?

Quoted 14 lines

lib/string.c +8 -0

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

Andrey Semashev <[email protected]> 於 2022年7月11日 週一 凌晨4:01寫道：

Quoted 32 lines · Yu-Jen Chang

Quoted 30 lines

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 <[email protected]>

Signed-off-by Ching-Chun (Jim) Huang <[email protected]>

---
 lib/string.c | 28 +++++++++++++++++++++-------
 1 file changed, 21 insertions(+), 7 deletions(-)

lib/string.c +1 -1

index 80469e6c3..8ca965431 100644
@@ -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

Quoted 8 lines

lib/string.c EXPORT_SYMBOL(strnstr); · line 915

Quoted 8 lines

lib/string.c +2 -2

- * @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)

Quoted 10 lines

Quoted 10 lines

lib/string.c +5 -4

 {
-     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) {

Quoted 8 lines

lib/string.c EXPORT_SYMBOL(strnstr); · line 926

Quoted 5 lines

lib/string.c +5 -0

+             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?

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 first 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.

Quoted 15 lines

Quoted 14 lines

lib/string.c +8 -0

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

On 7/11/22 17:52, Yu-Jen Chang wrote:

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.

Quoted 36 lines

Andrey Semashev <[email protected]> 於 2022年7月11日 週一 凌晨4:01寫道：

Quoted 35 lines · Yu-Jen Chang

Quoted 33 lines

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 <[email protected]>

Signed-off-by Ching-Chun (Jim) Huang <[email protected]>

---
 lib/string.c | 28 +++++++++++++++++++++-------
 1 file changed, 21 insertions(+), 7 deletions(-)

lib/string.c +2 -2

index 80469e6c3..8ca965431 100644
@@ -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.
  *

Quoted 5 lines

Quoted 5 lines

lib/string.c EXPORT_SYMBOL(strnstr); · line 915

Quoted 5 lines

lib/string.c +1 -1

  * 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?

Quoted 20 lines

Quoted 11 lines

Quoted 11 lines

lib/string.c +5 -4

 {
-     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) {

Quoted 8 lines

lib/string.c EXPORT_SYMBOL(strnstr); · line 926

Quoted 5 lines

lib/string.c +5 -0

+             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?

Quoted 5 lines

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 first 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.

Quoted 16 lines

Quoted 16 lines

Quoted 15 lines

lib/string.c +8 -0

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

Andrey Semashev <[email protected]> 於 2022年7月11日 週一 晚上11:00寫道：

Quoted 3 lines · Yu-Jen Chang

Quoted 2 lines

Andrey Semashev <[email protected]> 於 2022年7月11日 週一 凌晨4:01寫道：

Quoted 1 line · Yu-Jen Chang

Quoted 12 lines

Quoted 11 lines

Quoted 5 lines

lib/string.c EXPORT_SYMBOL(strnstr); · line 926

Quoted 2 lines

lib/string.c +2 -0

+             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?

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 first 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.

Quoted 6 lines

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 = p + length;
    c &= 0xff;

    while ((long ) p & (sizeof(long) - 1)) {
        if (p >= end)
            return NULL;
        if (*(unsigned char *)p == c)

            return (void *) p;
        p++;
    }
    if (p <= end - 8) {
        mask = c;
        MEMCHR_MASK_GEN(mask);

        for (; p <= end - 8; p += 8) {

            val = *(u64*)p ^ mask;
            if ((val + 0xfefefefefefefeffull)
& (~val & 0x8080808080808080ull))
                break;
        }
    }

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

    return NULL;
}

Sent: 12 July 2022 15:59

Quoted 6 lines

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.

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

From: Yu-Jen Chang

Quoted 1 line

Sent: 12 July 2022 15:59

...

Quoted 8 lines

Quoted 6 lines

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.

That should be predicated on !HAS_EFFICIENT_UNALIGNED_ACCESS.

...

Quoted 5 lines

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

I would add a couple of comments, like:

	// Convert to check for zero byte.
	// Standard check for a zero byte in a word.

(But not the big 4 line explanation you had.

It is also worth looking at how that code compiles on 32bit arch that don't have a carry flag. That is everything based on MIPS, including riscv.

Quoted 21 lines · David Laight

From: Yu-Jen Chang

Quoted 1 line

Sent: 12 July 2022 15:59

...

Quoted 8 lines

Quoted 6 lines

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.

That should be predicated on !HAS_EFFICIENT_UNALIGNED_ACCESS.

...

Quoted 5 lines

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

Quoted 8 lines

I would add a couple of comments, like:

	// Convert to check for zero byte.
	// Standard check for a zero byte in a word.

(But not the big 4 line explanation you had.

It is also worth looking at how that code compiles on 32bit arch that don't have a carry flag. That is everything based on MIPS, including riscv.

It may be worth looking at how glibc does it:

https://sourceware.org/git/?p=glibc.git;a=blob;f=string/memchr.c;h=422bcd0cd646ea46711a57fa3cbdb8a3329fc302;hb=refs/heads/release/2.35/master#l46

They do use 32-bit words on 32-bit targets and 64-bit on 64-bit ones. I think memchr in the kernel should follow this.

Sent: 13 July 2022 11:03

Quoted 27 lines · Andrey Semashev

Quoted 26 lines · David Laight

From: Yu-Jen Chang

Quoted 1 line

Sent: 12 July 2022 15:59

...

Quoted 8 lines

Quoted 6 lines

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.

That should be predicated on !HAS_EFFICIENT_UNALIGNED_ACCESS.

...

Quoted 5 lines

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

I would add a couple of comments, like:

	// Convert to check for zero byte.
	// Standard check for a zero byte in a word.

(But not the big 4 line explanation you had.

Quoted 7 lines

Quoted 3 lines

It is also worth looking at how that code compiles on 32bit arch that don't have a carry flag. That is everything based on MIPS, including riscv.

It may be worth looking at how glibc does it:

https://sourceware.org/git/?p=glibc.git;a=blob;f=string/memchr.c;h=422bcd0cd646ea46711a57fa3cbdb8a3329
fc302;hb=refs/heads/release/2.35/master#l46

Quoted 3 lines

They do use 32-bit words on 32-bit targets and 64-bit on 64-bit ones. I think memchr in the kernel should follow this.

Also, if by chance this optimization is aimed for x86-64, it may be worth adding an arch-specific version that uses ERMS.

From: Andrey Semashev

Quoted 37 lines

Sent: 13 July 2022 11:03

Quoted 27 lines · Andrey Semashev

Quoted 26 lines · David Laight

From: Yu-Jen Chang

Quoted 1 line

Sent: 12 July 2022 15:59

...

Quoted 8 lines

Quoted 6 lines

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.

That should be predicated on !HAS_EFFICIENT_UNALIGNED_ACCESS.

...

Quoted 5 lines

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

I would add a couple of comments, like:

   // Convert to check for zero byte.
   // Standard check for a zero byte in a word.

(But not the big 4 line explanation you had.

Quoted 7 lines

Quoted 3 lines

It is also worth looking at how that code compiles on 32bit arch that don't have a carry flag. That is everything based on MIPS, including riscv.

It may be worth looking at how glibc does it:

Quoted 8 lines

https://sourceware.org/git/?p=glibc.git;a=blob;f=string/memchr.c;h=422bcd0cd646ea46711a57fa3cbdb8a3329
fc302;hb=refs/heads/release/2.35/master#l46

Quoted 3 lines

They do use 32-bit words on 32-bit targets and 64-bit on 64-bit ones. I think memchr in the kernel should follow this.

Also, if by chance this optimization is aimed for x86-64, it may be worth adding an arch-specific version that uses ERMS.

Don't believe everything you see in glibc.
The common cases in the kernel are different from the ones they tend to optimise for..

You might try using:

        #define GEN_MASK(x) (x * (unsigned long)0x0101010101010101ull)

for the mask and the two constants.
Then make all the variables 'long'.

I'm not at all sure what the test for fast multiply is about. It may be very historic, for modern cpu generating the 64bit constant is likely to be more problematic (check arm64). If the input value is 'unsigned char' (or masked) then the compiler may decide to do the repeated <<= itself.

David

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK Registration No: 1397386 (Wales)

Quoted 65 lines · Yu-Jen Chang

Quoted 63 lines · David Laight

From: Andrey Semashev

Quoted 37 lines

Sent: 13 July 2022 11:03

Quoted 27 lines · Andrey Semashev

Quoted 26 lines · David Laight

From: Yu-Jen Chang

Quoted 1 line

Sent: 12 July 2022 15:59

...

Quoted 8 lines

Quoted 6 lines

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.

That should be predicated on !HAS_EFFICIENT_UNALIGNED_ACCESS.

...

Quoted 5 lines

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

I would add a couple of comments, like:

   // Convert to check for zero byte.
   // Standard check for a zero byte in a word.

(But not the big 4 line explanation you had.

Quoted 7 lines

Quoted 3 lines

It is also worth looking at how that code compiles on 32bit arch that don't have a carry flag. That is everything based on MIPS, including riscv.

It may be worth looking at how glibc does it:

Quoted 8 lines

https://sourceware.org/git/?p=glibc.git;a=blob;f=string/memchr.c;h=422bcd0cd646ea46711a57fa3cbdb8a3329
fc302;hb=refs/heads/release/2.35/master#l46

Quoted 3 lines

They do use 32-bit words on 32-bit targets and 64-bit on 64-bit ones. I think memchr in the kernel should follow this.

Also, if by chance this optimization is aimed for x86-64, it may be worth adding an arch-specific version that uses ERMS.

Don't believe everything you see in glibc.
The common cases in the kernel are different from the ones they tend to optimise for..

You might try using:

        #define GEN_MASK(x) (x * (unsigned long)0x0101010101010101ull)

for the mask and the two constants.
Then make all the variables 'long'.

I'm not at all sure what the test for fast multiply is about. It may be very historic, for modern cpu generating the 64bit constant is likely to be more problematic (check arm64). If the input value is 'unsigned char' (or masked) then the compiler may decide to do the repeated <<= itself.

Quoted 8 lines

Quoted 5 lines

David

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK Registration No: 1397386 (Wales)

I have rewrite my code as the following. I use several macros

My gosh, have you checked what strscpy() does under the hood?

Why can’t you just reuse parts of it?

Quoted 68 lines

to
generate the mask and detect target char for 32-bit or 64-bit. The DETECT_CHAR macro is the same as this part:

(val + 0xfefefefefefefeffull) & (~val & 0x8080808080808080ull)

The 0xfefefefefefefeffull is the 2's complement of 0x0101010101010101ULL. I perform subtraction here exactly.

If the CPU architecture is unable to perform unaligned access efficiently, the pre-alignment loop will align the string at first.

#define LBLOCKSIZE (sizeof(long))
#if BITS_PER_LONG == 64

#define DETECT_CHAR(X) \
(((X) - 0x0101010101010101ULL) & ~(X) & 0x8080808080808080ULL)

#define MEMCHR_MASK_GEN(mask) \

do {                                                                   \
    (mask) |= (mask) << 8;                                         \
    (mask) |= (mask) << 16;                                        \
    (mask) |= (mask) << 32;                                        \
} while (0)

#else

#define DETECT_CHAR(X) (((X)-0x01010101UL) & ~(X)&0x80808080UL)

#define MEMCHR_MASK_GEN(mask) \

do {                                                                   \
    (mask) |= (mask) << 8;                                         \
    (mask) |= (mask) << 16;                                        \
} while (0)

#endif

void *memchr(const void *p, int c, size_t length)

{
    unsigned long mask, val;
    const void *end = p + length;
    c &= 0xff;
#ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS
    while ((long)p & (sizeof(long) - 1)) {
        if (p >= end)
            return NULL;
        if (*(unsigned char *)p == c)
            return (void *)p;
        p++;
    }
#endif
    if (p <= end - LBLOCKSIZE) {
        mask = c;
        MEMCHR_MASK_GEN(mask);

       for (; p <= end - LBLOCKSIZE; p += LBLOCKSIZE) {
              val = *(unsigned long *)p ^ mask;
              if (DETECT_CHAR(val))
                  break;
       }
    }

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

Quoted 2 lines

    return NULL;
}

--
With Best Regards,
Andy Shevchenko

From: Yu-Jen Chang

Quoted 1 line

Sent: 12 July 2022 15:59

...

Quoted 7 lines

Quoted 6 lines

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.

Quoted 1 line

Got it. I add pre-alignment loop. It aligns the address to 8 or 4bytes.

That should be predicated on !HAS_EFFICIENT_UNALIGNED_ACCESS.

This patche series optimized "memchr()" and add a macro for "memchr_inv()" so that both funtions can use it to generate bit mask.

The original implementaion of "memchr()" is based on byte-wise comparison, which do not fully use 64-bit or 32-bit register in CPU. We implement a word-wise comparison so that at least 4 bytes can be compared at the same time. The optimized "memchr()" is nearly 4x faster than the original one for long strings. In Linux Kernel, we find that the length of the string

searched by "memchr()" is up to 512 bytes in drivers/misc/lkdtm/heap.c. In our test, the optimized version is about 20% faster if the target character is at the end of the string when going through a 512-byte string.

Sent: 12 August 2022 20:07

Hi!

Quoted 3 lines

This patche series optimized "memchr()" and add a macro for "memchr_inv()" so that both funtions can use it to generate bit mask.

Quoted 5 lines

The original implementaion of "memchr()" is based on byte-wise comparison, which do not fully use 64-bit or 32-bit register in CPU. We implement a word-wise comparison so that at least 4 bytes can be compared at the same time. The optimized "memchr()" is nearly 4x faster than the original one for long strings. In Linux Kernel, we find that the length of the string

Well... how much slower is it for short strings?

Quoted 4 lines

searched by "memchr()" is up to 512 bytes in drivers/misc/lkdtm/heap.c. In our test, the optimized version is about 20% faster if the target character is at the end of the string when going through a 512-byte string.

"What is the average length passed to memchr" would be more useful question.

Best regards,
Pavel