Оптимизируем бинарный поиск - Сергей Слотин
ฝัง
- เผยแพร่เมื่อ 6 ต.ค. 2024
- Доклады об ускорении условных баз данных на 5−10% большинству людей не интересны: да, это то, за что программистам платят, но эти оптимизации обычно слишком сложные и специфичные, чтобы их можно было сразу применить где-нибудь еще.
Другое дело - оптимизация базовых алгоритмов из учебников - тех, которые кажутся настолько простыми, что пытаться ускорять их даже в голову не придет. Такие оптимизации, как правило, просты, поучительны, многократны и, на удивление, не так редки, как многие думают.
В этом докладе мы сосредоточимся на одном из таких фундаментальных алгоритмов - бинарном поиске. Рассмотрим ряд способов ускорить его с помощью branchless-программирования, оптимизации доступов к памяти и использования SIMD-инструкций и постепенно выведем алгоритм до 15 раз быстрее std::lower_bound. - วิทยาศาสตร์และเทคโนโลยี
легендарное видео, спасибо, чтобы всё понять - уверен буду пересматривать и в этом месяце и через пару лет. хочется еще об "оптимизации" в С++ по алгоритмам и "как лучше писать код на С++, чтобы ассемблерование было эффективнее"
Спасибо! В видео так много упомянуто интересных тем для изучения, а ведь казалось бы - простой классический алгоритм...
Прекрасный доклад! Спасибо!
О как. Интуитивно стараюсь избегать if бестолковых. Вместо for лучше while использовать. А оно вон почему. Спасибо за инфу!
Грустно, что это красиво лишь на бенчмарках. Проверил вплоть до B-деревьев (не включая их) тесты под msvc. На бенчмарках ускорение в 3-4 раза есть, но prefetch чаще ухудшает результат. И как только я вывел код в полезную нагрузку, то к великому сожалению stl показывает себя лучше в 2.5 раза:) Поиск был правда по double, а не int. А последние алгоритмы с Eygzinger'ом и B-tree не совсем соответствуют stl, так как возвращать всё-таки хочется итератор (приходится моделировать мат. распределение), из-за чего в Eygzinger BS приходится лишний массивчик с прежними индексами заводить. В общем грустно всё это
Крутой доклад.
Про вопрос с внедрением в стандарт не понял только: почему нельзя использовать оба алгоритма, используя более лучший в зависимости от ширины поиска на конкретном шаге?
@bydlokoder доклад ведёт 👍😂