連載1 高速なメモリーコピー 補足

今回は宿題となっていたmmx命令のmovntqについて試してきました。この命令は連載の中で紹介したsse命令のmovntdqと似た働きをしますが、一度に処理できるデータ量が8バイトと少ない代わりにアライメントの制約を受けないと言うメリットがあります。この辺のメリットとデメリットがどう作用するかを試してきました。

check	アライメント	パソコン2 Celeron
		memcpy()	ssememcpy()	mmxmemcpy()
check1	(dst+0, src+0)	1076 MB/s	1594 MB/s	1524 MB/s
check2	(dst+1, src+0)	473 MB/s	1580 MB/s	1400 MB/s
check3	(dst+0, src+1)	898 MB/s	1578 MB/s	1534 MB/s
check4	(dst+1, src+1)	709 MB/s	1600 MB/s	1288 MB/s
check5	(dst+3, src+2)	460 MB/s	1584 MB/s	1288 MB/s

※memcpy()は連載1-7回のデータをそのまま転載しています。

	パソコン2 Celeron
CPU	Intel Celeron 420 (Conroe-L) 1.6GHz Socket 775LGA
Chipset	i945G/GZ
Memory	DDR2, 1GB (single) read=3.3GB/s write=1.2GB/s
OS	Windows2000 Pro SP4
補足	デスクトップPC

mmxmemcpy()がmovntqを使ったメモリーコピー処理となり、メモリーのアライメントは一切そろえずひたすらmovqで読込んでmovntqで書き込んでいきます。

一方ssememcpy()は以前と同じものです。全ての条件でアライメントを揃えて処理しています。なお、memcpy()は今回データを取っていないので前回のものをそのまま記載しています。

全体的に見てmovntqは予想以上に良い結果となりました。アライメントが揃っているcheck1ではssememcpy()に肉薄していますし、書き込みのアライメントのみ揃っているcheck3でも肉薄しています。check2,4,5では恐らく書き込み側のアライメントが揃っていないためにパフォーマンスが低下していますが、memcpy()と比べるとパフォーマンスの低下は低く良好な結果だと思います。

 

最後になりますが、きっちりアライメントを揃えてからsseの専用命令を使うのがベストですが、sse命令が使えない、レジスターが足りない、プログラムをシンプルにしたいなどの理由からmmxを使った処理も十分検討に値すると思いました。

 

次回からは「コーデックを使った画像転送システム」を紹介いたします。ファンタジーリモートの心臓部とも言える重要な部分ですが実はとっても簡単です。コーデックに関するドキュメントなどググってもあまり出てこないのでその辺を意識した連載にしたいと思っています。

連載1 高速なメモリーコピー その７

今回はメモリーコピー編の最終回としてmemcpy()とSSE命令を使ったメモリーコピー処理の処理速度を比較します。

 

テスト方法はアライメントを揃えた128MBのバッファを2つ確保（バッファsrcとバッファdst）して、srcからdstに4MBずつコピーしていきます。128MBを超えたらまた0バイト目からコピーを続けて1秒間に何MBコピーできるかを測定。

また、アライメントをワザとずらしたパターンでもテストします。アライメントから1バイトずらした場合を”+1”、2バイトずらした場合を”+2”と表記しています。

尚、これらは全てシングルスレッドによる処理となります。

 

アライメント	パソコン1 Athlon		パソコン2 Celeron
	memcpy()	ssememcpy	memcpy()	ssememcpy()
パターン1 (dst+0, src+0)	888 MB/s	1442 MB/s	1076 MB/s	1554 MB/s
パターン3 (dst+1, src+0)	881 MB/s	1350 MB/s	473 MB/s	1554 MB/s
パターン3 (dst+0 src+1)	887 MB/s	1366 MB/s	898 MB/s	1522 MB/s
パターン2 (dst+1, src+1)	846 MB/s	1445 MB/s	709 MB/s	1554 MB/s
パターン3 (dst+3, src+2)	845 MB/s	1349 MB/s	460 MB/s	1554 MB/s

 

 

 

	パソコン1 Athlon	パソコン2 Celeron
CPU	Athlon64X2 4400+　2.2GHz Socket 939	Intel Celeron 420 (Conroe-L) 1.6GHz Socket 775LGA
Chipset	NVIDIA　nForce4	i945G/GZ
Memory	DDR400, 2GB(dual) read=3.6GB/s write=1.6GB/s	DDR2, 1GB (single) read=3.3GB/s write=1.2GB/s
OS	WindowsXP Pro SP2	Windows2000 Pro SP4
補足	デスクトップPC	デスクトップPC

※メモリーのread,writeはCrystalMark 0.9.114によるものです。

