Итак, накидал тут намеднясь первую версию теста с заменой указателей на индексы в массиве. Что бы избавиться от длинных операций с памятью, заменив их вычислением адреса. Надо сказать, что 16 РОН тут решают, без них вся затея не стоила бы выделки.
В итоге получилось, что одна операция чтения из памяти 8 байт заменяется на чтение 2 байт, одно 32-битное умножение и сложение.
И вот здесь возникло у меня сомнение. А точно ли второе быстрее первого? Решил проверить. Чисто на паскале это вообще не так, с указателями работает гораздо быстрее. А вот на ассемблере все не так однозначно.
Код на указателях почти всегда чуть быстрее кода на индексах, малоуловимо, чуть выше погрешности измерения.
С памятью, конечно, ситуация не в пользу указателей. Если использовать указатели, то в худшем случае (СЛАУ из 3-х переменных типа float32) на хранение коэффициентов можно использовать 60% памяти, 40% уйдет на указатели. В случае же использования индексов можно под коэффициенты использовать не менее 83% памяти.
Так что даже не знаю, какой вариант выбрать. Как думаете?
Из любопытного. Для работы с массивами часто используется индексная адресация, вычисляемая как сумма базы и смещения, масштабированного на размер элемента данных. Но при последовательной обработке строк можно было бы ограничиться только базой, так как следующий элемент находится рядом. То есть вот такой код
@LOOP:
inc BX;
fmul dword ptr [R11 + RBX*4]; // вычисление адреса займет 2 такта
...
jb @LOOP;
заменить таким
lea RDX, [R11 + RBX*4];
@LOOP:
add RDX, 4;// вычисление адреса займет 1 такт
inc BX;
fmul dword ptr [RDX];
...
jb @LOOP;
Идея состояла в том, что бы немного ускорить перемещение от элемента к элементу. Так вот, такой вариант оказался медленнее, по крайней мере для операций с плавающей точкой на моем процессоре. Честно говоря, несколько удивился этому.
> Так что даже не знаю, какой вариант выбрать. Как думаете?
ОтветитьУдалитьВроде есть еще один вариант: информация о перестановках вроде нужна только на время решения системы, что если хранить данные плоско, а массив указателей переиспользовать между системами для перестановки уравнений? Правда сходу сложно сказать на сколько этот вариант будет лучше/хуже: с одной стороны массив нужно заполнять каждый раз, но с другой минимум математики при самом решении системы. По памяти точно экономнее.
> вычисление адреса займет 2 такта
Вроде масштабирование индекса не влияет на производительность, и lea выполняет умножение и сложение за 1 такт. Забавно что хоть lea и про адреса, но на деле ей можно подсунуть произвольные числа, и тот же clang этим активно пользуется, например "x*5" компилируется в "lea eax, [rdi + 4*rdi]".
Кстати да, что-то не сообразил, можно и маленький массив под ссылки на строки, память хорошо сэкономится. В реальной жизни, наверное, так и нужно делать. В принципе, не важно, когда такая информация будет заполняться: на этапе формирования СЛАУ или в процессе решения, общее время формирования+решение будет примерно одинаковым. Если же сосредоточится именно на времени решения, то тогда формировать надо заранее, наверное.
УдалитьПо документации AMD такая конструкция, как ты привел в своем комментарии, занимает 2 такта. Но, может быть, на совсем новых процессорах и за один такт умудряются делать.
Согласен, смотря что мерять, в реальной жизни формат скорее всего будет привязан к потребителю, и скорее всего 1 из 2-х:
Удалить- плоский массив
- многомерный массив с указателями
При этом не факт что мутировать данные всегда возможно, а если копировать, то алгоритму и решать как хранить удобнее, поэтому переиспользуемый многомерный массив может оказаться лучшим вариантом, но не факт, так как быстрее копировать одномерный...
Известная проблема синтетический тестов, можно так заоптимизировать, что в реальности будет медленнее из-за трансформации входных данных :)
Извиняюсь про LEA был не прав, я смотрел про современный Intel, а AMD Piledriver действительно выполняет LEA с масштабированием за 2 такта судя по https://www.agner.org/optimize/instruction_tables.pdf , но в Ryzen, как я понял, ее наконец ускорили.