Итак, в прошлом посте я столкнулся с фактом, что полное 128-битное умножение примерно в 8 раз медленнее, чем 64-битное. Как-то медленновато будет!
В чем же дело? А дело, понятно, в коде. Вот в таком:
class operator UInt128.Multiply(Op1, Op2: UInt128): UInt128;
begin
if Op1.HiPart = 0 then
if Op2.HiPart = 0 then // малое умножение
Result := SmallMultiply(Op1.LowPart, Op2.LowPart)
else
Result := Op2*Op1.LowPart
else
if Op2.HiPart = 0 then
Result := Op1*Op2.LowPart
else // большое умножение
Result := LargeMultiply(Op1, Op2);
end;
Идея этого кода в следующем: невозможно оптимизировать весь код на ассемблере, оптимизировать надо только самые часто используемые части. А таким частями часто оказываются "листовые" функции, т. е. функции, которые не вызывают других функций.
Вот и здесь оператор умножения 128 на 64 бита у меня уже был реализован, добавил еще функции для малого и большого умножения.
Но такой подход оправдан только в том случае, если "листовые" функции выполняют достаточно большой объем работы, что бы издержки по вызову и возврату из функции были незначительны на фоне общего времени её выполнения.
Так вот, это не тот случай! "Листовые" функции слишком быстрые и поэтому затраты на их вызов получаются слишком велики.
Поэтому переписываю вышеприведенный оператор умножения на ассемблере без вызова функций.
Кстати, саму структуру этого оператора умножения я тоже не сам придумал, а подсмотрел у AMD в Software Optimization Guide.
У них есть пример 64-битного умножения в 32-битном режиме, собственно, его можно смело переносить в вариант 128-битного умножения на 64-битных регистрах. Естественно, с учетом того, что свободных регистров в 64-битном режиме поболе будет.
Естественно, в примере нет никаких вызовов вспомогательных процедур, просто переходы на разные участки кода, но смысл такой же.
Ну и надо сказать, что они там тоже активно IMUL используют для короткого умножения.
Тем не менее, я при переносе вышеприведенного кода на ассемблер пошел своим путем и использовал полную версию беззнакового умножения. Видимо, в силу упертого консерватизма.
И получил в результате примерно 151 млн. 128-битных умножений в секунду, ускорив исходный код в 1.7 раза. Неплохо!
Теперь 128-битное умножение всего лишь в 4.5 раза медленнее, чем 64-битное, что в принципе вполне приемлемо.
И вот я смотрю на код и вот не нравятся мне эти условные переходы. Думаю: "А что будет, если я вообще от них откажусь?"
Отказываюсь от проверок, тупо всегда умножая, как будто операнды полные , провожу несколько экспериментов с регистровой оптимизацией и еще немного ускоряю полное умножение!
В результате получаю 165 млн. оп./с или в 4.1 раза медленнее 64-битного умножения. Отлично!
Но, возможно, я вместе с водой выплеснул и ребенка? Ведь исходный пример от AMD не просто так был придуман и позволял снизить количество операций умножения, когда один или оба операнды имели данные меньше 64-бит длиной.
Поэтому тестирую вариант, когда один из операндов имеет 128-битные данные, а вот у второго данные помешаются в 64 бита.
С условными операторами это дает 159 млн. оп./с, что совсем не намного быстрее, чем когда оба оператора полноразрядные. А вот без условных операторов, когда всегда выполняется 128-битное умножение полностью, скорость возрастает до 168 млн. оп./с.
То есть полное умножение оказывается быстрее сокращенного!
Почему так? Видимо, из-за условных операторов и сброса конвейера. У меня есть предположение, что этот код из Optimization Guide кочует из одной версии руководства в другую, а написан он был давным-давно, в эпоху 386 или 486 процессоров.
Тогда операции умножения выполнялись гораздо дольше, (от 9 до 38 тактов на 486 процессоре), конвейер либо вообще отсутствовал, либо был очень короткий, а операции сравнения были почти такими же быстрыми, как и сейчас. Поэтому для такой архитектуры использование переходов в процедуре длинного умножения было вполне оправдано.
Но на современных процессорах команда умножения выполняется гораздо быстрее, а конвейер имеет значительную длину, так что его сброс стоит очень дорого. Так что, по всей видимости, для 128-разрядных умножений использовать условные переходы невыгодно.
За исключением, пожалуй, того случая, когда данные обеих операндов меньше 64 бит. К сожалению, оттестировать такой вариант очень сложно, так как результат умножения очень быстро растет.
Но, честно говоря, я не вижу смысла оптимизации именно для такого случая. Если данные столь короткие, то не проще ли для их обработки использовать 64-битный тип?
А если данные все же велики, то вероятность того, что оба операнда будут меньше 64 бит, мала и встречаться будет нечасто, так что потери производительности от такой ситуации будут крайне незначительны.
Ну и наконец про IMUL. Ну все же используют, а я чего-то не стал... Ну, попробую. Я, собственно, не ожидал какого-то увеличения производительности на моем PileDriver, исходя из производительности умножения (короткое и длинное умножение занимают одинаковое количество тактов на этой архитектуре). Да, получилось на одну команду меньше и регистры веселее использовались. Но вот скорость стабильно оказывалась на несколько процентов меньше, чем в случае полного умножения.
Не знаю, с чем это связано. Вообще даже идей нет. Допускаю, что на Intel и на AMD Ryzen с коротким умножением эта функция будет выполняться на те же несколько процентов быстрее. Но в целом это ничего не меняет, поэтому оставил в коде беззнаковую полную версию MUL.
