Есть ли способ сделать мою функцию для проверки равенства строк еще быстрее?

Question

Я хочу научиться писать более быстрый код на C, поэтому я написал и постоянно оптимизирую функцию, которая проверяет равенство двух строк.

int stringsequal(register char *s1, register char *s2)
{
    do
    {
        if(!(*s1 ^ 0)) return 1;
    }
    while(!(*(s1 ++) ^ *(s2 ++)));
    return 0;
}

РЕДАКТИРОВАТЬ: Благодаря вашим отзывам я улучшил свой код! Вот мой новый код:

int stringsequal(register char *s1, register char *s2)
{
    while(1)
    {
        if(!((*s1 + *s2) ^ 0)) return 1;
        if(*(s1 ++) ^ *(s2 ++)) break;
    }
    return 0;
}

РЕДАКТИРОВАТЬ: Если бы я мог удалить этот вопрос, я бы извиняюсь за тратить ваше время на всех.

Answer 1

Ваша первая функция просто не работает и неверна.

Вы не правильно указали типы параметров. Не используйте register, так как это никак не влияет. Регистр игнорируется на любом уровне оптимизации. Компиляторы лучше меня или вас в микрооптимизации, поэтому помогите оптимизатору компилятора с const и restrict, если применимо.

Второй можно упростить.

int stringsequal1(const char *restrict s1, const char *restrict s2)
{
    do
    {
        if(*s1 != *s2) return 0;
    }
    while(*s1++ + *s2++);
    return 1;
}

и код результата для обоих:

int stringsequal1(const char *s1, const char *s2)
{
    do
    {
        if(*s1 != *s2) return 0;
    }
    while(*s1++ + *s2++);
    return 1;
}

stringsequal1:
        xor     edx, edx
        jmp     .L11
.L15:
        add     rdx, 1
        add     eax, eax
        je      .L14
.L11:
        movsx   eax, BYTE PTR [rdi+rdx]
        cmp     al, BYTE PTR [rsi+rdx]
        je      .L15
        mov     eax, 1
        ret
.L14:
        ret

int stringsequal2(register char *s1, register char *s2)
{
    while(1)
    {
        if(!((*s1 + *s2) ^ 0)) return 1;
        if(*(s1 ++) ^ *(s2 ++)) break;
    }
    return 0;
}

stringsequal2:
        xor     eax, eax
        jmp     .L18
.L22:
        add     rax, 1
        cmp     cl, r9b
        jne     .L21
.L18:
        movsx   r8d, BYTE PTR [rdi+rax]
        movsx   r9d, BYTE PTR [rsi+rax]
        mov     ecx, r8d
        add     r8d, r9d
        jne     .L22
        mov     eax, 1
        ret
.L21:
        xor     eax, eax
        ret

Answer 2

Можно ли как-нибудь ускорить выполнение функции проверки равенства строк?

Чем быстрее, тем лучше, но нет, если он ломается функционально. Остальной код может как будет

// Faster but wrong functionally
int stringsequal0(register char *s1, register char *s2) {
  return 0;
}

Оба из OP strcequal() функционально несовершенны. Первые сообщают strequal("", any_string) как равные, а вторые сообщают как равные каждый раз, когда char s добавляют к 0. (Рассмотрим char в одной строке с отрицательным значением).

Быстрее: Да. Вместо того, чтобы вызывать свой собственный для strequal(), либо вызовите стандартную библиотечную функцию strcmp(), либо посмотрите код модели после одной из ее реализаций.

Концептуально, в цикле необходимо только сравнение *s1 == *s2 и *s1 == 0. *s2 == 0 - это , а не , необходимое в цикле.

inline /* or don't inline */ int strequal1(const char *a, const char *b) {
  return strcmp(a,b)==0;
}

int strequal2(const char *s1, const char *s2) {
  while (*s1 && *s1 == *s2) {
    s1++;
    s2++;
  }
  return *s1 == *s2;
}

В конце концов, только профилирование будет определять, что "быстрее". Напомним, один подход может быть быстрее с небольшими и маловероятными математическими строками, в то время как другой подход может работать лучше с длинными строками, которые редко отличаются.

Компиляторы умны и хитры. Оптимизирующие компиляторы могут анализировать код и заменять вызовы, такие как strcmp(s, "abc")==0, для сравнения с 4 байтами. Обратите внимание, что компиляторы могут «обманывать» и выполнять действия, на которые не может положиться обычный код C. Компилятор может не понимать ваш strequal(), чтобы воспользоваться аналогичными преимуществами.

Я сомневаюсь очень OP может вывести решение, которое значительно превосходит strcmp() с длинными похожими строками.

Answer 3

Я думаю, что вы текущий код, не выполняет функции strcmp. Петля

 while(!(*(str1 ++) ^ *(str2 ++))); 

ничего не делает.

Strcmp возвращает целое число меньше, равно или больше нуля, если найдено, что str1 меньше, соответствует или больше str2.

ваш метод возвращает 1 или ноль и не соответствует спецификации strcmp.

Кроме того, я думаю, что strcmp уже оптимизирован. использование memcmp не даст лучшей производительности, если вам сначала нужно знать длину str1 и str2. поэтому вам нужно будет передать все строковые символы для строк str1 и str2.

здесь реализация glibc.

int STRCMP (const char *p1, const char *p2)
{
  const unsigned char *s1 = (const unsigned char *) p1;
  const unsigned char *s2 = (const unsigned char *) p2;
  unsigned char c1, c2;

  do
    {
      c1 = (unsigned char) *s1++;
      c2 = (unsigned char) *s2++;
      if (c1 == '\0')
        return c1 - c2;
    }
  while (c1 == c2);

  return c1 - c2;
}