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

質問

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

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

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

void hoge(char *dst, char *src, int len) {
int i;
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バイト分になります。

宜しくお願いします。

回答No.6

nissii202 · ベストアンサー

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
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

回答No.5

nissii202

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

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

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

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

回答No.4

nissii202

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

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

お礼

ありがとうございます。

他のコンパイラ（バージョン）も出してみました。

しかし、下のやりすぎて処理は消えている以外は、それなりに時間がかかる処理ですので、かかるのは当然ですが
（とはいっても、0.5秒もかかりません）
その処理が、gcc4.2 (-O3)ですと、20秒以上待たされるようです。

ちなみに、どのコンパイラも、-Oなしですと、20秒以上待たされる程激遅になるのは、確かなようです。

# ↓だけは、さすがに、0.0秒です。
/********* gcc4.8 -O3 （やりすぎて処理が消えている）
.file "test.c"
.section .text.startup,"ax",@progbits
.p2align 4,,15
.globl main
.type main, @function
main:
.LFB0:
.cfi_startproc
rep; ret
.cfi_endproc
.LFE0:
.size main, .-main
.ident "GCC: (FreeBSD Ports Collection) 4.8.0 20120930 (experimental)"
.section .note.GNU-stack,"",@progbits

/********* gcc4.8 -O3 fputcを追加
.file "test.c"
.section .text.startup,"ax",@progbits
.p2align 4,,15
.globl main
.type main, @function
main:
.LFB0:
.cfi_startproc
pushq %r13
.cfi_def_cfa_offset 16
.cfi_offset 13, -16
movl $100000, %edi
movl $100000, %r13d
pushq %r12
.cfi_def_cfa_offset 24
.cfi_offset 12, -24
pushq %rbp
.cfi_def_cfa_offset 32
.cfi_offset 6, -32
pushq %rbx
.cfi_def_cfa_offset 40
.cfi_offset 3, -40
subq $8, %rsp
.cfi_def_cfa_offset 48
call malloc
movl $100000, %edi
movq %rax, %rbp
call malloc
movq %rax, %r12
.p2align 4,,10
.L2:
xorl %ebx, %ebx
.p2align 4,,10
.L5:
movl $97, %edi
call fputc
movzbl (%r12,%rbx), %edx
movb %dl, 0(%rbp,%rbx)
addq $1, %rbx
cmpq $100000, %rbx
jne .L5
subl $1, %r13d
jne .L2
addq $8, %rsp
.cfi_def_cfa_offset 40
popq %rbx
.cfi_def_cfa_offset 32
popq %rbp
.cfi_def_cfa_offset 24
popq %r12
.cfi_def_cfa_offset 16
popq %r13
.cfi_def_cfa_offset 8
ret
.cfi_endproc
.LFE0:
.size main, .-main
.ident "GCC: (FreeBSD Ports Collection) 4.8.0 20120930 (experimental)"
.section .note.GNU-stack,"",@progbits

補足

/********* 書き直したソース

#define AA 100000
#include <stdlib.h>

int main(void) {
int i,j;
int len=AA;
char *dst,*savedst;
char *src,*savesrc;

dst=malloc(AA);
src=malloc(AA);
savesrc=src;
savedst=dst;
for(j = 0; j < AA; j++) {
src=savesrc;
dst=savedst;
for(i = 0; i < len; i++) {
//fputc('a');
*dst++=*src++;
}
}
}

/********* gcc4.2 -O3 (-O2も全く同じ）
.file "test.c"
.text
.p2align 4,,15
.globl main
.type main, @function
main:
.LFB2:
pushq %rbx
.LCFI0:
movl $100000, %edi
call malloc
movl $100000, %edi
movq %rax, %rbx
call malloc
xorl %esi, %esi
movq %rax, %rcx
.L2:
xorl %edx, %edx
.p2align 4,,7
.L3:
movzbl (%rdx,%rcx), %eax
movb %al, (%rdx,%rbx)
addq $1, %rdx
cmpq $100000, %rdx
jne .L3
addl $1, %esi
cmpl $100000, %esi
jne .L2
popq %rbx
ret
.LFE2:
.size main, .-main
.section .eh_frame,"a",@progbits
.Lframe1:
.long .LECIE1-.LSCIE1
.LSCIE1:
.long 0x0
.byte 0x1
.string "zR"
.uleb128 0x1
.sleb128 -8
.byte 0x10
.uleb128 0x1
.byte 0x3
.byte 0xc
.uleb128 0x7
.uleb128 0x8
.byte 0x90
.uleb128 0x1
.align 8
.LECIE1:
.LSFDE1:
.long .LEFDE1-.LASFDE1
.LASFDE1:
.long .LASFDE1-.Lframe1
.long .LFB2
.long .LFE2-.LFB2
.uleb128 0x0
.byte 0x4
.long .LCFI0-.LFB2
.byte 0xe
.uleb128 0x10
.byte 0x83
.uleb128 0x2
.align 8
.LEFDE1:
.ident "GCC: (GNU) 4.2.1 20070831 patched [FreeBSD]"
.section .note.GNU-stack,"",@progbits

/********* llvm-gcc
.file "test.c"
.text
.globl main
.align 16, 0x90
.type main,@function
main:
.Leh_func_begin0:
pushq %r15
.Ltmp0:
pushq %r14
.Ltmp1:
pushq %rbx
.Ltmp2:
.Ltmp3:
movl $100000, %edi
callq malloc
movq %rax, %rbx
movl $100000, %edi
callq malloc
movl $100000, %r14d
movq %rax, %r15
.align 16, 0x90
.LBB0_1:
movq %rbx, %rdi
movq %r15, %rsi
movl $100000, %edx
callq memcpy
decl %r14d
jne .LBB0_1
popq %rbx
popq %r14
popq %r15
ret
.Ltmp4:
.size main, .Ltmp4-main
.Leh_func_end0:

.section .eh_frame,"a",@progbits
.LEH_frame0:
.Lsection_eh_frame0:
.Leh_frame_common0:
.Lset0 = .Leh_frame_common_end0-.Leh_frame_common_begin0
.long .Lset0
.Leh_frame_common_begin0:
.long 0
.byte 1
.asciz "zR"
.byte 1
.byte 120
.byte 16
.byte 1
.byte 3
.byte 12
.byte 7
.byte 8
.byte 144
.byte 1
.align 8
.Leh_frame_common_end0:
.Lmain.eh:
.Lset1 = .Leh_frame_end0-.Leh_frame_begin0
.long .Lset1
.Leh_frame_begin0:
.Lset2 = .Leh_frame_begin0-.Leh_frame_common0
.long .Lset2
.long .Leh_func_begin0
.Lset3 = .Leh_func_end0-.Leh_func_begin0
.long .Lset3
.byte 0
.byte 4
.Lset4 = .Ltmp0-.Leh_func_begin0
.long .Lset4
.byte 14
.byte 16
.byte 4
.Lset5 = .Ltmp1-.Ltmp0
.long .Lset5
.byte 14
.byte 24
.byte 4
.Lset6 = .Ltmp2-.Ltmp1
.long .Lset6
.byte 14
.byte 32
.byte 4
.Lset7 = .Ltmp3-.Ltmp2
.long .Lset7
.byte 131
.byte 4
.byte 142
.byte 3
.byte 143
.byte 2
.align 8
.Leh_frame_end0:

.section ".note.GNU-stack","",@progbits
.ident "GCC: (GNU) 4.2.1 (Based on Apple Inc. build 5658) (LLVM build)"

回答No.3

SherlockHolmes2

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

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

お礼

ありがとうございます。

これは、あくまで、ルーチンの一部を掲載したもので
実際は、余裕で標準ライブラリで処理できないものです。

回答No.2

wormhole

＞例えでいえば、同じことをする数文字の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の方のおっしゃってる通りですね。

お礼

ありがとうございます。

アセンブラリストを出してから、時間とれなくなってしまいました。。汗

FreeBSDのシステムコンパイラ gcc4.2ですと、-O2でも-O3でも
この回答の2倍以上程度のコードになってしまっているようですが、
gcc4.8、4.7.3を試したら、それなりの速度に戻ってくれました。

また、わずかながら、gccよりもllvm-gccのが速い感じもしています。

回答No.1

TooManyBugs

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をレジスタ上に持たなければ動作速度では数十倍になると思われます。

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

お礼

ありがとうございます。
回答遅くなり申し訳ありません。