опция оптимизации

[Физик]

Есть ли у FPC при комилировании опция оптимизации как например у Фортрана при компляции можно задать опцию оптимизации:
g77 -O ..... или i fort -O3 ....

Программа на Fortran с оптимизацией считает в 5 раз быстрее, чем без оптимизации.
Надеюсь, что у FPC тоже есть такая крутая опция.

[Рождённый_в_СССР]

хм...
-Ox

где x:

g - оптимизация по размеру кода
G - по скорости кода
r - хранить переменные целиком в регистрах (эксперементальная вещь и бывает выкидывает глюки)
u - включить кусочную оптимизацию (принцип - если каждый кусок быстрый, то и алгоритм быстрый), читать ниже об этом...
1 - быстрая оптимизация кода (при компиляции)
2 - чуть медленнее
3 - оптимизация O2 + Ou (где то видел что даже 5-ти проходная?)

так же если оперируете FPU/MMX/SSE/SSE2 не плохо использовать

-Opx

где x:

1 - для 386/486 камней
2 - Pentium/PentiumMMX
3 - PentiumPro,Pentium II-III,Celeron 6 покаления,K6
4 - Pentium 4
5 - Pentium M

будет базовая арифметика (включая массивную) работать быстрее... а также переходы в программе... но связывается с каким-то одним камнем...

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

на практике даже -O2 вполне хватает... я иногда на асме не могу лучше кода придумать, чем FPC мне выдаёт... по умолчанию юзается -OG, -O1 - менее эфективная, -O2 и -O3 более эфеткивны

более подробно:

OG - достаточно быстрая и толковая оптимизация (по умолчанию используется) но делает большой код

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

O1 - заменяет хорошо известные структуры на более быстрый эквивалент

O2 - крутит что-то на основе ассемберной оптимизации (уже хорошо развитой в as)

O3 - то же, но более привередливо относится к ускорению именно по времени

с Ou вообще дело тёмное ) её далеко не всегда можно юзать... а так как она входит в O3, то последнюю тоже не всегда...
почему? я сам в этом долго в своё время разбирался )))

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

Код: Выделить всё

G:integer
procedure A(var b:integer);
begin
  if G=b then
  begin
                 inc(b);
                 if G<>b then writeln('bug');
  end;
end;

реально оказывается что G - это конкретная переменная (с адресом), а b - передаваемый параметр (т.е. только адрес) с точки зрения компилятора... и никакой памяти физически ей не выделяется в любом виде компиляций )
при оптимизации Ou однако идея такая:
определённо инкримировать регистр лучше, чем прибавлять в памяти хз где единицу, а так как оптимизируем блоками не знаем что G и b завязыны и даже есть одна и та же переменная! то выдается код вида

Код: Выделить всё

            mov ax, G
            mov bx,word [b]
            cmp bx,ax
            je +4 (@1)
            jmp @END
         @1: inc bx
            jne @ВЫВЕСТИ_СЛОВО_БАГ <- не знаем, что то , что в bx должно по идее быть в [b], т.е. в G )
         @END:
            mov word [b],ax       <- только тут сообщаем, что переменная одна и таже ! потому как адреса совпадают [G]=b
            ret

вместо положенного

Код: Выделить всё

            mov ax, G
            mov bx, b
            cmp word [bx],ax
            je +4 (@1)
            jmp @END
         @1: 
            inc [bx]               <- инкримируем именно содержимое в памяти
            mov ax,G            <- читаем что именно сравниваем с b        
            cmp [bx],ax         <- оказывается в G уже всё изминилось ! )
            jne @ВЫВЕСТИ_СЛОВО_БАГ <- и этого не выведется
         @END:
            ret

поэтому при такой оптимизации функция A(G) выдаст слово bug, несмотря на то, что G=b (потому как она вызывается так... и адреса у них одинаковые) но блок функции не успел сообщить глобальной переменной, что её значение изменено... это требует частичная компиляция... вроде вот так приблизительно разжёван пример...

