J

2004 | 08 | 09 | 10 | 11 | 12 |
2005 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2006 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 12 |
2008 | 01 | 02 | 04 | 10 | 11 | 12 |
2009 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2011 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2012 | 01 | 03 | 04 | 05 | 06 | 07 | 08 | 12 |
2013 | 01 | 02 | 03 | 05 | 06 | 07 | 08 | 09 | 10 | 11 |
2014 | 01 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2015 | 02 | 03 | 04 | 05 | 06 | 07 | 10 | 11 | 12 |
2016 | 01 | 02 | 04 | 05 | 06 | 07 | 09 | 11 | 12 |
2017 | 01 | 02 | 03 | 05 | 06 | 07 | 08 | 09 |

ホーム

日記内の"morihyphen.hp.infoseek.co.jp"へのリンクは切れてます。必要な場合はお手数ですが int.main.jp へ書き換えをお願いします。

TODO: ファイル名確認を忘れないこと > 自分

twitter

 | 

2015-04-23

みんな意外とauto vectorizationとか信用してて愕然とする 16:50

http://d.hatena.ne.jp/shi3z/20150422/1429659958

の反論見てると、「いまどきはコンパイラSIMDにしてくれるし」みたいなのがそれなりにあるのだけど、僕は基本的に自動ベクトル化とか信用していないので、私は考えが古い人間なのかと思って結構ショックだった。

(機械語知ってればデバッグ技の幅がかなり広がるので、可能なら機械語まで知っておいたほうがいいというのには大体同意できる。その話はまた気が向いたら…)


以下、自動SIMD化を信用できない理由について書いておく。

遅くなる場合がある

まだプロファイルフィードバック技術が完成していない現代では、コンパイラがループ回数わからないから、3回とか7回のループだと遅くなる場合があるんだよな。

#include <x86intrin.h>
#include <stdio.h>

void __attribute__((noinline,noclone))
f(int *p, int *q, int n)
{
    int i;
    for (i=0; i<n; i++) {
        p[i] += q[i];
    }
}

int a[7];
int b[7];

int
main()
{
    int t0, t1, i;
    for (i=0; i<10000000; i++) {
        f(a, b, 7);
    }
}
$ gcc -O2 vec.c  
$ perf stat ./a.out 

 Performance counter stats for './a.out':

         55.615946      task-clock (msec)         #    0.997 CPUs utilized          
                 3      context-switches          #    0.054 K/sec                  
                 0      cpu-migrations            #    0.000 K/sec                  
                47      page-faults               #    0.845 K/sec                  
       151,202,534      cycles                    #    2.719 GHz                    
   <not supported>      stalled-cycles-frontend  
   <not supported>      stalled-cycles-backend   
       460,530,894      instructions              #    3.05  insns per cycle        
       110,101,691      branches                  # 1979.678 M/sec                  
             4,898      branch-misses             #    0.00% of all branches        

       0.055802920 seconds time elapsed

$ gcc -O3 vec.c  
$ perf stat ./a.out 

 Performance counter stats for './a.out':

         71.496307      task-clock (msec)         #    0.997 CPUs utilized          
                 1      context-switches          #    0.014 K/sec                  
                 0      cpu-migrations            #    0.000 K/sec                  
                47      page-faults               #    0.657 K/sec                  
       184,097,523      cycles                    #    2.575 GHz                    
   <not supported>      stalled-cycles-frontend  
   <not supported>      stalled-cycles-backend   
       560,549,898      instructions              #    3.04  insns per cycle        
       130,104,201      branches                  # 1819.733 M/sec                  
             4,710      branch-misses             #    0.00% of all branches        

       0.071746861 seconds time elapsed

cycles instructions
-O2(自動SIMD無し) 151,202,534 460,530,894
-O3(自動SIMD有り) 184,097,523 560,549,898
-O3/-O2 121.8 [%] 121.7 [%]

まあ、これは結構弱点突いてるが、それでも、経験的に小さいループをそれなりに含む巨大なプログラムを -O3 でコンパイルすると遅くなったりほとんど変わらなかったりする場合が大半なように思う。


あと出てるコード見ると

