Есть ли предел у оптимизации?

← →
badevlad © (2007-04-17 14:26) [0]

Разрабатываю один алгоритм, в нем есть очень большой цикл. В цикле выполняются следующий код:
var R1, R2, R3, SW, W1, W2: Single; B1, B2, B3, A1, A2, A3: Byte; // Cycle for ... do begin R1 := 0; R2 := 0; R3 := 0; for ... do begin SW := W1 * W2; R1 := R1 + B1 * SW; R2 := R2 + B2 * SW; R2 := R2 + B3 * SW; end; A1 := Round(R1); A2 := Round(R2); A3 := Round(R3); end;
Циклы очень большие, поэтому даже самая малая оптимизация дает очень значительный прирост быстродействия. Можно ли тут что-либо оптимизировать, или предел оптимизации уже достигнут?

← →
Kolan © (2007-04-17 14:31) [1]

> R1, R2, R3, SW, W1, W2: Single;
> B1, B2, B3, A1, A2, A3: Byte;

Убил бы за такие названия :(, ей богу убил&#133

A1 := Round(R1);
A2 := Round(R2);
A3 := Round(R3);

А на следующем витке цикла получены результаты затрутся новыми итд&#133 тогда это можно вынести за цикл.

← →
Сергей М. © (2007-04-17 14:32) [2]

Совершенству, как известно, предела нет)

← →
MBo © (2007-04-17 14:59) [3]

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

← →
badevlad © (2007-04-17 14:59) [4]

Разумеется, это только часть кода, упрощенный вариант. Нет смысла путать уважаемых программистов лишними переменными... Значения используются, но оптимизировать можно только здесь.

← →
badevlad © (2007-04-17 15:02) [5]

Значения переменной SW лежат в пределах от 0 до 1. Целые числа пробовал, приходится сначала умножать на 1000 (например), а потом на это же число делить. В результате скорость значительно (!) понизилась. Видимо, сопроцессор старается.

← →
Сергей М. © (2007-04-17 15:03) [6]

> badevlad © (17.04.07 14:59) [4]

А какие "узкие" места в твоем коде, как сам-то думаешь ?

← →
badevlad © (2007-04-17 15:06) [7]

Тестирование показывает, что максимальные затраты времени уходят на вычисления в самом вложенном цикле:
SW := W1 * W2; R1 := R1 + B1 * SW; R2 := R2 + B2 * SW; R2 := R2 + B3 * SW;
Без этого кода скорость возрастает на порядок.

← →
Desdechado © (2007-04-17 15:09) [8]

1. Есть подозрения, что тип Byte обрабатывается медленнее, чем тип Integer/Cardinal.
2. Какой смысл каждый раз вычислять в цикле SW, если переменные, от которых оно зависит, не меняются в этом цикле?
3. Очень подозрительная строка R2 := R2 + B3 * SW;, может, там R3 надо?

← →
Сергей М. © (2007-04-17 15:10) [9]

По кр.мере есть резон реализовать эти строки на ассемблере.

← →
badevlad © (2007-04-17 15:23) [10]

Для Desdechado:

1. Возможно, попробую. Но вряд ли...
2. Не обращайте внимание, это из-за некоторых сокращений.
3. Не важно, главное - принцип.

← →
MBo © (2007-04-17 15:59) [11]

Приведи более реальный код

> badevlad

Слушай > MBo © (17.04.07 15:59) [11].

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

> 1. Есть подозрения, что тип Byte обрабатывается медленнее,
> чем тип Integer/Cardinal

По идее, одинаково - при условии выключенного Range Checking.

Пробовал - одинаково.

for ... do begin SW := W1 * W2; R1 := R1 + B1 * SW; R2 := R2 + B2 * SW; R3 := R3 + B3 * SW; end;
Меняем на:
SW := W1 * W2; b1sw:=B1 * SW; b2sw:=B2 * SW; b3sw:=B3 * SW; for ... do begin R1 := R1 + b1sw; R2 := R2 + b2sw; R3 := R3 + b3sw; end;

> badevlad © (17.04.07 14:26)

Переменные SW, W1, W2, B1, B2 и B3 по отношению к внутреннему циклу инвариантны - значит, выносим их вычисления за цикл и получаем [15]. После этого внутренний цикл становится вообще не нужен, т.к. R1, R2 и R3 вычисляются простым умножением:
R1 := b1sw * M;
R2 := b2sw * M ;
R3 := b3sw * M;
где M - количество итераций внутреннего цикла.

Выкидываем внутренний цикл и видим, что начальное обнуление этих переменных тоже не требуется и его тоже можно выкинуть. Остается наружный цикл, а в нем - три заключительные формулы. Но они опять же инвариантны и тоже могут быть вынесены за цикл - после чего наружный цикл становится пустым и тоже выкидывается.

В итоге остаются 4 формулы и никаких циклов:
SW := W1 * W2 * M;
A1 := Round(B1 * SW);
A2 := Round(B2 * SW);
A3 := Round(B3 * SW);

И еще остается вопрос - либо все это действительно так, либо требуется уточнение условий задачи.

А single лучше заменить на родной тип сопроцессора (double или extended в зависимости от режима).

Есть ли предел у оптимизации? Найти похожие ветки