после -Ou пример по коду становится меньше на 4 байта, а по скорости - почти на 20% меньше тиков на i486, однако выводит слово bug ) чего быть не должно...

поэтому -Ou и -O3 стоит пользоваться с осторожностью... если не понимаете, о чём тут речь - лучше вообще не пользоваться экономит это ну не более 10% на практике, если полно минифункций... как в драйверах...

во фортране однако вроде оптимизация бывает и на уровне функций языка, путём выбора лучшего алгоритма... здесь такое редко проглядывается... потому как алгоритм пишет программист и сам же его оптимизирует... однако на уровне конструкций ассемблера - оптимизация изумительная... я сам не раз поражался находчивости авторов FPC... за нами только правильно алгоритм придумать... хотя бы +/- близкий к оптимальным всякие муравьиные алгоритмы пример обратного )

p.s. думаю достаточно... если что неправильно - поправьте )
p.p.s. извините за Intel-синтаксис... я не уважаю те компиляторы, где только AT&T типа GNU... (продолжите сами)

[Физик]

Рождённый_в_СССР, спасибо за развёрнутый ответ.

К сожалению , при использовании "ручной" оптимизации, например "-OG - O3 - Op4", код быстрее чем, при опртимизации по умолчанию, работать не стал.

Этот же код на Fortran c указаной в первом посте оптимизацией работает в 3.6 раза быстрее, чем на FPC. Для меня важно именно быстродействие, поэтому подумываю вернуться назад к Fortranу.

Далее привожу тескт кода для тестирования быстродействия на FPC и Fortran. Кому интересно, можете пооптимизировать.

Достигнутые результаты для FPC - 68 сек., для Fortrana - 19 cек!!! на Intel Pentium 4 3.4 Ггц под Linux, т.е. А=68/19=3.6.

Если кому удасться получить значение А пусть не меньше 1, а хотя бы поряка 1, то остаюсь в Вашей FPC-компании.



FPC:

program matmult;
uses Dos;
var
i,j,k,l,n : integer;
a,b,c : array [1..2000,1..2000] of double;
col : array [1..2000] of double;
op,mf : double;
tim1,tim2,tim : real;

function second :real;
var
h1,m1,s1,ds1 : word;
begin
GetTime(h1,m1,s1,ds1);
second := h1*3600+m1*60+s1+0.01*ds1;
end;

begin
n := 2000;
op := (2.0*n-1)*n*n;

for j:=1 to n do
for i:=1 to n do
begin
a[i,j]:=i;
b[i,j]:=1.0/j;
end;

writeln(' N = ', n);
tim1 := second;

for j:= 1 to n do
begin
for l := 1 to n do
col[l] := b[l,j];

for i := 1 to n do
begin
c[i,j] := 0.0;
for k := 1 to n do
c[i,j] := c[i,j] + a[i,k]*col[k];
end;
end;
tim2:= second;
tim := tim2 -tim1;
mf := op/(tim*1000000.0);
writeln( c[1,1],c[1,n]);
writeln( c[n,1],c[n,n]);

writeln(' TIME CALCULATION: ', tim,' MFLOPS: ', MF);

end.

Тот же код на Fortran:

PROGRAM MATMULT
IMPLICIT NONE
INTEGER I,J,K,N,L,NM
PARAMETER ( N=2000)
REAL*8 A(N,N),B(N,N),C(N,N),S,ROW(N),COL(N)
REAL*8 TIME,DDOT,OP,MF,DSECND


OP = (2.D0*N-1)*N*N

DO 1 I = 1,N
DO 1 J = 1,N
A(I,J) = DBLE(I)
B(I,J) = 1./DBLE(J)
1 CONTINUE

WRITE(*,*) 'N = ',N
TIME = DSECND()

DO 2 I = 1,N
DO L = 1,N
ROW(L) = A(I,L)
END DO
DO 2 J = 1,N
C(I,J) =0.0d0
DO 3 K = 1,N
3 C(I,J) = C(I,J) + ROW(K)*B(K,J)
2 CONTINUE

