Фильтрация среза чисел по порогу — типичная задача. В Rust её обычно пишут через filter() и collect(), но на случайных данных такой код ведёт себя странно. Для миллиона f64 от 0.0 до 100.0 замеры через criterion дают: при 1% оставленных элементов — 0.59 мс, при 50% — 3.94 мс, а при 99% — 1.49 мс. Копирование почти вдвое большего объёма данных оказывается в 2.6 раза быстрее.
Первое подозрение — реаллокации Vec. Предвыделение через Vec::with_capacity(input.len()) улучшает результат на 50% лишь до 3.87 мс. Дело не в аллокациях, а в процессоре.
Современный CPU выполняет инструкции конвейерно и предсказывает направление веток. Если предсказание неверно, конвейер сбрасывается — это 15–20 циклов на x86, тогда как само сравнение стоит около одного цикла. При 1% данных предсказатель почти всегда угадывает «пропустить», при 99% — «сохранить», а при 50% случайных данных он угадывает как монетка. Полмиллиона сбросов дают около 2 мс штрафа.
Проверка: если отсортировать тот же вход, время 50% падает с 4.15 мс до 0.93 мс — в 4.5 раза. В отсортированных данных сначала идут «skip», потом «keep», и предсказатель быстро обучается. Известный эффект, про него есть вопрос на Stack Overflow с 27 тысячами апвоутов.
Решение — branchless programming. Элемент пишется всегда, а результат сравнения двигает курсор: out[n] = x; n += (x > threshold) as usize; затем truncate(n). Сравнение используется как число 0 или 1, а не как развилка. В ассемблере это инструкция seta. Непредсказуемая ветка исчезает.
Результаты branchless-версии: 1% — 1.09 мс, 25% — 1.05 мс, 50% — 1.03 мс, 75% — 1.02 мс, 99% — 1.11 мс. Худший случай ускорился почти в 4 раза, время почти не зависит от данных. Но лучший случай стал хуже: при 1% обычная версия быстрее, потому что почти всегда правильно предсказанная ветка почти бесплатна, а branchless всегда делает миллион записей.
Вывод: ветка дешёвая, непредсказуемая — нет. Branchless подходит только для горячих путей, где профайлер показал ветвление на случайных данных. Код сложнее читать, компиляторы и так много оптимизируют, так что без замеров применять его не стоит.