56

バックグラウンド

私の質問は、経験豊富な MATLAB ユーザーがしばしば保持/作成する信念/仮定を幾分弱体化させる単純な観察によって動機付けられています。

  • MATLAB は、組み込み関数や基本的な言語機能 (インデックス ベクトルや行列など) に関して、非常に最適化されています。
  • MATLAB のループは (JIT にもかかわらず) 低速であり、アルゴリズムがネイティブの「ベクトル化」された方法で表現できる場合は、一般的に回避する必要があります。

要するに、MATLAB のコア機能は効率的であり、MATLAB コードを使用してそれを凌駕しようとすることは、不可能ではないにしても困難です。

ベクトル索引付けのパフォーマンスの調査

以下に示すコード例は基本的なものです。すべてのベクトル エントリにスカラー値を割り当てます。まず、空の vector を割り当てますx

tic; x = zeros(1e8,1); toc
Elapsed time is 0.260525 seconds.

すべてのエントリをx同じ値に設定したいと思います。実際には、たとえば のように別の方法で行うことになりますx = value*ones(1e8,1)が、ここでのポイントは、ベクトル インデックスのパフォーマンスを調査することです。最も簡単な方法は次のように書くことです:

tic; x(:) = 1; toc
Elapsed time is 0.094316 seconds.

これを方法 1 と呼びましょう ( に割り当てられた値からx)。非常に高速のようです (少なくともメモリ割り当てよりも高速です)。ここで行うのはメモリ操作だけなので、得られた実効メモリ帯域幅を計算し、それを私のコンピューターのハードウェア メモリ帯域幅と比較することで、このコードの効率を見積もることができます。

eff_bandwidth = numel(x) * 8 bytes per double * 2 / time

上記では、2SSE ストリーミングが使用されない限り、メモリ内の値を設定するには、メモリからの読み取りとメモリへの書き込みの両方が必要になるため、乗算します。上記の例では:

eff_bandwidth(1) = 1e8*8*2/0.094316 = 17 Gb/s

私のコンピューターのSTREAM ベンチマーク メモリ帯域幅は約 17.9 Gb/s であるため、実際、この場合、MATLAB はピークに近いパフォーマンスを提供します! ここまでは順調ですね。

方法 1 は、すべてのベクトル要素を何らかの値に設定する場合に適しています。ただし、エントリごとに要素にアクセスする場合は、を などstepに置き換える必要があります。以下は、方法 1 との直接の速度比較です。:1:step:end

tic; x(1:end) = 2; toc
Elapsed time is 0.496476 seconds.

異なるパフォーマンスを期待することはできませんが、方法 2 は明らかに大きな問題です。理由もなく 5 倍の速度低下が発生します。私の疑いは、この場合、MATLAB がインデックス ベクトル ( 1:end) を明示的に割り当てることです。これは、 の代わりに明示的なベクトル サイズを使用することで多少確認されendます。

tic; x(1:1e8) = 3; toc
Elapsed time is 0.482083 seconds.

方法 2 と 3 のパフォーマンスは同じくらい悪いです。

もう 1 つの可能性は、インデックス ベクトルを明示的に作成し、idそれを index に使用することxです。これにより、最も柔軟なインデックス作成機能が提供されます。私たちの場合には:

tic;
id = 1:1e8; % colon(1,1e8);
x(id) = 4;
toc
Elapsed time is 1.208419 seconds.

方法 1 と比較して 12 倍の速度低下です。に使用されるメモリが増えるため、方法 1 よりもパフォーマンスが低下することは理解していますがid、方法 2 および 3 よりもパフォーマンスが大幅に低下するのはなぜですか?

絶望的に聞こえるかもしれませんが、ループを試してみましょう。

tic;
for i=1:numel(x)
    x(i) = 5;
end
toc
Elapsed time is 0.788944 seconds.

驚くべきことに、ループはvectorized方法 4 よりも優れていますが、それでも方法 1、2、3 よりも遅いです。

tic;
for i=1:1e8
    x(i) = 6;
end
toc
Elapsed time is 0.321246 seconds.

そして、これがおそらくこの研究の最も奇妙な結果です。MATLAB で記述されたループは、ネイティブのベクトル インデックス作成よりも大幅に優れています。そんなはずはありません。JIT されたループは、方法 1 でほぼ得られた理論上のピークよりも 3 倍遅いことに注意してください。したがって、まだ改善の余地がたくさんあります。通常の「ベクトル化された」索引付け ( 1:end) がさらに遅いことは驚くべきことです (強い言葉の方が適しています)。