TIME = DSECND() - TIME
MF = OP/(TIME*1000000.0)
WRITE(*,10) C(1,1),C(1,N),C(N,1),C(N,N)
10 FORMAT(2X,2F16.6)
WRITE(*,*) ' TIME CALCULATION: ', TIME,
*' MFLOPS: ', MF
END

double precision function dsecnd()
real tarray(2)
dsecnd = etime(tarray)
return
end

[Slavikk]

>Физик
Низкоуровневые операции будут быстрее на фортране или асме. И интел на данный момент производит один из быстрых компиляторов фортран. С другой стороны если программа не под дос и состоит не из 3 циклов, так же присутствует операции считывания и запись данных во внешние источники - разница в скорости незначительна (теряется при считывании и записи). А если нужно оптимизировать короткие циклы, то лично я использую учебник по асму .

>Рождённый_в_СССР
Очень полезный материал, в wiki бы запостить.

[volvo877]

Физик, а давай в следующий раз ты будешь выкладывать действительно аналогичные программы? Ты же в Паскалевскую программу внес никому не нужное перемещение данных:

Код: Выделить всё

for l := 1 to n do
  col[l] := b[l,j];

, чего, заметь, в Fortran-овском варианте просто НЕТ, там ты почему-то пользуешься именно B(K, J). Давай посмотрим, что будет, если матрицу B представить как массив СТОЛБЦОВ, и работать с ней напрямую?

Код: Выделить всё

program matmult;
uses Dos;

type
  vector = array[1 .. 2000] of double;
var
  i,j,k,l,n : integer;
  a,b,c : array [1..2000] of vector;
  col : vector;

  op,mf : double;
  tim1,tim2,tim : real;

function second :real;
var
  h1,m1,s1,ds1 : word;
begin
  GetTime(h1,m1,s1,ds1);
  second := h1*3600+m1*60+s1+0.01*ds1;
end;

var
  s: double;

begin
  n := 2000;
  op := (2.0*n-1)*n*n;

  for j:=1 to n do
    for i:=1 to n do begin
      a[i,j]:=i;
      b[j,i] := 1.0/j; // Внимание на индексы, работаем с массивом столбцов !
    end;

  writeln(' N = ', n);
  tim1 := second;

  for j:= 1 to n do begin
    for i := 1 to n do begin
      s := 0.0;
      for k := 1 to n do
        s := s + a[i,k]*b[j, k]; // Здесь тоже
      c[i,j] := s;
    end;
  end;

  tim2:= second;
  tim := tim2 -tim1;
  mf := op/(tim*1000000.0);
  writeln( c[1,1],c[1,n]);
  writeln( c[n,1],c[n,n]);

  writeln(' TIME CALCULATION: ', tim:10:5,' MFLOPS: ', MF:10:5);
end.

И что? Программа сразу становится минимум на 20% быстрее...

[shade]

Я не могу сравнивать FPC vs Fortran, но вот как бы я оптимизировал:

во-1-х:
Цикл

Код: Выделить всё

       for j:=1 to n do
          for i:=1 to n do
            begin 
                  a[i,j]:=i;
                  b[i,j]:=1.0/j;
             end;

Я бы заменил на

Код: Выделить всё

for i:=1 to n do
  for j:=1 to n do
  begin 
    a[i,j]:=i;
    b[i,j]:=1.0/j;
  end;

обрадуем кеш процессора последовательной записью

во-2-х я попробовал бы ещё оптимизировать этот цикл так:
сменим нумерацию с [1,n] на [0,n-1] и

Код: Выделить всё

for k:=0 to n*n-1 do
begin
  i := k div n;
  j := k mod n;
  a[i,j] := i + 1;
  b[i,j] := 1.0/ (j + 1);
end;

Было - два цикла - стал один => было два условных перехода - стал один => реже сброс конвейра

Т.к. этот цикл вне подсчета времени, то будем считать что был он просто для примера.

в-3-х - матрица b после инициализации только читается,.. причем читается по столбцам - транспонируем её и будет читаться по строкам - чему обрадуется кеш

в-4-х - после п.3 нам не нужен массив col - в лучшем случае заменим его на указатель

