hard for me

а там используется
пункт 6 в описании

optimiser

спасибо за участие!

автор1) test_integers: заменил в шараховской HybridSortSha_AII вызовы Compare на прямое сравнение (+ пара правок под integer) - и она обогнала вашу (немного)
рано или поздно нужно было это проверить
что круче: низкоуровневые оптимизации и алгоритмы
победили в очередной раз алгоритмы :)

автор2) вставил в test_integers код вашего шаблона и поставил "type T = integer" - скорость оказалась чуточку, но медленнее чем у QuickSortInteger (мелочь, а неприятно)
Это потому что сама функция универсальная
Чтобы скорость осталась прежней - нужно CMP_MODE выставить 1
Сейчас же копируется не интеджер, а массив байт - поэтому медленнее

автор3) еще по-мелочи: вы проверяли выигрыш самодельного "стека" по скорости? ведь при работе такого же решения, но с рекурсией, стек будет задействован на в точности ту же глубину - кстати, у вас она ограничена 64, а в системном явно больше
Проверять - не проверял. Но смысл в том, что в случае самодельного стека экономятся(оптимизируются) регистры, а так же снимаются накладные расходы на вызов функции - push/pop регистров в стек и call/ret. А что до глубины в 64 - так это явно с запасом :). На случай если в x64 приложении будет сортироваться массив байт размером 2^64 (я даже не знаю как такое число назвать) и при этом не будут использоваться сортировки вставками :)

авторз.ы. как ни странно, с test_strings таких проблем нет - измененный шаблон даже чуть быстрее, чем QuickSortString
это погрешности измерения
можешь сравнить код функций - должно быть идентично

автордо кучи:
- для несколькисекундных тестов разрешение GetTickCount маловато - QueryPerformanceCounter гораздо лучше
- перед тестом стоит сделать Randomize, чтобы на разных запусках были разные данные
(хотя может быть смысл и не делать этого)
я согласен, только времени было впритык
если внесёшь свою лепту - будет круто

Aleksandr Sharahovна E6850 (D7, InsCount=32 у всех алгоритмов) чуть быстрее те, что в статье:

QuickSort(String) test:
SmartQuickSort... 11581ms.
SmartQuickSortTemplate... 11533ms.
QuickSortSha_AII... 9689ms.
QuickSortSha_0AA... 9693ms.
QuickSortSha_A0I... 9691ms.
My DumbQuickSort... 10195ms.

Это неудивительно, т.к. это все это почти одинаковые алгоритмы.
Помоему результат отличный. Твои сортировки быстрее моей больше чем на 10%!
Не скажешь навскидку, в чём цимус? В трёх опорах? Я у себя побоялся их применять.

авторВ код особо не вникал, но замечу, что время измеряется довольно грязно:
включается копирование буфера, проверка правильности сортировки, перемежается с выводом - ужас.
Проверка корректности используется только в DEBUG
Копирование буфера... Я просто не знаю, как сделать лучше
Модернизируй пожалуйста тест и выложи сорсы

как может быть, что на одной конфигурации мой код работает быстрее, а на другой - Шарахова?
должен быстрее работать код Шарахова везде

Хотелось бы, чтобы Александр сравнил и сказал, почему у него быстрее на 10%
Есть ли простая модификация, после которой мой код обгонит его

asviridenkovТогда есть смысл посмотреть на код!

Ты раз такой любитель оптимизации, то обратил бы внимание на другой аспект.
У меня вот гораздо чаще возникают претензии к скорости поиска а не сортировки.
С появлением TDictionary стало получше, но все равно говорят что там до оптимальности очень далеко, особенно в
плане скорости работы хэш-функции.
Вот если бы ты написал что-то компилируемое во всей линейке XE2+ 32/64 всеплатформенное и работающее быстрее, было бы круто.

Представляю вашем вниманию альтернативную библиотеку шаблонов Rapid.Generics
https://github.com/d-mozulyov/Rapid.Generics

Бенчмарки сортировок, поисков и контейнеров привожу ниже. Бенчмарк по хеш-таблицам будет скорее всего на этой неделе, но в другой ветке.





P.S. Для оптимизации сортировок, небольшие части сортируются вставками. Для числовых предусмотрены так же поразрядные сортировки
P.P.S. Данные таблицы характерны для версий компилятора XE7+. На версиях ниже, производительность будет существенно отличаться