Quick sort работает в c# почему-то быстрее, чем в с++. Разве не должно быть наоборот?

Question

[Espleth]

Написал qsort на с++ и точно такой же код на c#. В итоге один и тот же код на с++ работает в несколько раз медленнее, чем на c#. К примеру на с++ сортирует миллион элементов за секунды 1.5 (это с указателями, а если использовать векторы так вообще секунд 6), а на c# примерно за 0.5 сек. Почему так, ведь с++ должен работать быстрее, чем c#? Обе сортировки написаны в VS 13. Если надо скину код.

Answer 1

[Trrrrr]

Во первых убедитесь, что вы скомпилировали в с++ в релизе.
Во вторых покажите ваш код на с++, я уверен, что смогу очень быстро показать вам что у вас тормозит и как минимум получить одинаковую скорость.

Comments

[Espleth]

Как уже написал, компилил в дебаге, однако в релизе c# по прежнему быстрее с++ работает. Вот исходники https://drive.google.com/file/d/0B4GhpKcqpvU7T015a...

[Trrrrr]

@Espleth сейчас изучу

[Trrrrr]

@Espleth да код вполне нормальный, кроме пары моментов с кодстайлом, но то лично мои предрасудки. Конечно можно убрать статик и еще руками прописать __forceinline. у меня результат что в шарпе что в с++ с вашим кодом получился одинаковый, в обоих случаях в среднем 5.5 секунд что для меня в данном случае звучит логично. Какой то глупости откровенной нет (не считая что с начала билдили в дебаге :)) есди ващу строяку qSort заменить на std::sort(arr, arr + length); то у меня вышло почти в 4 раза быстрее за 1.5 секунд.

[Espleth]

@Trrrrr Ну насчет качества кода я уверен, что он так себе, что и отражается во времени работы по сравнению с библиотечным qsort (там, конечно, еще наверняка вместо 0го элемента массива для перестановки выбирался какой-нибудь средний, ускоряя работу, плюс еще куча других оптимизаций, но мне и без этого возни с кодом хватило). Странно, что у Вас получается одинаковое время работы моего алгоритма на с++ и на c#, потому что у меня на с++ работает столько же, сколько и у вас, а вот на c# секунды за 2-3 справляется. А я просто ожидал, что c# будет раза в 2 дольше работать, поэтому и удивился. И если использовать в с# List arr, то arr.Sort(); будет тоже 20кк элементов секунды 2-3 считать.

[lookid]

@Espleth МОЕГО АЛГОРИТМА. Что еще себе присвоите?

[Espleth]

@lookid Хорошо. Моей реализации всем известного алгоритма. Это как бы очевидно. Довольны?

[lookid]

@Espleth реализация это когда вы берете черновую теорью и по ней пишите с вашими идеями. А тут просто копипаста. Возможно даже из википедии.

[Espleth]

@lookid Даже спорить не хочется. Ну если я ее скопировал откуда-то, то уж не поленитесь, поищите откуда. А то пока только голословные обвинения. Да и я вообще не хвастаться кодом сюда пришел, а спросить про скорость работы. Это так, если вы не заметили.

[becks]

@lookid, отстаньте от человека со своей ерундой.

[Trrrrr]

@Espleth вообще, с учетом алгоритма должно быть от одинаково то до с# изза дополнительных рантайм проверок. Ускорить с++ код можно даже в таком виде, но и код сам поменяется. В таком виде как сейчас чисто арифметические операции, странно было б если б современный JIT компилятор шарпа не смог бы с таким разобраться. единственное, что я юзал 2012ую студию. Возможно там компилятор в вашей студии умеет какое нибудь многопоточное распаралеливание или еще чего, что не умеет в с++.

[Espleth]

@Trrrrr Возможно вы правы. Спасибо за ответы.

[AxisPod]

Вообще дело в том, что JIT компилятор довольно оптимальный код может давать, даже уж очень оптимальный и вполе такое возможно, надо просто посидеть в дебаге и поглядеть на дизасм обоих версий.

Answer 2

[lookid]