в-5-х - b[i,j] = 1 / j - а зачем вообще нам матрица? Если она всегда такая, то она нам не нужна мы раскроем соответвующие значения не посредственно в цикле
col[k] := b[k,j];
b[k,j] = 1 / j
=> col[k] = 1 / j
=> 1 / j можно вынести за один цикл

в-6-х аналогично a[i,j] = i;
Цикл

Код: Выделить всё

      for j:= 1 to n do
        begin
        for l := 1 to n do
        col[l] := b[l,j]; 
        
      for i := 1 to n do
        begin
         c[i,j] := 0.0;
          for k := 1 to n do
          c[i,j] := c[i,j] + a[i,k]*col[k];
         end;
   end; 

упрощается до

Код: Выделить всё

for j := 1 to n do
  for i := 1 to n do
  begin
    c[i,j] := 0;
    for k := 1 to n do
      c[i,j] := c[i,j] + i / j;
  end;

Поправте, если где-то ошибся - главное идея понятна

В целом перепишется так:

Код: Выделить всё

program matmult;
uses Dos;

const
  n = 600;
  op = (2.0*n-1)*n*n; { интересно а что это такое? }
  prec = 4;  { число знаков после точки - для вывода резултата }

var
  c: array [0..n-1, 0..n-1] of double;
  i,j,k,l: longint;
  mf: double;
  tim1, tim2, tim: real;
  
function second :real;
var
  h1,m1,s1,ds1 : word;
begin
  GetTime(h1,m1,s1,ds1);
  second := h1*3600+m1*60+s1+0.01*ds1;
end; 
 
begin      
  writeln('  N = ', n);  
  tim1 := second;
  
  for l := 0 to n*n-1 do
  begin
    j := l div n;
    i := l mod n;
    c[i,j] := 0.0;
    for k := 0 to n-1 do
      c[i,j] := c[i,j] + (i + 1) / (j + 1);
  end; // for l
  
  tim2:= second;
  tim := tim2 -tim1;
  mf := op/(tim*1000000.0);
  writeln( c[0,0]:10:prec, ' ', c[0,n-1]:10:prec );
  writeln( c[n-1,0]:10:prec,' ', c[n-1,n-1]:10:prec );

  writeln(' TIME CALCULATION: ', tim:10:prec,' MFLOPS: ', MF:10:prec);
end.

[shade]

в-7-х

Код: Выделить всё

  c[i,j] := 0.0; 
    for k := 0 to n-1 do
      c[i,j] := c[i,j] + (i + 1) / (j + 1); 

переписывается в виде

Код: Выделить всё

c[i,j] := n * (i + 1) / (j + 1);

После такой оптимизации Fortran уже не нужен

и полный код

Код: Выделить всё

program matmult;
uses Dos;

const
  n = 2000;
  op = (2.0*n-1)*n*n; { интересно а что это такое? }
  prec = 4;  { число знаков после точки - для вывода резултата }

var
  c: array [0..n-1, 0..n-1] of double;
  i,j,l: longint;
  mf: double;
  tim1, tim2, tim: real;
  
function second :real;
var
  h1,m1,s1,ds1 : word;
begin
  GetTime(h1,m1,s1,ds1);
  second := h1*3600+m1*60+s1+0.01*ds1;
end; 
 
begin      
  writeln('  N = ', n);  
  tim1 := second;
  
  for l := 0 to n*n-1 do
  begin
    j := l div n;
    i := l mod n;
    c[i,j] := n * (i + 1) / (j + 1);
  end; // for l
  
  tim2:= second;
  tim := tim2 -tim1;
  mf := op/(tim*1000000.0);
  writeln( c[0,0]:10:prec, ' ', c[0,n-1]:10:prec );
  writeln( c[n-1,0]:10:prec,' ', c[n-1,n-1]:10:prec );

  writeln(' TIME CALCULATION: ', tim:10:prec,' MFLOPS: ', MF:10:prec);
end.

(быть может ещё можно оптимизировать)

[shade]

например так

Код: Выделить всё