全体的に観てssememcpy()がmemcpy()より1.5～3倍程度高速であることが判ります。
また、Athlonではどのパターンのmemcpy()も差が少ないですが、Celeronではアライメントが揃っていないと処理速度が半分以下まで低下する場合があります。これはcore2duoでも同様の傾向がみられました（データを送ってくださった方ありがとうございました）。
それから、ssememcpy()に着目すると、Celeronの方はどのパターンもほぼ同じ結果ですが、AthlonではSSE命令の実行速度が遅いため演算処理を含むパターン3が若干遅くなっています。
Celeronの方はCrystalMarkの書き込みテスト以上の速度が出ているのが少し気になるところですが、それについては不明です。

以上で、メモリーコピー編は終わりです。

連載1 高速なメモリーコピー その６

今回はパターン3についてです。
コピー元：0x11111115
コピー先：0x22222229

の場合はとりあえずパターン2と同様に最初の11バイトをmemcpy()で処理して次のアドレスからメインの処理を開始します。
コピー元：0x11111120
コピー先：0x22222234

最初のmemcpy()でコピー元のアライメントが揃うので、読み込みは何も考えずにmovdqaで16バイトずつガンガン読込んでいきます。

問題は書き込みです。このままではアライメントが揃っていないのでmovntdqが使えません。そこで、読込んだ16バイトの内、12バイトだけを汎用命令のmovdquで書き込んで、残り4バイトはレジスターに残しておきます。こうすると、次の書き込みアドレスが0x22222240になるので、残りの4バイトと新しく読み込んだ16バイトの内の前方12バイトをレジスター上で合成してからmovntdqで書き込むことができます。

レジスターで合成する処理がちょっと面倒ですが、読み書き共にアライメントが揃うこの方法が私の知る限り最も効率良くメモリーコピーを行えます。

movdqa  xmm0, [esi+ 0];     movdqu  [esi+eax+ 0], xmm0;     add     eax, _SHIFT;     psrldq  xmm0, _SHIFT;   LB_SHIFT( MAIN ):     movdqa  xmm1, [esi+16];     movdqa  xmm3, [esi+32];     movdqa  xmm2, xmm1;     movdqa  xmm4, xmm3;     pslldq  xmm1, 16-_SHIFT;     psrldq  xmm2, _SHIFT;     pslldq  xmm3, 16-_SHIFT;     psrldq  xmm4, _SHIFT;     por     xmm1, xmm0;     por     xmm3, xmm2;     MOVNTDQ [esi+eax+ 0], xmm1;     MOVNTDQ [esi+eax+16], xmm3;       movdqa  xmm1, [esi+48];     movdqa  xmm3, [esi+64];     movdqa  xmm2, xmm1;     movdqa  xmm0, xmm3;     pslldq  xmm1, 16-_SHIFT;     psrldq  xmm2, _SHIFT;     pslldq  xmm3, 16-_SHIFT;     psrldq  xmm0, _SHIFT;     por     xmm1, xmm4;     por     xmm3, xmm2;     MOVNTDQ [esi+eax+32], xmm1;     MOVNTDQ [esi+eax+48], xmm3;       add     esi, 64;     loop    LB_SHIFT( MAIN );

_SHIFTはズレ量を示す定数です。

コピー元：0x11111115

コピー先：0x22222229

の場合の_SHIFTは12となります。これらをマクロにして、ズレ量が１の場合から15の場合の15種類を用意することでどんなアドレスの組み合わせが来ても対応できるようにします。

 

高速なメモリーコピーの紹介は以上です。高速処理はアライメントを揃えることが何より重要。最初からアライメントが揃っている場合や自分で管理出来るときは簡単。

アライメントが揃っている保証が無い場合は少々面倒でもアライメントを揃える工夫をするとプログラムは劇的に早くなるそんなことをメモリーコピーを通じて感じていただけらら幸いです。

次回はベンチマークテストを行って締めくくろうと思います。

連載1 高速なメモリーコピー その５

今回は自分でメモリーの管理が出来ずアライメントが揃っていない場合（たまたま揃っている場合も含みます）のメモリーコピー処理に付いてです。

メモリーコピー処理ではコピー元とコピー先の2つのメモリーが関係しますので、次の3パターンが考えられます。

 

パターン	アライメントの状態	処理
パターン1	コピー元とコピー先共にアライメントが揃っている。 例) コピー元：0x11111110 コピー先：0x22222220	前回のssememcpy1()を使う。
パターン2	コピー元とコピー先共にアライメントが揃っていないが、ズレている量が同じ。 例) コピー元：0x11111115 コピー先：0x22222225	ズレている量を端数としmemcpy()で処理、その後はパターン1と同じssememcpy1()を使う。
パターン3	コピー元とコピー先のズレ量が異なる。 例) コピー元：0x11111115 コピー先：0x22222229	汎用レジスターを使ってズレ量を吸収する。

