?

Log in

No account? Create an account

August 7th, 2019

std::sort против qsort

Есть странная фишка в Visual Studio C++ (в данном конкретном случае - в 2015-й).

Есть STL-евская функция std::sort.
На вход она принимает предикат, то есть функцию, которая возвращает bool, если a < b.
Есть STD C функция qsort.
На вход она принимает функцию, которая возвращает int: -1, если a < b, +1, если a > b и 0, если a == b.

Первая функция возвращает меньше информации, поэтому естественно было бы предположить, что её придется вызывать чаще. А значит, если сравнение само по себе долгое и сложное (как например сравнение строк), тогда qsort должен быть быстрее.

Эксперимент же показывает, что std::sort работает быстрее qsort (естественно, в релизе и с одинаковой оптимизацией).

Гуру программирования объясняют, дескать, все дело в том, что в STL сравнения инлайнятся. Хрен там.

Я написал тестик, в котором один и тот же массив сортировался с использованием вызова по указателю на функцию strcmp, то есть никакого инлайна не должно было быть. К тому же сама strcmp - непростая, и затраты на её вызов должны быть пренебрежимо малы по сравнению с затратами на исполнение тела.

И что же? На 100 тыс. элементов std::sort все равно сортировал строки вдвое быстрее, чем qsort: 15 мс против 32 мс. При этом по каким-то загадочным причинам время от времени получалось вдруг 15 против 16, а потом опять разница вдвое.

На 500 тыс. элементов std::sort тоже оказался быстрее, стабильно показывая цифры вроде 78 против 125.

А что насчет количества вызовов? Поставил я счетчики и внезапно оказалось, что std::sort вызывает функцию сравнения меньшее количество раз - ненамного, но все-таки. То есть теория насчет того, что std::sort придется вызывать сложные сравнения чаще, тоже не работала.

Проверка в отладчике показала, что std::sort и qsort вроде бы не ведут к общему коду, то есть реализованы по-разному. Хотя, казалось бы, напрашивается использование общего кода. Возникает подозрение, что STL функцию когда-то оптимизировали, а STD C функцию не стали трогать.