Оптимизация в Коде, связанном со строковыми функциями

Это не даст никакой оптимизации, потому что именно это и делает strcmp().

В целом, так как функции str...() используются настолько интенсивно, что можно положиться на разработчиков библиотек, реализующих их максимально эффективно. Только после того, как вы написали свой собственный код, использующий эти функции, обнаружили проблему и отследили ее с помощью USING A PROFILER, следует подумать о написании замен.

Беспокойство по поводу того, что strcmp() в большинстве случаев является микрооптимизацией - не стоит усилий. Есть и другие вещи, которые могут быть более разнообразными, например:

for (i = 0; i < strlen(s); i++)
{
     ...do stuff with s[i]...
}

Оптимизатор может и не осознавать, что он может и должен избегать вызова функции при каждой итерации цикла - если в цикле выполнить инкремент s, то он может и не избежать этого. Это дорого.

Однажды очень давно я использовал такую функцию как strstr() на буферах размером 20 КБ или около того, и программа отлично работала на коробке HP, где я ее разрабатывал. Я портировал ее обратно на машину Sun (помните, это было 20 лет назад - проблемы давно исправлены), а программа даже не ползла - она была практически стационарной. Проблема оказалась циклом в strstr(), в котором более или менее использовалась strlen(), как показано выше. При использовании на коротких буферах не было большой проблемы; при использовании на 20 килобайтных буферах, при поиске закономерности, которая появлялась через каждые пару килобайт, бедная машина останавливалась. Проблема была показана путем профилирования приложения. Я подключил суррогат strcat(), который позволил избежать ошибки и все вернулось на круги своя.

Другим распространенным источником медлительности при избытке является использование strcat(). Например:

strcpy(dst, name);
strcat(dst, "/subdir/");
strcat(dst, file);
strcat(dst, ".sfx");

Обычно это не является фактическим источником проблем с производительностью - но при отсутствии доказательств обратного это может быть источником переполнения буфера. Необходимо знать, что длины достаточно малы, чтобы уместиться в dst. Но, если вы знаете длины каждого бита (как вы должны быть уверены, что они поместятся), вы можете написать вместо этого:

strcpy(dst, name);
dst += len_name;
strcpy(dst, "/subdir/");
dst += sizeof("/subdir/") - 1;
strcpy(dst, file);
dst += len_file;
strcpy(dst, ".sfx");

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

Керниган и Пайк рассказывают интересную историю о том, как улучшить производительность спам-фильтра в книге 'The Practice of Programming'. Она начала использовать strstr() в цикле; в итоге получилась совсем другая конструкция, потому что обстоятельства, для которых была спроектирована strstr(), не соответствовали требованиям их системы фильтрации спама. Но, опять же, они выполнили эту работу только потому, что было продемонстрировано наличие проблемы с производительностью, и они проделали достаточную работу, чтобы программа не стала узким местом в системе, но не более того.

Может быть познавательно изучать glibc реализацию strlen:

• Нет проверки NULL аргументов (даже утверждений)
• Строки сравниваются байт-байт до тех пор, пока не достигнут длиннофокусного адреса. После этого все сравнения производятся в 4- или 8-байтных кусках.
• Нет никакой векторизации или архитектурно-специфического материала (т.е. нет #ifdefs).
• Коварная часть при сравнении 4 или 8 байт за раз - выяснить, какой байт был нулем при неудачном сравнении.

Вас может заинтересовать эта статья (автор Джоэл Спольский). Речь идет о функциях низкого уровня (в частности, C string) и о том, как они оптимизируются.

Джонатан абсолютно прав, особенно пример strlen(s), который я нашел (в чужом коде :-) с помощью одного выстрела из стека.

Вы говорите о микрооптимизации, о которой стоит беспокоиться ПОСЛЕ того, как в противном случае настроил блейз из кода. Сравнение первого символа перед вызовом strcmp действительно экономит некоторое время из-за накладных расходов на вход/выход из функции, но мое эмпирическое правило заключается в том, что это стоит делать только в том случае, если вызов strcmp стоит более 10%.

<sarcasm>

В отличие от других ответов, о вашем утверждении:

Например, сколько оптимизации даст сравнение первого символа двух строк (и проверка их равенства) перед вызовом strcmp?

Я думаю, что это отличная идея. Итак, мы должны сделать это:

int compstr(const char *a, const char *b)
{
   if (*a == *b) return strcmp(a+1, b+1);
   else return *(unsigned char *)a < *(unsigned char *)b ? -1 : 1;
}

Но зачем останавливаться на этом? Мы должны проверить еще один символ, давая нам лучшую оптимизацию:

int compstr(const char *a, const char *b)
{
    size_t i;
    for (i=0; *a == *b && i < 2; ++a, ++b, ++i)
        if (*a == 0)
            return 0;
    if (i == 2) return strcmp(a, b);
    return *(unsigned char *)a < *(unsigned char *)b ? -1 : 1;
}

Конечно, мы можем сделать намного лучше. Давайте сделаем количество символов для сравнения параметром:

/* Really fast implementation to compare strings,
   takes the optimization parameter n_comp */
int compstr(const char *a, const char *b, size_t n_comp)
{
    int i;
    for (i=0; *a == *b && i < n_comp; ++a, ++b, ++i)
        if (*a == 0)
            return 0;
    if (i == n_comp) return strcmp(a, b);
    return *(unsigned char *)a < *(unsigned char *)b ? -1 : 1;
}

Но если мы хотим сравнить первые несколько символов, почему бы нам не сделать все это самим? Итак, вот финальная, полностью оптимизированная версия:

/* Final, highly optimized function to compare strings */
int strcmp (const char *a, const char *b)
{
    for (; *a == *b; ++a, ++b)
        if (*a == 0)
            return 0;
    return *(unsigned char *)a < *(unsigned char *)b ? -1 : 1;
}

После написания нашей версии, мы рады обнаружить, что она идентична версии в P.J. Plauger's The Standard C Library (и, конечно же, она избегает любых архитектурных оптимизаций, которые использовала бы хорошая библиотека)!

</sarcasm>

Другими словами, как говорили другие, нет смысла в преждевременной оптимизации.

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

Стандартная строка c-runtime string довольно сильно оптимизирована. Маловероятно, что вы сможете его улучшить, кроме как используя знания о вашей проблемной области, которых не может иметь c-runtime.

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

Но Вы делаете сравнение строк, которые совпадают, еще более дорогостоящим!

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

Единственный мой общий совет: не используйте strcat . Конечно, это быстро и просто, но чем больше вы его используете, тем дороже он становится. Лучше следить за концом строки и strcpy до конца.

Стандартная библиотека на Си очень оптимизирована. А некоторые компиляторы встраивают функции CRT, так что вы экономите на накладных расходах на инструкцию вызова. Однако, если вам все-таки нужно больше скорости, есть несколько вариантов. Если вы зайдёте по этой ссылке, то сможете скачать программу, которая насчитывает несколько strcmp-процедур, написанных программистами на языке ассемблера.

http://www.masm32.com/board/index.php?topic=2508.0

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

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

Вот результаты, которые они получают при сравнении строки abcdefg с abcz

lstrcmp - original (from Microsoft) : 19314 clocks; Return value: 1
lstrcmp - kunt0r  : 957 clocks; Return value: 24832
lstrcmp - Lingo   : 501 clocks; Return value: 1

Как видно по количеству часов (меньше - лучше), остальные функции работают намного быстрее.

Есть ли какие-нибудь рекомендации, которым можно следовать перед вызовом стандартных строковых функций на C?

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

В конце концов, если у вас есть доказательства того, что ваше приложение слишком медленное, вы можете профилировать и посмотреть, имеют ли строковые функции какое-либо отношение к вашей проблеме. И если улучшение скорее будет происходить из подлинейного алгоритма вроде Бойер-Мура, чем путем подстройки strcmp.

Два правила оптимизации Майкла А. Джексона:

1. Не делайте этого.

2. (Только для экспертов) Пока не делайте этого.

Я считаю, что важно то, что каждый репозиторий / база данных, связанный со строкой, может иметь свои собственные характеристики, которые могут быть манипулируют или используют для создания ваших оптимальных функций строковых операций. Однако в этом посте есть несколько простых приемов для некоторых случаев - вы можете выбрать то, что соответствует вашим потребностям, и использовать его: http : //www.codemaestro.com/articles/21