今回からアライメントの“ズレ“と言う表現がでてきます。このズレとはアライメントからどれだけズレているかを示しますが具体的にはアドレスの下位4bitで判断し、下位4bitが同じ場合はズレ量が同じと見なします。パターン1は前回紹介したので、今回はパターン2です。

例の様にコピー元とコピー先のアドレスのうち下位4bitが2進数で0101(16進で5)と同じ場合がパターン2となり、この場合は最初の11バイトだけをmemcpy()を使って処理することで、残りは0x11111120から0x22222230へコピーする処理となります。残った部分はアライメントが揃っているのでパターン1と同様にssememcpy1()が使えます
続く．．．

連載1 高速なメモリーコピー その４

メモリーアライメントのそろえ方

 

void *p1 = malloc( size + 15 ); void *p2 = ((unsigned long)p + 15) & 0xFFFFFFF0;

 

まずは確保したいバッファサイズ（size）より15バイト多く確保してそのアドレスをp1とします。

p1のアドレスがどうなるかは環境に依存するらしいので16バイトの境界にあっているとは限りません。なのでこのままでは高速なSSE命令が使えないので二行目の計算を行って16バイトの境界に合わせます。

計算方法は15を足してから下位4bitをクリアするだけです。これでp2の先頭から処理することで高速なSSE命令を使えます。

ちなみに、次の関数を使うと最初からアライメントの揃ったバッファのアドレスを取得できるようです（実際に使ったことは有りませんが）。

void * _aligned_malloc(      size_t size,      size_t alignment ); ex) void *p3 = _aligned_malloc( size, 16 );

 

このように16バイトのアライメントに揃えたバッファ_srcから_dstに対して_sizeバイトコピーするSSE処理は次のようになります。

