STL vector perf redux

Alright, my exercise in STL vector perf analysis was to a large extent an exercise in n00bness. Nevertheless, I learned a lot of stuff, thanks to the readers, and here's the summary.

If you are looking for the gory details, read this: http://1-800-magic.blogspot.com/2008/02/stl-vector-performance.html and the commentary.

The task: stuff an STL vector with 10000 numbers, measure what it takes per iteration.

The performance of course will vary with the computer. Mine is T2600 @ 2.16GHz.

C reference point - pre-allocated array.
2 clocks per iteration:

int *work = (int *)malloc(10000 * sizeof(int));
for (int j = 0; j < 10000; ++j)
  work[j] = j;

C reference point - dynamically allocated array using STL allocation policy.
70 clocks per iteration:

int size = 20;
int *work = (int *)malloc(size * sizeof(int));
for (int j = 0; j < 10000; ++j) {
  if (j >= size) {
    size = size + size / 2;
    work = (int *)realloc(work,
        size * sizeof(int));
  }
  work[j] = j;
}

STL, dynamically allocated vector, with or without security checks.
140 clocks per iteration.

vector work;
for (int j = 0; j < 10000; ++j)
  work.push_back(j);

STL, pre-allocated, with security checks, push_back.
9 clocks per iteration.

vector work;
work.reserve(10000);
for (int j = 0; j < 10000; ++j)
  work.push_back(j);

STL, pre-allocated, no security checks, push_back.
8 clocks per iteration.

#define _SECURE_SCL 0
vector work;
work.reserve(10000);
for (int j = 0; j < 10000; ++j)
  work.push_back(j);

STL, pre-allocated, with security checks, [].
6 clocks per iteration.

vector work(10000);
for (int j = 0; j < 10000; ++j)
  work[j] = j;

STL, pre-allocated, no security checks, [].
2 clocks per iteration.

#define _SECURE_SCL 0
vector work(10000);
for (int j = 0; j < 10000; ++j)
  work[j] = j;

Resume: know what you're doing. Performance can be from 3x to 70x slower if you're not careful.

For those who didn't read the previous post, and want to argue that none of this is important, read this http://1-800-magic.blogspot.com/2007/12/memory-is-not-free-more-on-vista.html for a fun real life story when you wouldn't think that performance matters until the very end, when it suddenly does, but then it's too late :-).

Another observation: the fact that most STL implementations are not THAT much smaller is an accolade to the modern CPU design.

If you actually look at the generated code, the STL (especially push_back) compiles to much bigger assembly than you could guess from the results above - even without the security check it is ~30 instructions plus the call into reallocating logic.

; for (int j = 0; j < NUM_ITERATIONS; ++j)
mov         edx,dword ptr [esp+3Ch] 
mov         ecx,dword ptr [esp+38h] 
xor         esi,esi 
mov         dword ptr [esp+1Ch],esi 
mov         edi,edi 
; work.push_back(j);
L0:
cmp         ecx,edi 
jne         L1
xor         eax,eax 
jmp         L2
L1:
mov         eax,dword ptr [esp+40h] 
sub         eax,ecx 
sar         eax,2 
L2:
mov         ebx,edx 
sub         ebx,ecx 
sar         ebx,2 
cmp         ebx,eax 
jae         L3
mov         dword ptr [edx],esi 
add         edx,4 
mov         dword ptr [esp+3Ch],edx 
jmp         L4
L3:
lea         ecx,[esp+1Ch] 
push        ecx  
push        edx  
lea         eax,[esp+3Ch] 
call        std::vector<int,std::allocator<int> >::_Insert_n
mov         edx,dword ptr [esp+3Ch] 
mov         ecx,dword ptr [esp+38h] 
L4:
inc         esi  
cmp         esi,2710h 
mov         dword ptr [esp+1Ch],esi 
jl          $LN22+5Ah (4013E0h)

This is only 4 times slower than the C loop, which is so much less:

xor         eax,eax 
lea         esp,[esp]
L0: 
mov         dword ptr [ecx+eax*4],eax 
inc         eax  
cmp         eax,2710h 
jl          L0

This is because all these heaps of STL code execute in parallel, speculatively, whereas the straightforward C loop is not parallelizeable at all.