Как в glibc 🤗

Очень интересно, и каким же образом это делается с учётом что ожидается некоторая универсальность для разных архитектур

$ grep -R "e __HAVE_ARCH_MEMCHR" *
arch/powerpc/include/asm/string.h:#define __HAVE_ARCH_MEMCHR
arch/s390/include/asm/string.h:#define __HAVE_ARCH_MEMCHR /* inline & arch function */
arch/arm/include/asm/string.h:#define __HAVE_ARCH_MEMCHR
arch/alpha/include/asm/string.h:#define __HAVE_ARCH_MEMCHR
arch/x86/include/asm/string_32.h:#define __HAVE_ARCH_MEMCHR
arch/arm64/include/asm/string.h:#define __HAVE_ARCH_MEMCHR
arch/sh/include/asm/string_32.h:#define __HAVE_ARCH_MEMCHR

Это же не реклама, зачем употребтять "до"? Тем более, что в оригинале написано "около" - "around ~4x".

В 4 раза - что планируем получить...

> В ядре Linux размер обрабатываемых в memchr() строк достигает 512 байт. Прирост производительности для 512 байтовых строк, в ситуации, когда искомый символ находится в конце строки, составляет 20%.

Максимум 20% - мягко сказать, уже далеко не в 4 раза.

> Общий прирост производительности подсистем ядра при использовании оптимизированного варианта "memchr()" пока не оценивался

В реальности - 0.0X%, что даже постыдились показать.

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

if (strlen(s) == 5) --> if (strnlen(s, 6) == 5)

Это не сильно актуально при малых строках строках, а при огромных - выигрыш существенен. Тем не менее второй вариант кода - большая редкость.

uname -a
Linux 5.18.10-200.fc36.x86_64 #1 SMP PREEMPT_DYNAMIC Thu Jul 7 17:21:38 UTC 2022 x86_64 x86_64 x86_64 GNU/Linux

#include <stdio.h>
#include <stdlib.h>
#include <linux/types.h>
#include <string.h>
#include <ctype.h>
#include <time.h>
#include <sys/time.h>

#define A_SZ 1024*1024

unsigned char str[A_SZ] = { '\0' };

long long tv = 0;

unsigned long long _rdtsc()
{
union ts {
unsigned long long tx;
struct dword {
long tl, th;
} dw;
} t;

asm("rdtsc\n":"=a"(t.dw.tl), "=d"(t.dw.th));
return t.tx;
}

void gen_array()
{
int i, c;
srand(time(NULL));

for (i = 0; i < A_SZ;) {
c = rand() % 255;
if (!isprint(c))
continue;
str[i] = c;
i++;
}
printf("ARRAY SIZE: %d\n", i);
}

#define MEMCHR_MASK_GEN(mask) (mask *= 0x0101010101010101ULL)

void *new_memchr(const void *p, int c, size_t length)
{
__u64 mask, val;
const void *end = p + length;

c &= 0xff;

/* write(1, "strchr\n", 7); */

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

int main()
{
unsigned char ch;
char *ret = NULL;
int count = 0;

gen_array();

/* glibc */
tv = _rdtsc();
for (ch = 0x20; ch < 0x7E; ch++)
ret = memchr(str, ch, A_SZ);
printf("LIB: %lld\n", _rdtsc() - tv);

/* new */
tv = _rdtsc();
for (ch = 0x20; ch < 0x7E; ch++)
ret = new_memchr(str, ch, A_SZ);
printf("NEW: %lld\n", _rdtsc() - tv);

return (0);
}