Case insensitive search performance

Сегодня оптимизировал одно из узких мест в проекте: case insensetive поиск подстроки в строке - то есть не различая регистр.

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

Провел сравнение скорости разных способов проверки вхождения подстроки в строку.
За единицу скорости принял std::wstring::find() - она хотя не делает того, что нужно (не регистро-независимая), но в качестве эталона скорости - самое оно. Тестировал в VC++ 7.1 release mode с включенной оптимизацией по скорости.

Аналог std::wstring::find() из буста - boost::find_first() - оказался в 2,5 раза медленнее эталона.

Та функция из буста, которая делает то, что мне нужно - boost::ifind_first() - в 70 раз медленнее эталона. В коде проекта как раз она и использовалась - отсюда и дикие тормоза.

Первая моя вариация была такой: делаем копии строк, затем применяем к ним boost::to_upper(), затем - std::wstring::find(). Результат - в 51 раз медленнее эталона. Но это уже заметно быстрее boost::ifind_first().

Следующая версия - создание глобальной таблицы wchar_t ToUpper[0x10000], содержащая для каждого символа его upper case варианта. Используя эту таблицу внутри предиката для функции boost::first_finder(), получил версию, всего в 2 раза медленнее эталона!

При нежелании тратить 128Kb на подобную таблицу, ее можно сократить до 2Kb, просчитывая только ее начало и используя подобным образом: (c <= 0x451) ? ToUpper[c] : std::toupper(c, loc). В таком случае скорость получилась в 5 раз медленнее эталона.

Выбрана была последняя версия с буфером 2Kb, куда влезает вся латиница и кириллица. Дальнейшая оптимизация свелась к тому, что искомая подстрока переводилась в upper case всего один раз, а ToUpper[] применялась только к строкам в которых шел поиск. Этот финт, правда, почти не сказался на скорости.