Rust-бенчмарк: unicase обгоняет ручную сортировку без регистра

Автор начал с реального рабочего кода: список строк сортировался через sort_by_cached_key с приведением каждой строки к нижнему регистру через to_lowercase(), метод один раз считает ключ для каждого элемента и кеширует его. Возник вопрос: не будет ли быстрее вариант без выделения памяти под копию строки, сравнивать регистронезависимо "на лету", через итераторы символов, ведь тогда операция приведения к нижнему регистру выполняется не n раз (по разу на элемент), а порядка log(n) раз на сравнение при сортировке.

Сделать это "на лету" в Rust оказалось не так просто. Сравнение двух строк без учёта регистра через итераторы требует пройтись по всем символам, для каждого вызвать char::to_lowercase (он возвращает итератор, а не один символ, потому что один символ иногда переходит в несколько символов в нижнем регистре) и склеить результат через flat_map. Дополнительная сложность: у Iterator есть метод cmp, но сам типаж Ord для итераторов не реализован, потому что cmp не идемпотентен, вызов исчерпывает итератор. Поэтому в sort_by пришлось перемежать приведение к нижнему регистру и сравнение прямо внутри замыкания.

Автор написал бенчмарк на фреймворке divan, сравнив три варианта: 1) sort_by_cached_key с to_lowercase() (с выделением памяти под кешированный ключ), 2) sort_by с посимвольным сравнением через char::to_lowercase() без выделения памяти, 3) sort_by через тип UniCase из стороннего крейта unicase. Данные, случайные имена, сгенерированные крейтом fake (локаль EN), для размеров списка 1, 5, 10, 100, 1000 и 10000 элементов; замеры сделаны на MacBook Pro с чипом M2-MAX, точность таймера, 41 наносекунда.

Результат по медианному времени: на 10000 элементах sort_by_cached_key показал 864,8 мкс, unicase, 1,757 мс (примерно вдвое медленнее кешированного варианта), а посимвольное сравнение через итераторы, 5,572 мс, то есть почти в 6,4 раза медленнее кешированного варианта и примерно в 3,2 раза медленнее unicase. На малых и средних размерах картина другая: на 10 элементах unicase дал 207,7 нс против 457,7 нс у кешированного варианта и 483,8 нс у итераторного, более чем вдвое быстрее обоих; на 100 элементах unicase (4,833 мкс) и кешированный вариант (5,291 мкс) шли почти вровень, а итераторный вариант (18,16 мкс) отставал почти в 3,8 раза. Единственное исключение в пользу итераторного метода, тривиальный случай с одним элементом, где ему не приходится ничего кешировать.

Вывод автора: если элемент в списке не один, sort_by_cached_key почти всегда оправдан, а посимвольное сравнение через итераторы систематически медленнее, чем ожидалось, несмотря на отсутствие выделения памяти. Отдельным сюрпризом для автора стало то, что crate unicase на части размеров обгоняет оба самодельных варианта, хотя логика сравнения в нём сложнее, почему именно так, автор не объясняет, отмечая это как открытый вопрос.

Ключевые факты

Сравнивались три способа регистронезависимой сортировки строк в Rust: sort_by_cached_key с to_lowercase(), sort_by с посимвольным сравнением через итераторы char::to_lowercase(), и sort_by через сторонний крейт unicase (тип UniCase)
Бенчмарк на фреймворке divan прогнан на MacBook Pro M2-MAX для списков от 1 до 10000 случайных имён (крейт fake, локаль EN); точность таймера, 41 нс
На 10000 элементах медианное время: 864,8 мкс у кешированного варианта против 5,572 мс у посимвольного сравнения (почти в 6,4 раза медленнее) и 1,757 мс у unicase
На малых и средних размерах (5, 100 элементов) unicase зачастую быстрее обоих собственных вариантов, несмотря на более сложную логику сравнения, на 10 элементах у него 207,7 нс против 457,7 нс и 483,8 нс у конкурентов
Единственное исключение, список из одного элемента: там быстрее посимвольный вариант, потому что кешировать ключ не требуется

Почему это важно

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

Кому это важно

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

Как это применить

Для сортировки заметного числа строк без учёта регистра, использовать sort_by_cached_key с to_lowercase(), а не собирать сравнение вручную через итераторы. Если критичны и малые списки, стоит опробовать крейт unicase: на размерах в единицы-сотни элементов он в приведённых замерах обгонял оба самодельных варианта, хотя на 1000+ элементах уступал кешированному ключу.

Можно ли доверять

Методология прозрачная: код бенчмарка приведён целиком, использован специализированный фреймворк для бенчмарков (divan), измерения повторены на разных размерах входа. Ограничения, о которых источник умалчивает: не указаны дата публикации и версии использованных крейтов (divan, fake, unicase), а имя автора поста в самом тексте не названо. Причина, почему unicase оказался быстрее при более сложном сравнении, самим автором не объяснена.

Риски и подводные камни

Результат получен на одной машине (Apple M2-MAX) с одним набором случайных строк одной длины и одной локали, на другом железе, других длинах строк или другом алфавите соотношение времени между тремя вариантами может быть другим. Выводы о превосходстве unicase на малых размерах и кешированного ключа на больших не стоит переносить на произвольные данные без собственной проверки.

«Unicase часто оказывается быстрее, несмотря на более сложное сравнение.»

— автор поста