- Понижение силы операций
-
Понижением силы операции в теории компиляторов называют замену медленных операций, например, умножения и деления, на более быстрые, такие как сложение, вычитание, сдвиг. Так, деление (умножение) на равносильно сдвигу на разрядов вправо (влево).
Существуют алгоритмы преобразования операций умножения и деления на произвольное целое число в последовательность более простых операций (сложений, вычитаний и сдвигов). Подобная оптимизация обычно выполняется компилятором автоматически и не требует вмешательства программиста.
Примеры
Целочисленное умножение на 2:
{ до оптимизации (3 такта на Core 2 Duo) } y := 2*x; { после оптимизации } y := x+x; // 1 такт на Core 2 Duo y := x shl 1; // 1 такт на Core 2 Duo
Целочисленное умножение на 3:{ до оптимизации (3 такта на Core 2 Duo) } y := 3*x; { после оптимизации } y := x+x+x; // 2 такта на Core 2 Duo y := x shl 1 + x; // 2 такта на Core 2 Duo y := x shl 2 - x; // 2 такта на Core 2 Duo
Целочисленное умножение на 4:{ до оптимизации (3 такта на Core 2 Duo) } y := 4*x; { после оптимизации (1 такт на Core 2 Duo) } y := x shl 2;
Целочисленное умножение на 5:{ до оптимизации (3 такта на Core 2 Duo) } y := 5*x; { после оптимизации (2 такта на Core 2 Duo) } y := x shl 2 + x;
Целочисленное умножение на 6:{ до оптимизации (3 такта на Core 2 Duo) } y := 6*x; { после оптимизации } y := (x shl 2 - x) shl 1; // 3 такта, неоптимальный вариант реализации y := x shl 2 + x shl 1; // 2 такта при условии, что операции сдвига попадут в различные исполнительные устройства и будут выполнены параллельно
Можно заметить, что не для всех множителей возможна эффективная замена на более простые операции. Кроме того, решение о подобной замене должно учитывать микроархитектурные особенности процессора (как минимум латентность выполнения операций), под который производится подобная оптимизация (например, операции сдвига на процессоре Pentium 4 выполняются существенно дольше, чем на других процессорах, что необходимо учитывать)[1].
Сноски
- ↑ Во многих компиляторах (например, Intel C++ Compiler) существует возможность при помощи опций командной строки указать компилятору процессор, на котором планируется выполнение программы
Категория:- Оптимизации
Wikimedia Foundation. 2010.