質問

  • MATLAB での単純なインデックス付けは非常に非効率的です (方法 2、3、および 4 は方法 1 よりも遅い)、または何かを見逃していましたか?
  • 方法 4が方法 2 および 3よりも(非常に) 遅いのはなぜですか?
  • 1e8ループ バウンドの代わりに使用するとnumel(x)、コードが 2 倍高速化されるのはなぜですか?

編集 ジョナスのコメントを読んだ後、論理インデックスを使用してそれを行う別の方法を次に示します。

tic;
id = logical(ones(1, 1e8));
x(id) = 7;
toc
Elapsed time is 0.613363 seconds.

方法 4 よりもはるかに優れています。

便宜上:

function test

tic; x = zeros(1,1e8); toc

tic; x(:) = 1; toc
tic; x(1:end) = 2; toc
tic; x(1:1e8) = 3; toc

tic;
id = 1:1e8; % colon(1,1e8);
x(id) = 4;
toc

tic;
for i=1:numel(x)
    x(i) = 5;
end
toc

tic;
for i=1:1e8
    x(i) = 6;
end
toc

end
4

3 に答える 3

14

もちろん、私は推測することしかできません。ただし、JIT コンパイラを有効または無効にしてテストを実行すると、次の結果が得られます。

 % with JIT   no JIT
    0.1677    0.0011 %# init
    0.0974    0.0936 %# #1 I added an assigment before this line to avoid issues with deferring
    0.4005    0.4028 %# #2
    0.4047    0.4005 %# #3
    1.1160    1.1180 %# #4
    0.8221   48.3239 %# #5 This is where "don't use loops in Matlab" comes from 
    0.3232   48.2197 %# #6
    0.5464   %# logical indexing

分割すると、どこで速度が向上するかがわかります。

% withoutJit./withJit
    0.0067 %# w/o JIT, the memory allocation is deferred
    0.9614 %# no JIT
    1.0057 %# no JIT
    0.9897 %# no JIT
    1.0018 %# no JIT
   58.7792 %# numel
  149.2010 %# no numel

JIT がオフになっていると、MATLAB が使用されるまでメモリ割り当てを遅らせているように見えるため、初期化が高速化されているように見えるため、 x=zeros(...) は実際には何もしません。(ありがとう、@angainor)。

方法 1 から 4 は、JIT の恩恵を受けていないようです。subsref入力が適切な形式であることを確認するための入力テストが追加されているため、#4が遅くなる可能性があると思います。

結果はnumel、コンパイラが不確実な反復回数を処理するのが難しいこと、またはループの境界が適切かどうかをチェックすることによるオーバーヘッドに関係している可能性があります (no-JIT テストでは、そのために ~0.1 秒しか示唆されていないと考えられます)。 )

驚いたことに、私のマシンの R2012b では、論理インデックス作成が #4 よりも遅いようです。

これは、MathWorks がコードの高速化に多大な貢献をしてきたこと、そして最速の実行時間を取得しようとしている場合 (少なくとも、ループを使用しないこと) が常に最善ではないことを示していると思います。この時点で)。それにもかかわらず、(a) JIT はより複雑なループで失敗し、(b) ベクトル化を学ぶことで Matlab をよりよく理解できるため、一般的にベクトル化は良いアプローチであることがわかります。

結論: 速度が必要な場合はプロファイラーを使用し、Matlab のバージョンを切り替える場合はプロファイルを再作成します。 コメントで @Adriaan が指摘したように、最近では timeit() を使用して実行速度を測定する方がよい場合があります。


参考までに、次のわずかに変更されたテスト関数を使用しました

function tt = speedTest

tt = zeros(8,1);

tic; x = zeros(1,1e8); tt(1)=toc;

x(:) = 2;

tic; x(:) = 1; tt(2)=toc;
tic; x(1:end) = 2; tt(3)=toc;
tic; x(1:1e8) = 3; tt(4)=toc;

tic;
id = 1:1e8; % colon(1,1e8);
x(id) = 4;
tt(5)=toc;

tic;
for i=1:numel(x)
    x(i) = 5;
end
tt(6)=toc;

tic;
for i=1:1e8
    x(i) = 6;
end
tt(7)=toc;

%# logical indexing
tic;
id = true(1e8,1));
x(id)=7;
tt(8)=toc;
于 2012-11-14T16:12:14.017 に答える
9

私はすべての問題に対する答えを持っているわけではありませんが、方法 2、3、および 4 についていくつかの洗練された推測があります。

方法 2 と 3 について。実際、MATLAB はベクトル インデックスにメモリを割り当て、 から1までの値で埋めているよう1e8です。それを理解するために、何が起こっているのか見てみましょう。既定では、MATLAB はdoubleデータ型として を使用します。インデックス配列の割り当てには、割り当てと同じ時間がかかりますx

