?

Log in

No account? Create an account

Previous Entry | Next Entry

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 функцию не стали трогать.

Comments

( 10 comments — Leave a comment )
thedeemon
Aug. 7th, 2019 11:28 am (UTC)
Банально алгоритмы разные.

А время чем меряли-то? А то похоже на использование таймера низкого разрешения, в винде как раз один его тик около 15 мс. Надо QueryPerformanceCounter брать.
psilogic
Aug. 7th, 2019 11:34 am (UTC)
Да, возможно. Это объяснило бы случайные скачки между 15 и 30 мс.
theiced
Aug. 7th, 2019 04:50 pm (UTC)
разные алгоритмы очевидно. например std::sort переходит на инсершн при определённых размерах чанка. сортировка достаточно сложная тема же.
psilogic
Aug. 7th, 2019 05:41 pm (UTC)
В данном случае возникает закономерный вопрос - зачем делать одельный qsort, если его простейшая реализация через std::sort оказывается быстрее.
thedeemon
Aug. 8th, 2019 09:54 am (UTC)
Дык qsort сишный, для тех, у кого С++ харам.
bsivko
Aug. 8th, 2019 09:46 pm (UTC)
У quick sort рандомный выбор pivot, потому время обработки может быть разное.

Разница в 2 раза на одном железе несущественна. Реализация может немного просадиться на чём угодно - от особенностей компилятора до промаха в кэше.
psilogic
Aug. 8th, 2019 10:18 pm (UTC)
При чем тут рандомный выбор точки, если массив один и тот же сортируется?
bsivko
Aug. 9th, 2019 12:08 am (UTC)
Массив один и тот же, а pivot рандомный. Если pivot удачен, то время сокращается. Более ценные с точки зрения удачи pivot'ы в начале сортировки.

Т.е. если вначале 100 тыс. элементов, и pivot попал в самый малый элемент, то на втором заходе будет 100 000 минус 1 элемент, как будто массив никто не сортировал, а ~100 000 операций сравнения потрачено.Если pivot идеален, то он разобьет на две части по 50к и работы уже в 2 раза меньше.

В среднем попадание pivot'a разбивает массив на 1/sqrt(2) частей что ли. Если делается сортировка слиянием, то она делит всегда пополам, т:е: на равные части. Но она требует больше памяти, потому рабочей лошадкой берут quicksort. У него средняя ассимтотическая сложность такая же (n log n), но немногим медленнее (в k раз, где k константа, и на это уже обычно не обращают внимания).

Edited at 2019-08-09 12:10 am (UTC)
psilogic
Aug. 9th, 2019 06:46 am (UTC)
Выше вроде как выяснили, что рандомность связана с 15 мс погрешностью таймера - на границу попало.
bsivko
Aug. 9th, 2019 01:58 pm (UTC)
Да, скорее всего основной вклад от этого. Но это не отменяет рандомности quicksort
( 10 comments — Leave a comment )

Profile

ioda
psilogic
Мирослав Войнаровский
Психологика

Latest Month

September 2019
S M T W T F S
1234567
891011121314
15161718192021
22232425262728
2930     
Powered by LiveJournal.com
Designed by yoksel