(n - Умножение) против (n / 2 - умножение + 2 сложения), что лучше?

Question

У меня есть программа на C, которая имеет n умножений (одно умножение с n итерациями), и я нашел другую логику, которая имеет n / 2 итерации (1 умножение + 2 сложения). Я знаю о сложности, что оба имеют O (n). но с точки зрения циклов процессора. что быстрее?

Answer 1

Тест на вашем компьютере. Или посмотрите спецификации вашего процессора и угадайте.

Старая логика больше не применяется: на современных процессорах целочисленное умножение может быть очень дешевым, на некоторых новых процессорах Intel это 3 такта. Дополнения 1 цикл на этих же процессорах. Однако в современном конвейерном процессоре задержки, созданные зависимостями данных, могут привести к тому, что добавления будут занимать больше времени.

Я предполагаю, что N сложений + N / 2 умножений медленнее, чем N умножений, если вы выполняете операцию типа сгиба, и я бы предположил обратное для операции с типом карты. Но это только предположение.

Проверьте, хотите ли вы правду.

Однако: Большинство таких простых алгоритмов связаны с памятью, и оба будут иметь одинаковую скорость.

Answer 2

Прежде всего, следуйте первому совету Дитриха Эппа - измерение (по крайней мере, для сложных задач оптимизации) - единственный способ быть уверенным.

Теперь, если вы хотите выяснить, почему один быстрее другого, мы можем попробовать. Существует два разных важных показателя производительности: задержка и взаимная пропускная способность. Краткое изложение двух:

Задержка: это задержка, которую инструкция генерирует в цепочка зависимостей. Числа являются минимальными значениями. Кеш пропускает, смещение, и исключения могут увеличить счетчик часов значительно. Там, где включена гиперпоточность, использование того же Выполнение блоков в другом потоке приводит к снижению производительности. Денормальные числа, NAN и бесконечность не увеличивают время ожидания. единица времени используется для тактовых циклов ядра, а не для эталонных тактов определяется счетчиком меток времени.

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

Для Сэнди Бридж рек. пропускная способность для add r, r/i (для дальнейшего уведомления r = регистр, i = немедленный, m = память) равна 0,33, а задержка равна 1.

imul r, r имеет задержку 3 и rec. пропускная способность 1.

Так что, как вы видите, это полностью зависит от вашего конкретного алгоритма - если вы можете просто заменить одно imul двумя независимыми добавлениями, эта конкретная часть вашего алгоритма может получить теоретическое ускорение на 50% (и в лучшем случае, очевидно, ускорение ~ 350%). Но, с другой стороны, если ваши добавления добавляют проблемную зависимость, то один импульс может быть таким же быстрым, как и одно добавление.

Также обратите внимание, что мы проигнорировали все дополнительные сложности, такие как поведение памяти и кэша (вещи, которые, как правило, будут иметь гораздо большее влияние на время выполнения), или сложные вещи, такие как µop fusion и еще много чего. В общем, единственные люди, которые должны заботиться об этом, - авторы компиляторов - гораздо проще измерить результат их усилий;)

В любом случае, если вы хотите получить хороший список этого материала, см. это здесь (вышеупомянутое описание пропускной способности / пропускной способности также взято из этого конкретного документа).