処理が異常に遅い原因はわかりますか？

Question

久しぶりに、(perlのXSのために）C言語を組んでみましたが、
以下のコードが、異常に遅いようでした。

（実際には、違う処理ですが、これでも遅くなりましたので、単なる文字コピーです）

例えでいえば、同じことをする数文字のperlの正規表現処理の数１００倍の時間がかかっていました。

void hoge(char *dst, char *src, int len) {
inti;
for(i = 0; i < len; i++) {
*dst++=*src++;/* ここをなくすと、爆速になる */
}
}

※strlenで当初は試していましたが、ほとんどかわりありません。

どこが、原因でしょうか？

以下のコードは、きちんと爆速で動作してくれます。

void hoge(char *dst, char *src) {
for(; *dst++ = *src++;);
}

コンパイルオプションは
gcc -O2
または
gcc -O3
で、CPUは、x86_64でなっています。(AMD FX-4170)

処理した文字列は、約１００Mバイト分になります。

宜しくお願いします。

nissii202 · Accepted Answer

No.5の補足です。

各CPU向けの最適化について、VC++10のmemcpyについて言えば
CPUがSSE2をサポートしており、コピー元とコピー先のメモリアライメントが
16バイトで揃っていればSSE命令を利用し、それ以外でもストリング命令による
コピーが行われるなど単純にジャンプ命令でループしながらコピーするよりも
高速にメモリ転送が行われるように出来ています。
私の環境ではSSE2を使っても使わなくても0.5秒以下くらいでした。

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
CopyUp:
;
; First, see if we can use a "fast" copy SSE2 routine
        ; block size greater than min threshold?
        cmp     ecx,080h
        jb      Dword_align
        ; SSE2 supported?
        cmp     DWORD PTR __sse2_available,0
        je      Dword_align
        ; alignments equal?
        push    edi
        push    esi
        and     edi,15
        and     esi,15
        cmp     edi,esi
        pop     esi
        pop     edi
        jne     Dword_align

; do fast SSE2 copy, params already set
        jmp     _VEC_memcpy
        ; no return
;
; The algorithm for forward moves is to align the destination to a dword
; boundary and so we can move dwords with an aligned destination.  This
; occurs in 3 steps.
;
;   - move x = ((4 - Dest & 3) & 3) bytes
;   - move y = ((L-x) >> 2) dwords
;   - move (L - x - y*4) bytes
;

Dword_align:
        test    edi,11b         ;U - destination dword aligned?
        jnz     short CopyLeadUp ;V - if we are not dword aligned already, align

shr     ecx,2           ;U - shift down to dword count
        and     edx,11b         ;V - trailing byte count

cmp     ecx,8           ;U - test if small enough for unwind copy
        jb      short CopyUnwindUp ;V - if so, then jump

rep     movsd           ;N - move all of our dwords

jmp     dword ptr TrailUpVec[edx*4] ;N - process trailing bytes
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

nissii202 · Answer

ymda さんコード提供ありがとうございます。

gcc4.2 -O3だとインデックス参照になっていて、llvm-gccだと内側のループが
memcpyになっており外側のループがカウントダウンになっています。
llvm-gccだと、最適化でかなりコードが書き換えられているようです。

memcpyはコンパイラによっては、自作関数より遅いことがあるそうですが、
大抵は各CPU向けの最適化が施されており速くなるように作られています。

インテルとかのコンパイラは各CPU向けの最適化が行われるので速く
gccは多様な環境に対応することを第一として設計されているので
個別のCPU向けの最適化はあまりないようです。
結局コンパイラ次第ってことですかね…

nissii202 · Answer

No.2 さんのアセンブラ出力を見る限り、
func1はd++やs++をせずにiによるインデックス参照になっており、
func2はループ自体回らず何もせずreturnするようになっており、
func3はソースコード通りのポインタ直参照となっております。
なので、func1よりfunc3の方が速くfunc2は何もしていないので
爆速かと思われます。
あと、fun1のcmpl %eax, %edxよりもfunc2のtestb %al, %alの方が
若干速いと思われるのでそのあたりも関係があるかもしれません。

ymda さんの環境で出力したアセンブラコードがあればもう少し
詳しく分かるかもしれません。

SherlockHolmes2 · Answer

私はx86系のアセンブラは読めないので、見当違いでしたらスミマセン。

strncpyでコピーしてみてはどうでしょう？

wormhole · Answer

＞例えでいえば、同じことをする数文字のperlの正規表現処理の数１００倍の時間がかかっていました。

正規表現そのものには文字列コピーのような機能はないですけど具体的にはどんな処理なんでしょう？

またgccのバージョンも書かれた方がよいかと思います。
FreeBSD 9のgcc 4.7.3だと

void func1(char *d, char *s, int n)
{
  for (int i = 0; i < n; i++) {
    *d++ = *s++;
  }
}

void func2(char *d, char *s, int n)
{
  for (int i = 0; i < n; i++) {
  }
}

void func3(char *d, char *s)
{
  for (;*d++ = *s++;) {
  }
}

で出力されるコードはこんな感じです。

.text
        .p2align 4,,15
        .globl  func1
        .type   func1, @function
func1:
.LFB0:
        .cfi_startproc
        xorl    %eax, %eax
        testl   %edx, %edx
        jle     .L1
        .p2align 4,,10
.L5:
        movzbl  (%rsi,%rax), %ecx
        movb    %cl, (%rdi,%rax)
        addq    $1, %rax
        cmpl    %eax, %edx
        jg      .L5
.L1:
        rep
        ret
        .cfi_endproc
.LFE0:
        .size   func1, .-func1
        .p2align 4,,15
        .globl  func2
        .type   func2, @function
func2:
.LFB1:
        .cfi_startproc
        rep
        ret
        .cfi_endproc
.LFE1:
        .size   func2, .-func2
        .p2align 4,,15
        .globl  func3
        .type   func3, @function
func3:
.LFB2:
        .cfi_startproc
        .p2align 4,,10
.L10:
        movzbl  (%rsi), %eax
        addq    $1, %rsi
        movb    %al, (%rdi)
        addq    $1, %rdi
        testb   %al, %al
        jne     .L10
        rep
        ret
        .cfi_endproc
.LFE2:
        .size   func3, .-func3

ほぼ#1の方のおっしゃってる通りですね。

TooManyBugs · Answer

gccがどのようなオブジェクトを出すのか解りませんが。

>for(i = 0; i < len; i++) {
>　/*　*dst++=*src++;　ここをなくすと、爆速になる */
>}
この後でiを参照していなければ最適化で空のForループなので無くなっている、或いは i =len;に置換されている事が考えられます。

>for(; *dst++ = *src++;);
一旦ポインタをセットすればレジスタ操作のみになるので比較的高速動作すると思われます。

>for(i = 0; i < len; i++) {
>*dst++=*src++;　
>}

iのインクリメント、lenとの比較が付加されますからステップ数で数倍になります。
i,Lenをレジスタ上に持たなければ動作速度では数十倍になると思われます。

考えるよりアセンブリリストを出して比較すれば一目瞭然ですね。

処理が異常に遅い原因はわかりますか？

No.5の補足です。

ymda さんコード提供ありがとうございます。

No.2 さんのアセンブラ出力を見る限り、

この回答への補足

私はx86系のアセンブラは読めないので、見当違いでしたらスミマセン。

＞例えでいえば、同じことをする数文字のperlの正規表現処理の数１００倍の時間がかかっていました。

gccがどのようなオブジェクトを出すのか解りませんが。

似たような質問が見つかりました

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング