Quicksort без branch mispredictions: обогнал std::sort и pdqsort на C

Помните ту самую лекцию про branch prediction, где процессор предсказывает, пойдёте вы налево или направо, и ошибается? Оказывается, можно не заставлять его гадать.

Некий энтузиаст реализовал branch-avoidant quicksort на чистом C. Его сортировка не просто быстрее std::sort из STL, но и обходит легендарный pdqsort (который, напомним, используется в Rust, а раньше был в libc++). Секрет в том, чтобы заменить условные переходы на вычислительные трюки — процессор перестаёт спотыкаться на каждой развилке.

Конечно, код выглядит как заклинание на ассемблере с привкусом C. Но работает — на случайных данных прирост до 30%, на почти отсортированных — тоже неплохо. Правда, автор честно признаётся: на некоторых паттернах (например, много одинаковых элементов) выигрыш меньше, а на очень маленьких массивах лучше оставить старый добрый insertion sort.

Комментарий студии METABYTE: Мы тоже любим, когда код работает быстро, но если ваш проект уже использует std::sort, менять его на самописный quicksort — как замена колесам на болиде Формулы-1 на квадратные. Хотя для embedded-систем или игровых движков — почему бы и нет? Главное, чтобы CI не сломался.