оптимизация поиска строки для одного байта

В общем, алгоритмы поиска строк (например, Бойера-Мура) оптимизированы для случаев, когда строка поиска это долго. То есть Бойер-Мур великолепен, потому что, выровняв строку поиска с нашим текстом, мы можем пропустить N = len(search string) символы, если конец строки поиска не совпадает с текстом.

Но что, если наша строка поиска действительно короткая? Как один байт или символ? В этом случае Бойер-Мур мало помогает.

Итак, каковы некоторые альтернативные алгоритмы для ускорения поиска?

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

Я хотел бы знать, как на самом деле работает этот оптимизированный поиск строки / байта. Как же тогда работает реальное сравнение? Я знаю, что это, очевидно, должно включать битовую маскировку — но я не понимаю, как выполнение битовой маскировки лучше, чем просто поиск по символам.

Итак, предположим, что наш поисковый символ 0xFF, Не обращая внимания на проблемы с выравниванием, допустим, у нас есть некоторый буфер ввода: void* buf, Мы можем прочитать это слово за словом, сказав:

const unsigned char search_char = 0xFF;
unsigned char* bufptr = static_cast<unsigned char*>(buf);
unsigned char* bufend = bufptr + BUF_SIZE;

while (bufptr != bufend)
{
// Ignore alignment concerns for now, assume BUF_SIZE % sizeof(uintptr_t) == 0
//
std::uinptr_t next_word = *reinterpret_cast<std::uintptr_t*>(bufptr);

// ... but how do we compare next_word with our search char?

bufptr += sizeof(std::uintptr_t);
}

Я также понимаю, что приведенный выше код не является строго переносимым, потому что std::uintptr_t не гарантированно будет размер слова. Но давайте предположим ради этого вопроса, что std::uinptr_t равен размеру слова процессора. (Реальной реализации, вероятно, потребуются макросы для конкретной платформы, чтобы получить фактический размер слова)

Итак, как мы можем на самом деле проверить, если байт 0xFF происходит где-нибудь в значении next_word?

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