program matmult;
const n = 2000;
begin
  writeln(n: 10, ' ', 1:10);
  writeln(n*n: 10, ' ', n:10);
end.

Что-то я зутрудняюсь с подсчётом MF

[Физик]

Физик, а давай в следующий раз ты будешь выкладывать действительно аналогичные программы? Ты же в Паскалевскую программу внес никому не нужное перемещение данных:

Код: Выделить всё

for l := 1 to n do
  col[l] := b[l,j];

, чего, заметь, в Fortran-овском варианте просто НЕТ, там ты почему-то пользуешься именно B(K, J). Давай посмотрим, что будет, если матрицу B представить как массив СТОЛБЦОВ, и работать с ней напрямую?

Код: Выделить всё

program matmult;
uses Dos;

type
  vector = array[1 .. 2000] of double;
var
  i,j,k,l,n : integer;
  a,b,c : array [1..2000] of vector;
  col : vector;

  op,mf : double;
  tim1,tim2,tim : real;

function second :real;
var
  h1,m1,s1,ds1 : word;
begin
  GetTime(h1,m1,s1,ds1);
  second := h1*3600+m1*60+s1+0.01*ds1;
end;

var
  s: double;

begin
  n := 2000;
  op := (2.0*n-1)*n*n;

  for j:=1 to n do
    for i:=1 to n do begin
      a[i,j]:=i;
      b[j,i] := 1.0/j; // Внимание на индексы, работаем с массивом столбцов !
    end;

  writeln(' N = ', n);
  tim1 := second;

  for j:= 1 to n do begin
    for i := 1 to n do begin
      s := 0.0;
      for k := 1 to n do
        s := s + a[i,k]*b[j, k]; // Здесь тоже
      c[i,j] := s;
    end;
  end;

  tim2:= second;
  tim := tim2 -tim1;
  mf := op/(tim*1000000.0);
  writeln( c[1,1],c[1,n]);
  writeln( c[n,1],c[n,n]);

  writeln(' TIME CALCULATION: ', tim:10:5,' MFLOPS: ', MF:10:5);
end.

И что? Программа сразу становится минимум на 20% быстрее...

Попробовал не на 20%, а на 0.3%. Не устраивает...

[Физик]

в-7-х

Код: Выделить всё

  c[i,j] := 0.0; 
    for k := 0 to n-1 do
      c[i,j] := c[i,j] + (i + 1) / (j + 1); 

переписывается в виде

Код: Выделить всё

c[i,j] := n * (i + 1) / (j + 1);

После такой оптимизации Fortran уже не нужен

и полный код

Код: Выделить всё

program matmult;
uses Dos;

const
  n = 2000;
  op = (2.0*n-1)*n*n; { интересно а что это такое? }
  prec = 4;  { число знаков после точки - для вывода резултата }

var
  c: array [0..n-1, 0..n-1] of double;
  i,j,l: longint;
  mf: double;
  tim1, tim2, tim: real;
  
function second :real;
var
  h1,m1,s1,ds1 : word;
begin
  GetTime(h1,m1,s1,ds1);
  second := h1*3600+m1*60+s1+0.01*ds1;
end; 
 
begin      
  writeln('  N = ', n);  
  tim1 := second;
  
  for l := 0 to n*n-1 do
  begin
    j := l div n;
    i := l mod n;
    c[i,j] := n * (i + 1) / (j + 1);
  end; // for l
  
  tim2:= second;
  tim := tim2 -tim1;
  mf := op/(tim*1000000.0);
  writeln( c[0,0]:10:prec, ' ', c[0,n-1]:10:prec );
  writeln( c[n-1,0]:10:prec,' ', c[n-1,n-1]:10:prec );

  writeln(' TIME CALCULATION: ', tim:10:prec,' MFLOPS: ', MF:10:prec);
end.

(быть может ещё можно оптимизировать)

К сожалению, этот код к исходному не имеет никакого отношения.

[shade]

К сожалению, этот код к исходному не имеет никакого отношения.

Как это не имеет? Вычисляет-то он тоже самое... или вы нашли ошибку?