tic; x = zeros(1e8,1); toc
Elapsed time is 0.260525 seconds.

今のところ、インデックス配列にはゼロのみが含まれています。x方法 1 のように、最適な方法でベクトルに値を割り当てるには0.094316数秒かかります。ここで、インデックス ベクトルをメモリから読み取って、インデックス作成に使用できるようにする必要があります。それは追加の0.094316/2秒です。x(:)=1in vectorxは、メモリからの読み取りとメモリへの書き込みの両方が必要であることを思い出してください。したがって、読むだけで半分の時間がかかります。これが で行われるすべてであると仮定するとx(1:end)=value、方法 2 と 3 の合計時間は次のようになります。

t = 0.260525+0.094316+0.094316/2 = 0.402

それはほぼ正しいですが、完全ではありません。推測することしかできませんが、インデックス ベクトルに値を入力することはおそらく追加のステップとして行われ、さらに 0.094316 秒かかります。したがって、t=0.4963これは方法 2 および 3 の時間に多かれ少なかれ適合します。

これらは憶測にすぎませんが、MATLABがネイティブ ベクトル インデックス付けを行うときに明示的にインデックス ベクトルを作成することを確認しているようです。個人的には、これはパフォーマンスのバグだと思います。MATLAB の JIT コンパイラは、この単純な構造を理解し、正しい内部関数の呼び出しに変換できるほどスマートでなければなりません。現在のように、今日のメモリ帯域幅が制限されたアーキテクチャでは、インデックス作成は理論上のピークで約 20% 実行されます。

したがって、パフォーマンスを気にする場合はx(1:step:end)、次のような MEX 関数として実装する必要があります。

set_value(x, 1, step, 1e8, value);

MEX ファイルの配列をインプレースで変更することは許可されていないため、これは MATLAB では明らかに違法です。

編集方法4に関しては、次のように個々のステップのパフォーマンスを分析することができます:

tic;
id = 1:1e8; % colon(1,1e8);
toc
tic
x(id) = 4;
toc

Elapsed time is 0.475243 seconds.
Elapsed time is 0.763450 seconds.

最初のステップであるインデックス ベクトルの値の割り当てと入力には、方法 2 と 3 だけの場合と同じ時間がかかります。多すぎるようです-メモリを割り当てて値を設定するのに必要な時間はせいぜい必要なので( )、どこかに数秒0.260525s+0.094316s = 0.3548sのオーバーヘッドが追加されますが、これは理解できません。0.122 番目の部分 ( ) も非常に非効率に見えます。 の値を設定し、ベクトル ( )を読み取るのに必要な時間と、値のエラー チェックにx(id) = 4時間がかかるはずです。C でプログラムすると、次の 2 つの手順が実行されます。xid0.094316s+0.094316/2s = 0.1415sid

create id                              0.214259
x(id) = 4                              0.219768

使用されるコードは、doubleインデックスが実際に整数を表し、サイズが に適合することを確認しxます。

tic();
id  = malloc(sizeof(double)*n);
for(i=0; i<n; i++) id[i] = i;
toc("create id");

tic();
for(i=0; i<n; i++) {
  long iid = (long)id[i];
  if(iid>=0 && iid<n && (double)iid==id[i]){
    x[iid] = 4;
  } else break;
}
toc("x(id) = 4");

2 番目のステップは、予想よりも時間がかかります。これは、値0.1415sのエラー チェックが必要なためidです。オーバーヘッドが大きすぎるように思えます。もっとうまく書けるかもしれません。それでも、所要時間は0.4340s、ではありません1.208419s。MATLAB が内部で何をしているのか - 私にはわかりません。たぶんそれをする必要があります、私はそれを見ません。

もちろん、doublesインデックスとして使用すると、2 つの追加レベルのオーバーヘッドが発生します。

  • double2倍の大きさuint32。ここではメモリ帯域幅が制限要因であることを思い出してください。
  • インデックス付けのために double を整数にキャストする必要がある

方法 4 は、整数インデックスを使用して MATLAB で記述できます。

tic;
id = uint32(1):1e8;
toc
tic
x(id) = 8;
toc

Elapsed time is 0.327704 seconds.
Elapsed time is 0.561121 seconds.

これにより、明らかにパフォーマンスが 30% 向上し、ベクトル インデックスとして整数を使用する必要があることが証明されました。ただし、オーバーヘッドはまだあります。

私が今見ているように、MATLAB フレームワーク内で動作する状況を改善するために何もすることはできず、Mathworks がこれらの問題を修正するまで待つ必要があります。

于 2012-11-14T17:42:03.783 に答える