std::vectorと動的確保配列の比較

id:shibacho:20040719

これも、自分でアセンブラコードを見て検証したわけではないというのが我ながらダメだと思うが

それじゃ私がやっておきます。
サンプルにしたのは以下のコード。

#include 
const int BUFFERSIZE = 1000;

int search_vector(int target) {
  std::vector buffer(BUFFERSIZE);
  int result = -1;
  
  for (int index = 0; index < BUFFERSIZE; index++)
    if (buffer[index] == target)
    {
      result = index;
      break;
    }

  return result;
}

int search_array(int target) {
  int* buffer = new int[BUFFERSIZE];
  int result = -1;
  
  for (int index = 0; index < BUFFERSIZE; index++)
    buffer[index] = 0;

  for (int index = 0; index < BUFFERSIZE; index++)
    if (buffer[index] == target)
      result = index;

  delete [] buffer;
  return result;
}

コンパイラーとコンパイルオプションは以下の通り。
無駄なオプション沢山ついているけれど無視して下さい。

$ /usr/local/bin/g++-3.5.0 -v
Reading specs from /usr/local/lib/gcc/i686-pc-linux-gnu/3.5.0/specs
Configured with: ./configure --enable-languages=c,c++,java 
 --program-suffix=-3.5.0 --enable-java-awt=xlib,gtk --enable-java-gc=boehm  
 --enable-system-zlib --enable-libgcj
Thread model: posix
gcc version 3.5.0 20040718 (experimental)

$ /usr/local/bin/g++-3.5.0 -O3 -march=athlon-xp -freduce-all-givs 
 -fmove-all-movables -malign-double -maccumulate-outgoing-args 
 -minline-all-stringops -momit-leaf-frame-pointer -mmmx -msse -mfpmath=sse 
 -fomit-frame-pointer  -ftree-based-profiling -ftree-ccp -ftree-ch 
 -ftree-combine-temps -ftree-copyrename -ftree-dce -ftree-dominator-opts
 -ftree-dse -ftree-lrs -ftree-pre -ftree-sra -ftree-ter -S

吐き出されたコードより主要な部分を抽出し、簡単に整形した結果は以下の通り。
search_vectorの.L141当たり、search_arrayの.L4当たりが問題のループ部分です。

_Z13search_vectori:
	pushl	%ebp
	movl	%esp, %ebp
	pushl	%edi
	leal	-40(%ebp), %edi
	pushl	%esi
	pushl	%ebx
	subl	$60, %esp
	movl	$0, -40(%ebp)
	movl	8(%ebp), %esi
	movl	$0, -36(%ebp)
	movl	$0, -32(%ebp)
	movl	$0, 8(%esp)
	movl	$1000, 4(%esp)
	movl	%edi, (%esp)
	call	_ZN9__gnu_cxx10__mt_allocIiE8allocateEjPKv
	movl	%eax, (%edi)
	movl	-40(%ebp), %ecx
	movl	%eax, %ebx
	movl	%eax, 4(%edi)
	leal	4000(%eax), %eax
	movl	$1000, %edx
	movl	%eax, -44(%ebp)
	movl	%eax, 8(%edi)
	movl	%ecx, %eax

.L139:
	movl	$0, (%eax)
	addl	$4, %eax
	decl	%edx
	jne	.L139

	leal	4000(%ecx), %eax
	xorl	%edx, %edx
	movl	%eax, -36(%ebp)
	movl	%ecx, %eax

.L141:
	cmpl	%esi, (%eax)
	je	.L151
	incl	%edx
	addl	$4, %eax
	cmpl	$999, %edx
	jle	.L141

	movl	$-1, %esi
	movl	-44(%ebp), %eax
	subl	%ebx, %eax
	sarl	$2, %eax

	testl	%ebx, %ebx
	je	.L146
	movl	%eax, 8(%esp)
	movl	%ebx, 4(%esp)
	movl	%edi, (%esp)
	call	_ZN9__gnu_cxx10__mt_allocIiE10deallocateEPij
.L146:

	addl	$60, %esp
	movl	%esi, %eax
	popl	%ebx
	popl	%esi
	popl	%edi
	leave
	ret

_Z12search_arrayi:
	pushl	%ebp
	movl	%esp, %ebp
	pushl	%edi
	pushl	%esi
	pushl	%ebx
	subl	$12, %esp
	movl	$4000, (%esp)
	call	_Znaj
	leal	3996(%eax), %ecx
	movl	%eax, %edi
	movl	%eax, %edx

.L2:
	addl	$4, %edx
	movl	$0, (%eax)
	addl	$4, %eax
	cmpl	%ecx, %edx
	jle	.L2

	movl	$-1, %esi
	xorl	%ebx, %ebx
	xorl	%ecx, %ecx
	movl	%edi, %edx

.L4:
	movl	(%edx), %eax
	cmpl	8(%ebp), %eax
	cmove	%ecx, %esi
	incl	%ebx
	incl	%ecx
	addl	$4, %edx
	cmpl	$999, %ebx
	jle	.L4

	testl	%edi, %edi
	je	.L8
	movl	%edi, (%esp)
	call	_ZdaPv
.L8:

	addl	$12, %esp
	movl	%esi, %eax
	popl	%ebx
	popl	%esi
	popl	%edi
	leave
	ret

あとはクロック数の勝負になるんですけど、そこまでやる気がおきませぬ。
ぱっと見だとなんかstd::vectorの方が速いコードなんですけど・・・。
これ以上の部分を気にするのならばはっきり言ってC++コンパイラに頼っちゃだめでしょうな。
やっぱり参照だけなら二つの差は無いと思います。