f:
.LFB2469:
	.cfi_startproc
	testl	%edx, %edx
	jle	.L29
	leaq	16(%rdi), %rax
	cmpq	%rax, %rsi
	leaq	16(%rsi), %rax
	setae	%cl
	cmpq	%rax, %rdi
	setae	%al
	orb	%al, %cl
	je	.L12
	cmpl	$8, %edx
	jbe	.L12
	movq	%rdi, %rax
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	pushq	%rbx
	.cfi_def_cfa_offset 24
	.cfi_offset 3, -24
	andl	$15, %eax
	shrq	$2, %rax
	negq	%rax
	andl	$3, %eax
	cmpl	%eax, %edx
	cmovbe	%edx, %eax
	xorl	%ecx, %ecx
	testl	%eax, %eax
	je	.L4
	movl	(%rsi), %ecx
	addl	%ecx, (%rdi)
	cmpl	$1, %eax
	movl	$1, %ecx
	je	.L4
	movl	4(%rsi), %ecx
	addl	%ecx, 4(%rdi)
	cmpl	$3, %eax
	movl	$2, %ecx
	jne	.L4
	movl	8(%rsi), %ecx
	addl	%ecx, 8(%rdi)
	movl	$3, %ecx
.L4:
	movl	%edx, %r11d
	xorl	%r8d, %r8d
	xorl	%r10d, %r10d
	subl	%eax, %r11d
	movl	%eax, %eax
	leal	-4(%r11), %r9d
	salq	$2, %rax
	leaq	(%rdi,%rax), %rbx
	addq	%rsi, %rax
	shrl	$2, %r9d
	addl	$1, %r9d
	leal	0(,%r9,4), %ebp
.L6:
	movdqu	(%rax,%r8), %xmm0
	addl	$1, %r10d
	paddd	(%rbx,%r8), %xmm0
	movaps	%xmm0, (%rbx,%r8)
	addq	$16, %r8
	cmpl	%r9d, %r10d
	jb	.L6
	addl	%ebp, %ecx
	cmpl	%ebp, %r11d
	je	.L1
	movslq	%ecx, %rax
	movl	(%rsi,%rax,4), %r8d
	addl	%r8d, (%rdi,%rax,4)
	leal	1(%rcx), %eax
	cmpl	%eax, %edx
	jle	.L1
	cltq
	addl	$2, %ecx
	movl	(%rsi,%rax,4), %r8d
	addl	%r8d, (%rdi,%rax,4)
	cmpl	%ecx, %edx
	jle	.L1
	movslq	%ecx, %rax
	movl	(%rsi,%rax,4), %edx
	addl	%edx, (%rdi,%rax,4)
.L1:
	popq	%rbx
	.cfi_restore 3
	.cfi_def_cfa_offset 16
	popq	%rbp
	.cfi_restore 6
	.cfi_def_cfa_offset 8
.L29:
	rep ret
	.p2align 4,,10
	.p2align 3
.L12:
	xorl	%eax, %eax
	.p2align 4,,10
	.p2align 3
.L3:
	movl	(%rsi,%rax,4), %ecx
	addl	%ecx, (%rdi,%rax,4)
	addq	$1, %rax
	cmpl	%eax, %edx
	jg	.L3
	rep ret

結構「うっ…」っていう気分になるんだよね。


-O2 は↓このぐらい

f:
.LFB2493:
	.cfi_startproc
	xorl	%eax, %eax
	testl	%edx, %edx
	jle	.L1
	.p2align 4,,10
	.p2align 3
.L5:
	movl	(%rsi,%rax,4), %ecx
	addl	%ecx, (%rdi,%rax,4)
	addq	$1, %rax
	cmpl	%eax, %edx
	jg	.L5

何故こうなるかというと、

  • SIMDにすると4とか8の倍数でないと処理できなくなるので端数の処理が入る
  • p と q がオーバーラップしてるとSIMD化できないので p と q がオーバーラップしてるかどうか判定する処理が入る

というのがあって、プロファイルフィードバックが完成されるまでは原理的に回避不可能なのでコンパイラは悪くないんですよ。


