Быстрее ли умножать младшие числа в C/C++ (в отличие от больших чисел)?

Question

Пример вопроса:

Вычисление 123 * 456 быстрее, чем вычисление 123456 * 7890? Или это та же скорость?

Я задаюсь вопросом о 32-разрядных целых числах без знака, но я не буду игнорировать ответы о других типах (64-разрядные, со знаком, с плавающей точкой и т. Д.). Если это отличается, в чем разница? Являются ли биты 0/1?

Изменить: Если это имеет значение, я должен уточнить, что я имею в виду любое число (два случайных числа ниже 100 против двух случайных чисел выше 1000)

Answer 1

Для встроенных типов, по крайней мере, с размером слова архитектуры (например, 64-разрядный на современном ПК, 32-разрядный на большинстве недорогих ЦП общего назначения за последние пару десятилетий), для каждого компилятора / реализации / версии и ЦП I' Вы когда-либо слышали о том, чтобы код операции ЦП для умножения определенного интегрального размера занимал определенное количество тактов независимо от используемых величин. Умножение данных разных размеров выполняется по-разному на некоторых процессорах (например, AMD K7 имеет задержку в 3 цикла для 16-битного IMUL, против 4 для 32-битного).

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

При этом, если одно или оба значения являются константами во время компиляции, компилятор может избежать оператора умножения ЦП и оптимизировать операторы сложения или сдвига битов для определенных значений (например, 1 очевидно, что нет, обе стороны 0 ==> 0 результат, * 4 иногда может быть реализовано как << 2). Нет ничего особенного в методах остановки, таких как сдвиг битов, используемых для больших чисел, но меньший процент таких чисел может быть оптимизирован в той же степени (например, существует больше степеней двойки - для которых умножение может быть выполнено с использованием сдвига битов влево) между 0 и 1000, чем между 1000 и 2000).

Answer 2

Это сильно зависит от архитектуры и модели процессора.

В старые времена (около 1980-1990 гг.) Число единиц в двух числах было бы фактором - чем больше, тем дольше нужно было умножить [после корректировки знака, поэтому умножение на -1 не медленнее, чем умножение на 1, но умножение на 32767 (15 единиц) было заметно медленнее, чем умножение на 17 (2)]. Это потому, что умножение по существу:

unsigned int multiply(unsigned int a, unsigned int b)
{  
    res = 0;  
    for(number of bits)
    {
        if (b & 1)
        {
           res += a;
        }
        a <<= 1;
        b >>= 1;
    }
}

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

Кроме того, в старые времена часто были инструкции сделать 16 x 16 -> 32-битные результаты, но если вы хотели 32 x 32 -> 32 (или 64), компилятор должен был бы вызвать библиотечную функцию [или встроенную такую функция]. Сегодня я не знаю ни одного современного высокопроизводительного процессора [x86, ARM, PowerPC], который не может выполнить по крайней мере 64 x 64 -> 64, некоторые делают 64 x 64 -> 128, все в одной инструкции (не всегда один цикл, хотя

Обратите внимание, что я полностью игнорирую тот факт, что "если данные находятся в кеше, это важный фактор". Да, это фактор - и это немного похоже на игнорирование сопротивления ветра при движении со скоростью 200 км / ч - это совсем не то, что вы игнорируете в реальном мире. Однако для ЭТОГО обсуждения это совершенно неважно. Подобно тому, как люди, занимающиеся спортивными автомобилями, заботятся об аэродинамике, для того, чтобы заставить сложное [или простое] программное обеспечение работать быстро, требуется определенная забота о содержимом кэша.

Answer 3

Для всех намерений и целей одинаковая скорость (даже если бы были различия в скорости вычислений, они были бы неизмеримы). Вот вам пример сравнительного анализа различных операций процессора, если вам интересно: http://www.agner.org/optimize/instruction_tables.pdf.