Снижение стоимости операций

Снижением стоимости операций в теории компиляторов называют замену медленных операций, например, умножения и деления, на более быстрые, такие как сложение, вычитание, сдвиг. Так, деление (умножение) на $\text{[math]}$ $\text{[math]}$ $2^{n}$ $2^{n}$ равносильно сдвигу на $\text{[math]}$ $\text{[math]}$ $n$ $n$ разрядов вправо (влево).

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

ПримерыПравить

Целочисленное умножение на 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) существует возможность при помощи опций командной строки указать компилятору процессор, на котором планируется выполнение программы

ЛитератураПравить

Альфред Ахо, Моника Лам, Рави Сети, Джеффри Ульман. Компиляторы: принципы, технологии и инструментарий = Compilers: Principles, Techniques, and Tools. — 2-е издание. — М.: «Вильямс», 2008. — 1184 с. — 1500 экз. — ISBN 978-5-8459-1349-4.
Allen, Francis E.; Cocke, John & Kennedy, Ken (1981), Reduction of Operator Strength, in Munchnik, Steven S. & Jones, Neil D., Program Flow Analysis: Theory and Applications, Prentice-Hall, ISBN 978-0-13-729681-1
Cocke, John & Kennedy, Ken (November 1977), An algorithm for reduction of operator strength, Communications of the ACM Т. 20 (11)
Cooper, Keith; Simpson, Taylor & Vick, Christopher (October 1995), Operator Strength Reduction, Rice University, <http://softlib.rice.edu/pub/CRPC-TRs/reports/CRPC-TR95635-S.pdf>. Проверено 22 апреля 2010.

[1] Во многих компиляторах (например, Intel C++ Compiler) существует возможность при помощи опций командной строки указать компилятору процессор, на котором планируется выполнение программы

[1]