Код на тестах летит, а в проде тормозит, и вы уже не первый раз смотрите на профайлер? Причина не всегда в алгоритме: CPU пытается угадать, куда пойдёт выполнение по
if.Дэниел Лемайр собрал бенчмарк, который мерит ёмкость предсказателя ветвлений. Цикл пишет число в буфер, если оно нечётное. Случайные данные дают промах за промахом. Повторяющийся паттерн CPU запоминает и летит.
Разные чипы, разный лимит. AMD Zen 5 держит около 30 000 ветвлений, Apple M4 тянет 10 000, Intel Emerald Rapids укладывается в 5 000. Разброс в шесть раз.
Мне кажется, главная ценность здесь не в цифрах, а в угле. Ветвление — не бесплатная операция, а ресурс с лимитом. Если ваш прод ведёт себя не как тесты, причина может быть именно здесь. Разбор и код Лемайра: погоняйте на своём железе и проверьте, угадает ли ваш процессор.