strstr быстрее алгоритмов?

Question

У меня есть файл размером 21056 байт.

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

Я использовал все реализации алгоритмов со страницы «Точные алгоритмы сопоставления строк» ​​. Я использовал: KMP, BM, TBM и Horspool. А потом я использовал strstr и оценил каждый из них.

Что мне интересно, так это то, что каждый раз strstr превосходит все остальные алгоритмы. Единственный, кто быстрее, иногда это BM.

Разве strstr не должен быть самым медленным?

Вот мой код теста с примером тестирования BM:

double get_time()
{
    LARGE_INTEGER t, f;
    QueryPerformanceCounter(&t);
    QueryPerformanceFrequency(&f);
    return (double)t.QuadPart/(double)f.QuadPart;
}

before = get_time();
BM(token, strlen(token), buffer, len);
after = get_time();
printf("Time: %f\n\n", after - before);

Может ли кто-нибудь объяснить мне, почему strstr превосходит другие алгоритмы поиска? При необходимости я выложу больше кода по запросу.

Answer 1

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

(Причина, по-моему, состоит в том, что программисты любят реализовывать такие вещи.)

Answer 2

Horspool, KMP и др. Оптимальны для минимизации количества сравнений байтов.

Однако это не узкое место на современном процессоре. На процессоре x86 / 64 ваша строка загружается в кэш L1 кусками ширины строки кэша (обычно 64 байта). Независимо от того, насколько умный ваш алгоритм, если он не дает вам больше шагов, вы ничего не получите; и более сложный код Horspool (по крайней мере, один просмотр таблицы) не может конкурировать.

Кроме того, вы застряли со строковым ограничением "C" нулевого завершения: КУДА-ТО, где код должен проверять каждый байт.

strstr(), как ожидается, будет оптимальным для широкого диапазона случаев; например поиск крошечных строк, таких как "\r\n", в короткой строке, а также гораздо более длинных строк, в которых есть надежда на более умный алгоритм. Базовый цикл strchr / memcmp довольно сложно превзойти по всему диапазону возможных входных данных.

Практически все x86-совместимые процессоры с 2003 года поддерживают SSE2. Если вы разобрали strlen() / x86 для glibc , вы могли заметить, что он использует некоторые операции SSE2 PCMPEQ и MOVMASK для поиска нулевого терминатора 16 байт за раз. Решение настолько эффективно, что превосходит очевидный супер-простой цикл, для чего-либо длиннее пустой строки.

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

• Конвергенция SSE2 и strstr()

• лучше strstr() без кода ASM

  Если вы хотите увидеть решение, отличное от SSE2, которое доминирует в strstr() для целевых строк длиной более 15 байтов, проверьте:

  , который использует многобайтовые сравнения вместо strchr(), чтобы найти точку, в которой нужно выполнить memcmp.

Кстати, вы, наверное, уже поняли, что операции x86 REP SCASB / REP CMPSB выпадают на задницу дольше, чем 32 байта, и не намного лучше для более коротких строк. Хотелось бы, чтобы Intel уделил этому немного больше внимания, чем добавлению SSE4.2 "string" ops.

Для достаточно больших струн мои тесты показывают, что BNDM лучше, чем Horspool, по всем направлениям. BNDM более терпим к «патологическим» случаям, таким как цели, которые сильно повторяют последний байт шаблона. BNDM также может использовать SSE2 (128-битные регистры) таким образом, чтобы конкурировать с 32-битными регистрами по эффективности и стоимости запуска. Исходный код здесь .

Answer 3

Не видя ваш код, сложно сказать точно.strstr сильно оптимизирован и обычно написан на ассемблере.Он делает такие вещи, как чтение данных по 4 байта за раз и сравнение их (если нужно, битовое перемешивание, если выравнивание не правильное), чтобы минимизировать задержку памяти.Он также может использовать такие вещи, как SSE для загрузки 16 байтов за раз.Если ваш код загружает только один байт за раз, он, вероятно, погибает из-за задержки памяти.

Используйте отладчик и выполните разборку strstr - вы, вероятно, найдете там несколько интересных вещей..

Answer 4

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

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