(ここでJavaなら実行時情報が取れるからさらに最適化できる可能性がある説選手の登場だあ!プロファイルコードのオーバーヘッドがあるから、プロファイル取ることによって遅くなる可能性も増えてることを忘れないでほしい)


結局SIMD化されてるか確認しないといけない

どのコンパイラのバージョンで、どの関数がSIMD化されるか確認しはじめたら、それなりの作業になるから、もうそこまでやるなら手でintrinsics書いたほうが速いのだった。


たとえば、

void __attribute__((noinline,noclone))
f(int *p, int *q, int n)
{
    int i;
    for (i=0; i<n; i++) {
        int x = p[i];
        if (x == q[i]) {
            x += 4;
        }

        p[i] = x;
    }
}

void __attribute__((noinline,noclone))
g(int *p, int *q, int n)
{
    int i;
    for (i=0; i<n; i++) {
        if (p[i] == q[i]) {
            p[i]+=4;
        }
    }
}

このふたつのプログラム、同じように見えるが、g() のほうは、f()と比べると命令セットによっては自動SIMD化はかなり難しい。これは、p が readonly memory で、書き込みアクセス時に SEGV が飛ぶような状態になっていると、自動SIMD化によって意味が変わってしまうからだ。(今のSSEはpmaskmovdがあるからできる)


これを理解するには、対象プログラム、C言語、対象命令セット、コンパイラの挙動まできっちり理解していないといけない。そこまで理解してるなら、手でintrinsics書くのもそんな難しくないでしょ…


そして、これらが理解できてないと、うまく自動SIMDされないときに「なんだこのクソコンパイラ」とか言ってしまうのだ。おお…かわいそうに…コンパイラは悪くないのだ…。


現代の SIMD は正確には SIMD(Single Instruction Multiple Data) ではない

よく聞くフレーズに、「ポータブルなCで書いて、SIMD化はコンパイラにまかせて性能と移植性を両立!ワークライフバランス!」みたいなのがあるが、あれ聞くたびに「お前まじめにSIMD書いたことあんの?」とか問い詰めたくなってしまうのだった。


真面目にSIMD書くなら、かなり高い確率でシャッフル系の命令を使うと思う。シャッフル命令は、実際にはSIMD命令ではない。128bitのデータを入力として、128bitのデータを出力する、つまり、一個のデータを受け取って、一個のデータを出力する命令なのである。


これはどういうことかというと、128bitデータが定義されてるとは限らないC言語では、シャッフルは表現できない可能性が高いということだ(まあ配列使って表現するだけならできるが…)。シャッフルの使用頻度を考えると、シャッフル無しでSIMDを使うのは、かなりきつい縛りだと思われる。


他にも、水平演算みたいにC言語では表現が難しい命令はいくつかある。まあx86の水平演算は無くてもあんま困らない感じがあるが…


まとめ

まあでも、別に自動SIMDが必要無いと思ってるわけではなくて、-O2 を -O3 に変えるだけでできるのだから、ちょっと試して効果あったら採用とかでも別に良いのではないかと思う。

musokanmusokan 2015/04/24 05:58  うーんと、shi3z氏の元記事もそうなのですが、
2進数の集まりであるマシン語(機械語)と
アセンブラーを混同しておられるのがちょっと
気になりました。自動ベクトル化が信用できない
という記事の内容については同意です。

w_ow_o 2015/04/24 13:21 上で書いてる「機械語」は、機械語のつもりで書いてます。つまり、メモリに命令がどう展開されるか知ってたほうが嬉しい場面が多いという気持ちを込めて書いてます。
まあどっちか片方だけ理解するという人もいないと思うのでこういう文脈ではあんまり気にしないでよいと思いますが…

YSRYSR 2015/06/26 22:55 あの、シャッフル命令全然使ったことないんですけど、やっぱダメなんですかね……?
(自動SIMD・並列化がアレなのと水平計算があまり使えないのは同意)

w_ow_o 2015/06/27 13:18 分野によってはあんま使わないという人もいるかもしれないです。

トラックバック - http://d.hatena.ne.jp/w_o/20150423
 |