Вы размеры смотрели файлов? C# получился в разы меньше? Вы уверены, что не выкрутили оптимизацию на полную? Или VS для C# не выкрутила сама? С++ же не для детей и дибилов по 18 лет. Расчет идет на то, что разработчик сам знает всё и сам всё настроит. Выкрутите /O3 и прочее. Или скомпилируйте в g++ с -O3. Существуют релизы разной степени дебажности. Скомпилировали на дефолтных настройках и паникуете, как-будто систему свергли. Если вы что-то узнали, то это не значит, что этого никто не знает. Конфиги, флаги? Где это всё?

Answer 3

[Alex Chistyakov]

Почему C++ должен работать быстрее, чем C#?
Как минимум, у C# эффективнее аллокатор, когда ему нужно выделить память, он просто сдвигает указатель занятой памяти выше по хипу.
Если элементов всего миллион, и они целочисленные, то до GC дело даже и не дошло ни разу.

Comments

[Trrrrr]

Причем здесь аллокатор. К сожалению вы ошибаетесь. Есть куча алгоритмов сортировки, тот же inplace. Скорее всего автор реализовал кривой алгоритм и все. один и тот же код может тормозить на одном языке и не тормозить на другом.

[Alex Chistyakov]

@Trrrrr А в каком именно утверждении я ошибаюсь? В том, что у C# аллокатор эффективнее - ну, докажите, что это не так. А больше я ничего и не утверждал, я спросил, почему это C++ должен быть быстрее.

[Trrrrr]

@alexclear предпосылка не верная. Человек написал что то и это что то у него вышло в одном языке быстрее в другом медленнее. Это все что мы знаем. Мы даже не знаем догадался ли он в релизе собрать С++ код. А аллокаторы в с++ можно использовать свои, если окажется что код тормозит из за памяти. В чем я в данный момент сомневаюсь.

[Alex Chistyakov]

@Trrrrr Мой пойнт был не в том, что у человека тормозит аллокатор. А в том, что причины, по которым C++ должен быть быстрее C# совершенно не очевидны. Как пример я привел различие в алгоритмах работы стандартного аллокатора C# и стандартного же аллокатора C++, ни слова не говоря ни и чем другом.

[Trrrrr]

@alexclear Но я все же ставлю на дебаг режим в этом случае, стдшный вектор никак не тормозит по сравнению с указателями в релизе. А вот в дебаге добавляется куча проверок.

[Espleth]

@Trrrrr Вот исходники https://drive.google.com/file/d/0B4GhpKcqpvU7T015a... . Код, не сомневаюсь, кривой, однако на обоих языках он практически не отличается.
Каюсь, в дебаге собирал. Не знал, что в релизе все работает быстрее. Но протестил в релизе: на массиве 20кк элементов 2-3 секунды с# против секунд 5 с++.

[AxisPod]

@alexclear а вы думаете, что в C++ другой аллокатор?

[Alex Chistyakov]

@AxisPod Другой в сравнении с чем? В сравнении с C#? Я не думаю, я знаю, что он другой.

[Alex Chistyakov]

@AxisPod Задам встречный вопрос - а Вы что думаете, они там одинаковые, что ли? И что C# на каждое выделение памяти дергает стандартный malloc()?

Answer 4

[StrangeAttractor]

Не должно. Доподлинно известно, что есть вещи, которые работают на Java быстрее, чем на C++ или C (особенно если запрограммированы "втупую", без хитроумных ручных оптимизаций и хаков на основе учёта никоуровневых особенностей машины), а на Scala - ещё быстрее. C# данном контексте, можно сказать, та же Java/Scala. Я даже не удивлюсь, если найдутся задачи, в производительности которых будет лидировать, к примеру, PHP.

Comments

[Alex Chistyakov]

Вот если PHP будет лидировать в CPU-bound задачах, я крайне удивлюсь. Там такое количество добра вокруг данных и вызовов методов обернуто, что лидировать он не может ни при каких условиях.

Answer 5

[Александр Таратин]

А если с библиотечным сравнить?
www.cplusplus.com/reference/cstdlib/qsort

Comments

[Trrrrr]

Я сравнил. Библиотечный std::sort работает за 1.5 секна моем компе, против 5.5 кода автора на 20кк рандомных значений