В таком случае уточните задачу

Если речь идет о перемножении произвольных матриц, то есть более эффектиывные методы (в сравнении с умножением по определению), например, метод Штрассена - очень хорошо работает именно для больших матриц и имеет сложность примерно O(n^ 2.81). Лучший результат, если верить Кормену порядка O(n^2.376), только вот что-то забыл назвать алгоритм...

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

[Физик]

К сожалению, этот код к исходному не имеет никакого отношения.

Как это не имеет? Вычисляет-то он тоже самое... или вы нашли ошибку?

В таком случае уточните задачу

Если речь идет о перемножении произвольных матриц, то есть более эффектиывные методы (в сравнении с умножением по определению), например, метод Штрассена - очень хорошо работает именно для больших матриц и имеет сложность примерно O(n^ 2.81). Лучший результат, если верить Кормену порядка O(n^2.376), только вот что-то забыл назвать алгоритм...

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

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

Для перемножения матриц требуется выполнить N**3 ( N в кубе) операций, где N размерность матрицы. Кстати, op и есть - кол-во опрераций.
В вашей программе выполняется N**2 операций, что уж тут удивляться, что она работает так быстро.

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

[shade]

Ваша программа - это просто заполнение матрицы С по некоторому алгоритму.

Согласитесь, ваша программа тоже заполняет матрицу C по некоторому другому алгоритму, причем заполняет точно также...

Для перемножения матриц требуется выполнить N**3 ( N в кубе) операций, где N размерность матрицы.

Это если о исходных матрицах нам ничего неизвестно кроме их размера (NxN), да и то есть более эффективные алгоритмы, см. выше...

А если о матрице ещё кое-что известно, то сами видете результат - O(N^2) - теортетический минимум.

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

Дык, в том и смысл оптимизации...

А так получается просто сравнение компиляторов...

Но раз уж на то пошло, то сравните ещё с таким вариантом
(только с -O3 у меня выдает не верный результат)

Код: Выделить всё

program matmult;
uses Dos;
  var
    i,j,k,l,n          : longint;
    a,b,c              : array [0..2000,0..2000] of double;
    op,mf            : double;
    tim1,tim2,tim      : real;

   function second :real;
    var
       h1,m1,s1,ds1 : word;
    begin
      GetTime(h1,m1,s1,ds1);
      second := h1*3600+m1*60+s1+0.01*ds1;
     end; 
 
 begin      
      n := 2000;
      op := (2.0*n-1)*n*n;
            
       for j:=0 to n-1 do
          for i:=0 to n-1 do
            begin 
                  a[i,j]:=i + 1;
                  b[j,i]:=1.0 / (j + 1); // ! траспонированная матрица
             end;
               
      writeln('  N = ', n);  
      tim1 := second;
      
      for l := 0 to n*n-1 do
      begin
        i := l div n;
        j := l mod n;
        c[i,j] := 0;
        for k := 0 to n-1 do
          c[i,j] := c[i,j] + a[i,k]*b[j,k]; // ! см. выше
      end;
     
        tim2:= second;
      tim := tim2 -tim1;
      mf := op/(tim*1000000.0);
      writeln( c[0,0],   c[0,n-1]);
      writeln( c[n-1,0], c[n-1,n-1]);
 
      writeln(' TIME CALCULATION: ', tim:0:5,' MFLOPS: ', MF:0:5);
  
  end.

PS: Кстати, а какая у вас версия FPC? Попробуйте FPC 2.3.1 из svn...

[shade]

Сдаюсь,
сравнил g77 (не пойму какой версии) и fpc 2.3.1 (с неделю назад обновленный из svn)

Конкретно на этом примере g77 быстрее fpc в ~2.16 раза
(если расчеты верны)

[Физик]

Сдаюсь,
g77 быстрее fpc в ~2.16 раза
(если расчеты верны)

Для меня тоже такое превышение по скорости g77 (или отставание FPC) стало неприятной неожиданностью.

Всё таки придёться вернуться к старому-доброму Fortranу.