Все ж мне стало любопытно, почему 64-битный код работает медленнее 32-битного. Уже было ясно, что дело в компиляторе, потому что тесты Ивана на С++ показали, что 64-битный режим работает быстрее 32-битного.
Ведь нельзя сказать, что компилятор дельфи совсем нечего не делает. Потому что оптимизированный 64-битный код все же работает быстрее не оптимизированного. Просмотр в режиме отладчика тоже никаких явных корявостей не обнаружил. Поэтому я решил вспомнить, что такое ассемблер и переписал быструю сортировку вручную.
Стало немного быстрее, но 32-битный код я так и не догнал. Переписал 32-битный вариант и понял, что я что-то делаю не так, потому что мой ассемблерный 32-битный код оказался медленнее кода на дельфи.
Начал смотреть, что делает компилятор. И понял, что давным-давно регистровая оптимизация для x86 и x64 не очень актуальна. Благодаря теневым регистрам и предсказанию ветвления. Это вам не RISC. А я-то как раз пытался все в регистры перенести. Еще один момент связан с заполнение конвейера, но сюда я уже не стал глубоко залазить.
Короче, добился, что бы мой 32-битный ассемблерный код работал почти также быстро, как и скомпилированный. Но перенос его на 64 бита оказался все равно медленнее 32-битного.
Как выяснилось, дело здесь в том, что я обрабатывал 32-битные данные в 64-битных регистрах. Исходя из предположения, что на современных процессорах что 32-битная, что 64-битная регистровая операция производится примерно с одинаковой скоростью. По всей видимости, из того же предположения исходили и разработчики компилятора. :)
Так вот, это не так. Как только я начал работать с половинками 64-битный регистров, я сразу догнал по производительности 32-битный код.
Можно было, наверное, даже обогнать 32-битный код, более полно заполняя конвейер или улучшив работу предсказателя переходов (честно говоря, не понял, что тут будет работать). Для этого надо немного по-другому организовать выполнение циклов. Но выигрыш там небольшой, а мне лениво было.
В попытках разобраться даже Вадима Иванович немного напряг. У меня дома амдшный процессор, было любопытно посмотреть, как будет работать интеловский. В общем, я не ожидал особых отличий.
Но, тем не менее, результат немного меня удивил. Процессоры вообще-то разные и работают на разной частоте, поэтому прямого сравнения делать нельзя. Дело тут в нюансах.
Если 32-разрядный код интеловский процессор выполняет существенно быстрее амдшного, то 64-разрядный только чуть-чуть быстрее или чуть-чуть медленнее (в зависимости от алгоритма).
Чем проще сортировка, тем больше преимущество у интеловского процессора.
Еще одна удивительная особенность - пирамидальная сортировка на интеловском работает быстрее быстрой, а на амдшном - наоборот. Причем отличие достаточно значительное. Не знаю, с чем это связано, но, вроде как, хоть оба алгоритма и имеют одинаковую сложность n*log(n), у быстрой коэффициент вроде как меньше, если не брать вырожденные случаи.
Ведь нельзя сказать, что компилятор дельфи совсем нечего не делает. Потому что оптимизированный 64-битный код все же работает быстрее не оптимизированного. Просмотр в режиме отладчика тоже никаких явных корявостей не обнаружил. Поэтому я решил вспомнить, что такое ассемблер и переписал быструю сортировку вручную.
Стало немного быстрее, но 32-битный код я так и не догнал. Переписал 32-битный вариант и понял, что я что-то делаю не так, потому что мой ассемблерный 32-битный код оказался медленнее кода на дельфи.
Начал смотреть, что делает компилятор. И понял, что давным-давно регистровая оптимизация для x86 и x64 не очень актуальна. Благодаря теневым регистрам и предсказанию ветвления. Это вам не RISC. А я-то как раз пытался все в регистры перенести. Еще один момент связан с заполнение конвейера, но сюда я уже не стал глубоко залазить.
Короче, добился, что бы мой 32-битный ассемблерный код работал почти также быстро, как и скомпилированный. Но перенос его на 64 бита оказался все равно медленнее 32-битного.
Как выяснилось, дело здесь в том, что я обрабатывал 32-битные данные в 64-битных регистрах. Исходя из предположения, что на современных процессорах что 32-битная, что 64-битная регистровая операция производится примерно с одинаковой скоростью. По всей видимости, из того же предположения исходили и разработчики компилятора. :)
Так вот, это не так. Как только я начал работать с половинками 64-битный регистров, я сразу догнал по производительности 32-битный код.
Можно было, наверное, даже обогнать 32-битный код, более полно заполняя конвейер или улучшив работу предсказателя переходов (честно говоря, не понял, что тут будет работать). Для этого надо немного по-другому организовать выполнение циклов. Но выигрыш там небольшой, а мне лениво было.
В попытках разобраться даже Вадима Иванович немного напряг. У меня дома амдшный процессор, было любопытно посмотреть, как будет работать интеловский. В общем, я не ожидал особых отличий.
Но, тем не менее, результат немного меня удивил. Процессоры вообще-то разные и работают на разной частоте, поэтому прямого сравнения делать нельзя. Дело тут в нюансах.
Если 32-разрядный код интеловский процессор выполняет существенно быстрее амдшного, то 64-разрядный только чуть-чуть быстрее или чуть-чуть медленнее (в зависимости от алгоритма).
Чем проще сортировка, тем больше преимущество у интеловского процессора.
Еще одна удивительная особенность - пирамидальная сортировка на интеловском работает быстрее быстрой, а на амдшном - наоборот. Причем отличие достаточно значительное. Не знаю, с чем это связано, но, вроде как, хоть оба алгоритма и имеют одинаковую сложность n*log(n), у быстрой коэффициент вроде как меньше, если не брать вырожденные случаи.
Сравнил сгенерированный ассемблер для моей qsort. Я не большой знаток ассемблера, но как я понял:
ОтветитьУдалить1. 64-bit код почти не использует стек, в 32-bit коде достаточно много перемещений со стека, на стек.
2. 64-bit в основном использует "половинки" 64-bit регистров.
3. В обоих случаях компилятор развернул второй (хвостовой) рекурсивный вызов.
4. В 32-bit компилятору пришлось больше данных положить на стек перед рекурсивным вызовом, в 64-bit - всего один регистр (похоже компилятор правильно заиспользовал регистры, чтобы избежать их сохранения/восстановления)
5. В целом код вроде практически одинаковый, отличия в мелочах...
1. Это несколько странно, хотя, наверное, сильно зависит от процессора. На своем я установил четкую зависимость. Выгоднее использовать MOV, чем PUSH\POP. Работа со стека сильнее загружает процессор. Поэтому в дельфи при необходимости регистры сохраняются в локальных переменных с помощью MOV.
УдалитьОчень активно пользуются операциями память-регистр, которые современными процессорами выполняются очень быстро (естественное, если память кэшировна).
2. Вот да, если бы использовали полный, то наверняка проиграли бы 32-битному коду.
3. Вот это круто. Молодцы ребята, ничего не скажешь.
4. В дельфи вообще ничего не ложили практически. Стандартно выделили память под локальные переменные и две операции MOV в локальные переменные, что бы освободить регистры.
1. Моя ошибка, там действительно move используются в память по фиксированному смещению от адреса в esp, а я думал это и есть положить, достать из стека (esp ведь :))). Совсем я не знаю ассемблер.
УдалитьДа на прикладном уровне сейчас ассемблер вообще никому не нужен. ))) Производительность такая у современных процессоров, что на обычные задачи хватает с избытком.
УдалитьЭто я уж так балуюсь, привычка с детства осталась. )))