void ssememcpy1( void *_dst, void *_src, DWORD _size ) {     if (_size < 64) {         memcpy( _dst, _src, _size );         return ;     } __asm {     mov     esi, _src;     mov     eax, _dst;     sub     eax, esi;     mov     ecx, _size;     shr     ecx, 6;             // ecx = ecx / 64; LOOP_MAIN:     movdqa  xmm0, [esi+ 0];     movdqa  xmm1, [esi+16];     movdqa  xmm2, [esi+32];     movdqa  xmm3, [esi+48];     MOVNTDQ [esi+eax+ 0], xmm0;     MOVNTDQ [esi+eax+16], xmm1;     MOVNTDQ [esi+eax+32], xmm2;     MOVNTDQ [esi+eax+48], xmm3;     add     esi, 64;     loop    LOOP_MAIN;       add     eax, esi;     mov     _src, esi;     mov     _dst, eax; }     memcpy( _dst, _src, _size & 0x0000003F ); }

 

一回のループで64バイトずつコピーしていきます。　最初と最後に64バイト以下の端数の処理をmemcpy()を使って行います。

 

このように自分で管理するメモリー（自分で確保するメモリー）で高速な動作を求めるなら簡単に話が終わってしまうのですが、コーデックなどではアプリケーションやOSが確保したバッファを使って処理しなければいけない場面があり、その場合はアライメントが揃っている保証はありません。

したがって、上記の処理だけでは不十分なので、次回からは自分で管理できない場合について書いていきます。

連載1 高速なメモリーコピー その３

いよいよ最後のポイント、メモリーアライメントについてです。

メモリーには一定のバイト毎に区切りを示す境界がありまして、その区切りをまたぐ読み書きのアクセスを行うと大体半分くらいまで処理速度が低下してしまいます。
理由は判りませんが、何となく境界の前方と後方の両ブロックに対して処理しなければいけないとかそんなふうに私は理解しています。
また、SSE命令の場合は境界をまたいだアクセスが許されている命令と、アクセスが許されていない命令がありまして、許されていない命令で（境界をまたいだ）アクセスを行うとプログラムは強制終了されると言ったペナルティーまであります。

さらに、境界の間隔は命令（セット？）によって変わってきます。最初に示しましたmemcpy()の場合は2バイトか4バイト毎の境界となるようです（ちょっとどっちか判らないですが）、それに対してSSE命令は16バイト(128bit)毎と丁度レジスタのサイズと同じ間隔で境界が設定されています。

このような理由から高速な処理を行おうとした場合、どの命令を使うにしても結局アライメントは揃えないとベストな結果は得られないので、「高速なメモリーコピー処理」の肝は如何にしてアライメントをそろえるかと言う話に終始します。

アライメントさえ揃えてしまえば後は前回の「MOVDQAで128bit読み込んでちょこちょこっとやってMOVNTDQで書き込む」だけで簡単にベストな結果が得られます。
なんだそんなの簡単じゃんって思う方もいらっしゃると思いますが今回はここまで、続く．．．

「MOVNTQならアライメント制限なし」これはどうですか？とコメントを頂きました。

この命令はMMXレジスタを使ってメモリに書き込みを行う「書き込み専用命令」で、MOVNTDQと同様？にキャッシュを汚染しないのが特徴のようですね。
また、MMX全般に言えますがアライメントによる制限を受けずその点がMOVNTDQと異なるのでそこに利点があるかどうかでしょうか（って頂いたコメントのまんまですね＾＾

ちょっと比較したことが無いので結論は先送りさせていただきますが（今度AMV2コーデックを作るときに試してみようと思います）、エラーは出ないけど境界をまたいだ処理は遅くなるであろうという予測と、SSEレジスタを使った命令が全般的に高速化されていて、MMXを2命令使うよりSSEを1命令で済ませた方が速度面で期待できる（これはIntel系(core2duo以降？)のみです。
AMD系（Athlon64X2）ではMMXニ個とSSE一個がほぼ同じ時間で処理されるようです）という２点から見込みは薄いと思います。

連載1 高速なメモリーコピー その２

「キャッシュの制御もポイントの一つ」と言うコメントをいただきました。
確かにキャッシュの制御も超重要なポイントとなりますね。ありがとう御座います。という事で、ポイントは一つ増えて３つです。

・SSE命令を使う
・メモリーアライメントを制御する
・キャッシュを制御する

で、最初のSSE命令ですが私が扱えるSSE2命令までだと次の3つがあります。

命令	読み・書き	アライメント	備考
MOVDQU	両方可	そろえる必要なし	制限のゆるい汎用命令。
MOVDQA	両方可	そろえる必要あり	アライメントの制限がある代わりに早いらしい。
MOVNTDQ	書き込みのみ可	そろえる必要あり	アライメント制限に加え、書き込みのみの専用命令。

    
何れも128bitを一度に処理できますが、制限が厳しいものほど高速に動作するらしいです。厳密なデータは取っていませんが、私のAthlon64X2だと、MOVDQUをMOVDQAに代えてもあまり効果は得られない印象ですが、MOVDQAの書き込みをMOVNTDQに代えると30%くらいは早くなった気がします。
なので、「MOVDQAで128bit読み込んで、MOVNTDQで書き込む」というのを繰り返していくのが理想となります。

但し、この2つの命令はメモリーアライメントの制約がありまして、単純にmemcpyの代わりにはなってもらえません。

また、MOVNTDQが高速な理由と言うのが、「キャッシュを使わずに書き込みを行う※」という事らしいので早速3つ目のポイントも出てきます。

メモリーアライメントについては次回書くとして、キャッシュ制御について先に書いちゃいますね。

キャッシュ制御には読み込みを高速化するプリフェッチ（先読み）と、上記の様に書き込みを高速化するものがあります。
そこで、読み書き両方を高速化したらベストなのかなと考えますが、どうも違うようです。理由は現在のパソコンの事情から読み込み処理より書き込み処理の方が時間がかかる（ハードウエアの都合で理論上2倍の時間がかかるのかな、この辺は自信がありませんがベンチマークテストすると大体2倍くらい違いますよね）ので、プリフェッチにより読み込みを高速化しても書き込み処理が追いつかず、結局読込み処理は（書き込み処理が終わるまで）待たされてしまうことになるからです。

いきなり結論になってしまいますが、私は書き込み速度で頭打ちされているなと感じたので結局メモリーコピーでプリフェッチは行わないことにしました。

ちなみに、プリフェッチは書き込みよりも読み込みに負担がかかるハーフサイズ処理で大きな効果がありました（Athlonの場合だけの高速化、且つ、アライメントの問題で結局アマレココには採用しませんでしたが）。
続く．．．

※キャッシュの汚染を最小にとどめる・・・と言う解説なので、キャッシュを絶対に使わないってわけではないかもしれません。キャッシュの事は気にしないで書き込みだけなら誰にも負けない高速な命令と私は理解しています。

連載1 高速なメモリーコピー その１

私はC言語でプログラムを開発していてmemcpy()関数を使うことが多く、この関数は次のようなアセンブラに展開されるようです。

1:     mov     ecx, dword ptr [ebp+10h] 2:     mov     esi, dword ptr [ebp+0Ch] 3:     mov     edi, dword ptr [ebp+8] 4:     mov     eax, ecx 5:     shr     ecx, 2 6:     rep     movs dword ptr [edi], dword ptr [esi] 7:     mov     ecx, eax 8:     and     ecx, 3 9:     rep     movs byte ptr [edi], byte ptr [esi]

これは4Byte (32bit)ずつコピーしていって、4Byte未満の端数が出たら1Byteずつコピーしています。アセンブラのコードを見る限り無駄もなく安心して使える関数ですが処理速度の点ではもう少し向上させることが出来ます。

ポイントは2つ、一つ目は今のCPUならSSE命令を使って16Byte(128bit)ずつコピーできる点、そしてもう一つはメモリーアライメントを考慮することです。

続く．．．