32 vs 64: Assembler

Все ж мне стало любопытно, почему 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), у быстрой коэффициент вроде как меньше, если не брать вырожденные случаи.

Второй тест: 32 vs 64

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

Пришла пора проверить мои предположения тестом.

Вот его результаты:

Сортировка 32 не опт. 64 не опт. Выигрыш, разы 32 опт. 64 опт. Выигрыш, разы Эффект опт., 32 разы Эффект отп, 64, разы Прямым включением (50 тыс.) 4.92 3.71 1.33 1.20 1.66 0.73 4.09 2.24 Шейкерная (50 тыс.) 8.44 6.85 1.23 2.80 2.97 0.94 3.01 2.30 Быстрая наихудший (50 тыс.) 2.69 2.69 1.00 0.62 0.75 0.82 4.35 3.58 Пирамидальная (20 млн.) 3.56 3.87 0.92 2.17 2.75 0.79 1.65 1.41 Быстрая (20 млн.) 3.16 3.35 0.94 1.84 2.02 0.91 1.72 1.66

Сортируются массивы 32-битных целых чисел, размер массивов для каждого случае приведен в скобках. Ну и он совпадает с тем, что привел Иван Колесников в комментарии к предыдущему посту, чисто для сравнения.

Выводы: мое предположение совершенно не оправдалось.  То есть пропускная способность между процессором и кэшем вполне достаточна для вдвое более длинных указателей в 64-битной архитектуре.

А все дело в более низком качестве 64-битного компилятора по сравнению с 32-битным, по крайней мере в Delphi XE5.

Интересные факты:

1. Без оптимизации на Дельфи 64-битный код выполняется быстрее 32-битного. После оптимизации все меняется с точностью до наоборот.
2. Даже в наихудшем случае быстрая сортировка (напомню, сложность у нее порядка O(n^2)) работает все же быстрее простых методов сортировки с такой же оценкой сложности. Правда, для простых методов был взят наихудший случай, когда данные отсортированы в обратном порядке.
3. Простые методы сортировки оптимизируются гораздо более эффективно, чем сложные.
4. При этом наихудший вариант быстрой сортировки, когда в качестве опорного всегда выбирается первый элемент сортируемой части массива, показал такое же улучшение в результате оптимизации, как и простые методы. Не говорит ли это о том, что такой вариант быстрой сортировки может быть легко приведен к более простому варианту?

Грусть-печаль короче. Попробовать ради смеха на ассемблере под 64 бита что ли быструю сортировку накидать? )))

32 vs 64: что дальше?

Напомню, в своей предыдущей записи я сделал предположение, что в том конкретном случае 64-битная архитектура проигрывает из-за в 2 раза большего объема обращений к памяти: к куче и к стеку.

На самом деле, проверить, на мой взгляд, достаточно просто. Но, перед тем, как проверять, хочется немного пованговать и проверить, угадаю я или нет.

Проверить мои предположения можно выполнив какой-то алгоритм, который не использует динамическую память и много вызовов процедур. Не особо напрягая голову, я решил, что проще всего это сделать на простейших алгоритмах сортировки. Их преимущество состоит еще и в том, что они очень медленные, поэтому временная оценка будет достаточно точной. Итак, я планирую провести следующие эксперименты:

1. Сортировка простым включением. Проста, как три копейки. Переменных нужно не много, пишется двумя циклами без вызовов процедур. Поэтому вангую, что 32-битный и 64-битный вариант покажут одинаковую скорость работы, +- 5%.

2. Из простых сортировок самая сложная - это шейкерная. Вот где можно развернуться оптимизирующему компилятору с 16 регистрами общего назначения. Вызовов процедур нет. Вангую, что здесь должен победить 64-битный вариант.

3. Ради интереса посмотрим, как работают улучшенные варианты сортировки. Пирамидальная сортировка характеризуется весьма хаотичным обращение к памяти, а также относительной сложностью алгоритма. Вызовов процедур немного. Вангую примерный раритет между платформами.

4. Быстрая сортировка. Достаточно сложный вариант алгоритма, есть где поработать оптимизатору. Но очень много рекурсивных вызовов. Вот тут и можно проверить, влияет ли большое количество регистров, и, соответственно, большое количество операций обращения к памяти стека при вызове процедур, на производительность. Вангую, что 64 бита здесь продуют. Единственная проблема, как сформировать исходные данные так, что бы сортировка выполнялась медленнее всего, а глубина стека была наибольшей.

Первый тест: 32 vs 64

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

Краткая предыстория. Когда давно я с сыном соревновался, смогу ли я написать сжатие Хаффманом лучше, чем он. Хотя детали уже не помню, может все было совсем не так. Недавно просматривая свой старый код, решил портировать его под 64 бита и немного оптимизировать.

Вот что получилось (время операции указано в секундах, программа компилировалась на Delphi XE5):

Операция	32 bit	64 bit	Потери производительности
Сжатие	0.62	0.92	47.02%
Восстановление	2.81	4.30	53.16%
Замедление	4.515512	4.704038

В последней строчке показано, во сколько раз распаковка данных медленней, чем сжатие. Просто для информации. Сжимался 8-битный файл изображения в формате tif размером 57 Мбайт, после сжатия размер файла составил 46 Мбайт. В данном случае тестировалась именно сама операция сжатия, без учета построения дерева Хаффмана.

Как видите 64-битная архитектура для данного примера оказалась существенно медленнее. Почему так? На мой взгляд, причина именно в лимитировании скорости работы памяти. И дело тут не только в использовании ссылок, но и  в вызове процедур или функций. Каждый такой вызов приводит как минимум к двум обращениям к памяти, а обычно существенно больше.

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

Кстати, еще один интересный момент: много регистров - тоже палка о двух концах. Ведь при вызове процедуры использованные регистры надо сохранить в стеке, а потом восстановить их обратно. И чем больше регистров, тем больше издержки на вызов функции.

На самом деле причины в низкой производительности могут быть и другие, выше я привел только свои предположения. Как думаете вы, с чем связаны такие результаты 64-битного кода?

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

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

Так что не нужно думать, что 64-битная программа будет быстрее 32-битной. Понятно, что у 64-разрядного процессора есть много разных преимуществ, но только реализуются они не так уж и часто. Это задачи, обрабатывающие очень большие объемы данных, более 4 Гбайт, а также вычисления с большой точностью, например, шифрация данных. В обыденной жизни такие задачи встречаются не так уж и часто.

Еще один интересный момент в этом небольшом исследовании связан с тем, что распаковка происходит медленнее, чем сжатие. Происходит это потому, что при распаковке заранее не известно, сколькими битами закодирован символ, поэтому считывать данные приходится побитно. При сжатии же код символа известен заранее и записывается он в выходной поток одной операцией.