Почему стандартные строковые функции быстрее, чем мои собственные строковые функции?

Ответ 1

if(xstrlen(str1)!=xstrlen(str2))    //computing length of str1
    return -1;                      
k=xstrlen(str1)-1;                  //computing length of str1 AGAIN!

Вы вычисляете длину str1 TWICE. Это одна из причин, по которой ваша функция теряет игру.

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

Ответ 2

strcmp и другие библиотечные процедуры написаны в сборке или специализированном C-коде опытных инженеров и используют различные методы.

Например, реализация сборки может одновременно загружать четыре байта в регистр и сравнивать этот регистр (как 32-разрядное целое число) с четырьмя байтами от другой строки. На некоторых машинах реализация сборки может загружать восемь байтов или даже больше. Если сравнение показывает, что байты равны, реализация переходит к следующим четырем байтам. Если сравнение показывает, что байты не равны, реализация прекращается.

Даже при такой простой оптимизации существует ряд проблем. Если строковые адреса не кратны четырем байтам, у процессора может не быть инструкции, которая будет загружать четыре байта (для многих процессоров требуется четырехбайтовые нагрузки для использования адресов, которые выровнены по кратным четырем байтам). В зависимости от процессора для реализации, возможно, потребуется использовать медленные неодинаковые нагрузки или написать специальный код для каждого случая выравнивания, который выравнивает нагрузки и сдвигает байты в регистрах для выравнивания байтов, которые нужно сравнить.

Когда реализация загружает сразу четыре байта, она должна гарантировать, что она не загружает байты за конечный нулевой символ, если эти байты могут вызвать ошибку сегмента (ошибка, потому что вы пытались загрузить адрес, который не читается).

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

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

Ответ 3

Более быстрая реализация strlen:

//Return difference in addresses - 1 as we don't count null terminator in strlen.
int xstrlen(char *str)
{
    char* ptr = str;
    while (*str++);
    return str - ptr - 1;
}

//Pretty nifty strcmp from here:
//http://vijayinterviewquestions.blogspot.com/2007/07/implement-strcmpstr1-str2-function.html
int mystrcmp(const char *s1, const char *s2)
{
    while (*s1==*s2)
    {
        if(*s1=='\0')
            return(0);
        ++s1;
        ++s2;
    }
    return(*s1-*s2);
}

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

Ответ 4

Помимо проблем в вашем коде (которые уже указывались), - по крайней мере, в gcc-C-libs, функции str - и mem быстрее с шагом в большинстве случаев, потому что их шаблоны доступа к памяти оптимизированы.

Уже было несколько обсуждений по теме на SO.

Ответ 5

Попробуйте это:

int xstrlen(const char* s){
  const char* s0 = s;
  while(*s) s++;
  return(s - s0);
}

int xstrcmp(const char* a, const char* b){
  while(*a && *a==*b){a++; b++;}
  return *a - *b;
}

Вероятно, это можно ускорить, развернув цикл.

Ответ 6

1. Алгоритм

У вашей реализации strcmp может быть лучший алгоритм. Не должно быть необходимости вызывать strlen вообще, каждый вызов strlen будет снова итерации по всей длине строки. Вы можете найти простые, но эффективные реализации онлайн, вероятно, место для начала - это что-то вроде:

// Adapted from http://vijayinterviewquestions.blogspot.co.uk
int xstrcmp(const char *s1, const char *s2)
{
  for (;*s1==*s2;++s1,++s2)
  {
    if(*s1=='\0') return(0);
  }
  return(*s1-*s2);
}

Это не все, но должно быть простым и работать в большинстве случаев.

2. Оптимизация компилятора

Это глупый вопрос, но убедитесь, что вы включили все переключатели оптимизации при компиляции.

3. Более сложные оптимизации

Люди, которые пишут библиотеки, часто будут использовать более сложные методы, такие как загрузка четырехбайтового или 8-байтового int сразу и сравнение его, и только сравнение отдельных байтов, если все совпадает. Вам нужно быть экспертом, чтобы знать, что подходит для этого случая, но вы можете найти людей, которые обсуждают наиболее эффективную реализацию при переполнении стека (ссылка?)

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

4. Linker "обманывает" со стандартной библиотекой

С некоторыми стандартными библиотечными функциями компоновщик может заставить вашу программу вызывать их с меньшими накладными расходами, чем функции вызова в вашем коде, потому что он был разработан, чтобы больше узнать о конкретных внутренних функциях функций (ссылка?) Я не знаю, Знаю, если это применимо в этом случае, вероятно, это не так, но это то, о чем вы должны думать.

5. ОК, ладно, я получаю это, но когда СЛЕДУЕТ реализовать собственный strcmp?

Сверху моей головы, единственные причины для этого:

• Вы хотите узнать, как это сделать. Это хорошая причина.
• Вы пишете для платформы, которая не имеет достаточно хорошей стандартной библиотеки. Это очень маловероятно.
• Сравнение строк было значительным узким местом в вашем коде, и вы знаете что-то конкретное о своих строках, что означает, что вы можете сравнивать их более эффективно, чем наивный алгоритм. (Например, все строки выделены 8-байт выровнены, или все строки имеют N-байтовый префикс.) Это очень, очень маловероятно.

6. Но...

ОК, ПОЧЕМУ вы хотите избежать полагаться на strlen? Вы беспокоитесь о размере кода? О переносимости кода или исполняемых файлов?

Если есть веская причина, откройте другой вопрос, и может возникнуть более конкретный ответ. Поэтому я сожалею, если мне не хватает чего-то очевидного, но полагаться на стандартную библиотеку, как правило, намного лучше, если только что-то конкретное вы не хотите улучшить.