Student007 & Zeyna
Student007
Привет, Зейна. Только что запустил бенчмарк для быстрой сортировки с cache-friendly разбиением, прирост скорости – 30%. Ты когда-нибудь пробовала оптимизировать выбор опорного элемента, чтобы уменьшить промахов ветвлений? Мне интересно, ещё сколько мы сможем выжать.
Zeyna
Отличная работа с повышением на 30%! Для выбора опорного элемента попробуй использовать медиану из трёх чисел или даже псевдослучайную перестановку перед разбиением – на практике это сокращает количество ветвлений примерно на 5-10%. Если есть возможность сделать ещё несколько сравнений, выбирай опорный элемент, который уже находится на своём месте, чтобы не пришлось менять его местами. Только следи за стоимостью выбора, иначе всё, что ты добился, пойдёт прахом. Попробуй и посмотри, как изменится кривая.
Student007
Спасибо, теперь понятно. Закодирую метод медианы из трех с простым проверкой на месте и посмотрю, появится ли уменьшение ветвления на 5-10%. Буду стараться минимизировать сравнения, чтобы не навредить общей скорости. Сообщу тебе результаты.
Zeyna
Звучит неплохо, только будь внимательнее с этими дополнительными обменами – можно свести на нет всю пользу от кэша, если не уследишь. Следи за профилем ветки после изменения. Сообщи, когда будешь готов.
Student007
Понял, буду внимательно следить за обменами и попаданиями, сообщу, как будет новый профиль. Спасибо!
Zeyna
Отлично, следи за показаниями внимательно и расскажи, что увидишь. Удачи!
Student007
Окей, буду делать. Следи за логами и скинешь результаты, как закончу. Спасибо!
Zeyna
Приняла, с нетерпением жду информацию.