Simple Faster

−分岐やLoopの高速化例−

Delphi2,3用ソース(4.8kbyte)

　今回は分岐とループの最適化の一例を示します。

問題：
　　配列の中で、負の値が500個続くかどうかを調べる。



宣言部：
const
asiz=100000;
・・・
var
a:integer;
flag:integer;
ar:array[0..asiz-1] of integer;
最初はこういうふうに書くとします。

procedure run1;
var
i,ag:integer;
begin
  ag:=0;
  i:=0;
  while i < asiz do
  begin
     if ar[i]< 0 then inc(ag);
     if ag>=500 then
     begin
          flag:=1;
          i:=asiz;
     end
     else if ar[i]>=0 then ag:=0;
     inc(i);
  end;
end;
//run1を繰り返し実行するのにかかった時間　　416±5(ms)


これを分岐について最適化します

procedure run2;
var
i,ag:integer;
b:boolean;
begin
  ag:=0;
  i:=0;
  while i< asiz do
  begin
     if ar[i]< 0 then
       begin
       inc(ag);
       if ag>=500 then
       begin
         flag:=1;
         i:=asiz;
       end;

       end
     else ag:=0;
     inc(i);
  end;
end;
run2を繰り返し実行するのにかかった時間　　411±7(ms)


この場合はar[x]の値が負の値が多いので速度に差は出ませんが
もっと正の値が出やすくなると差がはっきりしてきます。

次はWhileをForにします。
procedure run3;
var
i,ag:integer;
begin
ag:=0;
for i:=0 to asiz-1 do
  begin
  if ar[i]<0 then
    begin
    inc(ag);
    if ag>=500 then
      begin
      flag:=1;
      break;
      end;
    end
  else ag:=0;
  end;
end;
//run3を繰り返し実行するのにかかった時間　　384±5(ms)


これは速くなりました。
なぜ速くなるかというと
Whileの場合は
　inc 加算
　cmp 比較
　jl ジャンプ
となっていたのが
forのときは
　dec 減算
　jnz ジャンプ
となるためです。

これを
if ag>=500 then
のところでもやってみようとしましたが

procedure run6;
var
i,ag:integer;
begin
ag:=500;
for i:=0 to asiz-1 do
  begin
  if ar[i]<0 then
    begin
    dec(ag);
    if ag=0 then
      begin
      flag:=1;
      break;
      end;
    end
  else ag:=500;
  end;
end;
//run6を繰り返し実行するのにかかった時間　　382±6(ms)


速度は変わりませんでした。
しかたないのでアセンブラで書いてみました

procedure run4;
var
p:integer;
begin
p:=longint(@ar[0]);
  asm
  mov ecx,500;		//ag:=500;
  mov edx,asiz;		//繰り返しの回数をedxレジスタにロードします。
  mov eax,p;		//配列の先頭のアドレスをレジスタにロードします。
@@1:
  cmp dword ptr[eax],0;	//eaxのアドレスが指し示す先と0を比較します。
  jnl @@2;		//小さくなけば@@2にjump
  dec ecx;		//ecxから1を引く(dec(ag))
//  test ecx,ecx
  jnz @@3;		//引き算の結果が零でなければ@@3にジャンプ	
  jmp @@4;		//無条件に@@4にジャンプ
@@2:
  mov ecx,500;		//ecxに500を代入
@@3:
  add eax,4;		//eaxに4を加算(integerのサイズ分アドレスを先に進ませる)
  dec edx;		//カウンタを減らす。(edxには最初は繰り返し回数が入っている)
  jnz @@1;		//引き算の結果が零でなければ@@1にジャンプ
  jmp @@5;		//無条件に@@5にジャンプ
@@4:
  mov Flag,1;		//Flagに1を代入
@@5:
  end;
end;
//run4を繰り返し実行するのにかかった時間　　358±4(ms)


これは速くなりました。
run6では
// test ecx,ecx
が余分にはいっていたのでそれを抜いただけです。

私は、あまり資料はみないで
実験してみて速かったらまあいっかと考えているので
結構いい加減です。
Delphi2,3用ソース(4.8kbyte)
by　黒田　Dycoon
意見、感想などはこちらへ、
Mail adress … dycoon@ceres.dti.ne.jp
上へ
目次へ


GigaHit