Array vs Vector performance
kris...@yahoo.co.uk
code snippets on Windows Visual Studio. The code accesses all elements
of vector/array iterating several times.
------------------------------- code ---------------------------------
// iterations
static const size_t MAX_ITER = 1000;
// size of vector/array
static const int SIZE = 100000;
// helper: accessing array
void TestArraySpeedHelper(int v[])
{
v[0] = 3;
int a = 0;
for (int iter = 0; iter < MAX_ITER; ++iter)
for (size_t i = 1; i < SIZE; ++i)
{
v[i] = v[i-1] + 1;
a = v[i];
}
cout << "Exiting TestArraySpeedHelper: " << a << endl;
}
// accessing array
void TestArraySpeed()
{
int v[SIZE];
TestArraySpeedHelper(v);
}
// helper: accessing vector
void TestVecSpeedHelper(vector<int> &v)
{
v[0] = 3;
int a = 0;
for (int iter = 0; iter < MAX_ITER; ++iter)
for (size_t i = 1; i < SIZE; ++i)
{
v[i] = v[i-1] + 1;
a = v[i];
}
cout << "Exiting TestVecSpeedHelper: " << a << endl;
}
// accessing vector
void TestVecSpeed()
{
vector<int> v(SIZE);
TestVecSpeedHelper(v);
}
void PrintTime()
{
system("echo | time");
}
typedef void (__cdecl *FuncType)();
// Call functions and print times
void TestVectorVsArray(FuncType ArrFunc, FuncType VecFunc)
{
cout << "Array speed" << endl;
PrintTime();
ArrFunc();
PrintTime();
cout << "Vector speed" << endl;
PrintTime();
VecFunc();
PrintTime();
}
int main(int argc, char** argv)
{
TestVectorVsArray(TestArraySpeed, TestVecSpeed);
}
-------------------- code end ---------------------------------------
Print statements are used intentionally to prevent optimising-
compiler
eliminating the code that has no observable behaviour.
I measured both the normal clock time as well as GlowCode profiler.
Here are the clock timings (in sec:milli sec) -
ArrFunc (array access)
Start time:53.64
End time: 53.86
----------- 00.22
VecFunc (vector access)
Start time: 53.95
End time: 54.47
------------ 00.52
Profiler timings -
TestArraySpeedHelper 142.622 (excludes allocation)
TestArraySpeed 144.029 (includes allocation and calls the helper)
TestVecSpeedHelper 507.527 (excludes allocation)
TestVecSpeed 509.329 (includes allocation and calls the helper)
There appears to be significant performance difference between the
array and the vector.
The helper functions measure usage excluding any allocation related
timing.
However, cout statements are also instrumented to simulate observable
behaviour, but they seem unlikely to account for this variation.
One explanation I could think of is, vector, being allocated
elsewhere
is losing out on cache hits, causing more page faults.
Is this difference expected or am I missing something?
I would also like to know if this code could be further simplified
for instrumentation, by eliminating cout-s for example.
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Martin T.
> I am experimenting with array and vector speeds using the following
> code snippets on Windows Visual Studio. The code accesses all elements
> of vector/array iterating several times.
>
> There appears to be significant performance difference between the
> array and the vector.
Note that with Visual Studio (I assume you're using a recent version)
you get checked iterators as default behavior.
[quote MSDN]
_SECURE_SCL
If defined as 1, unsafe iterator use causes a runtime error. If defined
as 0, checked iterators are disabled. The exact behavior of the runtime
error depends on the value of _SECURE_SCL_THROWS. The default value for
_SECURE_SCL is 1, meaning checked iterators are enabled by default.
[/quote]
I have done a few informal tests for myself a while back with
VS2005/VC++8 and when compiler optimizations were on and _secure_scl
off, the difference btw. vector and raw-array where negligible for me.
br,
Martin
Mathias Gaunard
> There appears to be significant performance difference between the
> array and the vector.
Did you correctly:
- use a release and not a debug build
- enable optimizations
- disable secure stl mode
?
Alberto Ganesh Barbati
> There appears to be significant performance difference between the
> array and the vector.
>
> The helper functions measure usage excluding any allocation related
> timing.
> However, cout statements are also instrumented to simulate observable
> behaviour, but they seem unlikely to account for this variation.
>
> One explanation I could think of is, vector, being allocated
> elsewhere
> is losing out on cache hits, causing more page faults.
>
> Is this difference expected or am I missing something?
>
These numbers are very suspicious. I don't expect to see any significant
difference between the two. Actually, I expect to see no difference at
all with a reasonably optimizing compiler. Are you sure you are not
doing your benchmark with some "debug feature" enabled? For example in
VC++ 8.0 all accesses to std::vector are checked for invalid indexes
even in release builds, unless you define the macro _SECURE_SCL to the
value 0. See
http://msdn.microsoft.com/en-us/library/aa985965(VS.80).aspx
for reference.
HTH,
Ganesh
tni
> array and the vector.
This is just the case for Visual C++. For GCC/MinGW, the execution time
is exactly the same.
Part of the problem are checked iterators (MS made the poor decision to
enable them by default; if you disable them, you have to do so in any
library you link to as well). If they are disabled, the array version is
still faster. Looking at the assembly code, the array version is really
clever (twice as fast as a naive assembly version), the vector version
is lousy. The MingW assembly looks almost like a straightforward
assembly version I would do.
Timing on my machine (10000 iterations):
VC8 array : 937ms
VC8 vector (checked iterators) : 3484ms
VC8 vector (checked iterators disabled) : 2391ms
MinGW 4.1 : 2031ms
> One explanation I could think of is, vector, being allocated
> elsewhere is losing out on cache hits, causing more page faults.
No. There are no page faults, whether the array is allocated on the
stack or heap doesn't make a difference.
> I would also like to know if this code could be further simplified
> for instrumentation, by eliminating cout-s for example.
Use <ctime> / clock() for timing.
Hak...@gmail.com
> // helper: accessing vector
> void TestVecSpeedHelper(vector<int> &v)
> {
> v[0] = 3;
> int a = 0;
> for (int iter = 0; iter < MAX_ITER; ++iter)
> for (size_t i = 1; i < SIZE; ++i)
> {
> v[i] = v[i-1] + 1;
> a = v[i];
> }
> cout << "Exiting TestVecSpeedHelper: " << a << endl;}
Since you're testing specifically vector speed, why not a vector
iterator instead of an int?
Change
> for (int iter = 0; iter < MAX_ITER; ++iter)
to
> for (vector<int>::iterator iter = v.begin(), vector<int>::iterator e = v.end(); iter != e; ++iter)
When I was first learning the STL, my C++ adviser told me, after I
complained about the iterator system of C++--wich I now think is
beautiful, that they probably want you to use iterators because they
abstract from what actually gets done and they probably mask some
unknown inefficiency. Maybe he was on to something.
> One explanation I could think of is, vector, being allocated
> elsewhere
> is losing out on cache hits, causing more page faults.
Well, the int array is allocated to the stack, and the vector, I've
always assumed, is allocated to the heap, so the test won't be fair
unless you allocate the ints on the heap. It's more realistic for that
number of ints, anyway.
Andre Poenitz
>> There appears to be significant performance difference between the
>> array and the vector.
>
> This is just the case for Visual C++. For GCC/MinGW, the execution time
> is exactly the same.
>
> Part of the problem are checked iterators (MS made the poor decision to
> enable them by default; if you disable them, you have to do so in any
> library you link to as well). If they are disabled, the array version is
> still faster. Looking at the assembly code, the array version is really
> clever (twice as fast as a naive assembly version), the vector version
> is lousy. The MingW assembly looks almost like a straightforward
> assembly version I would do.
Out of curiosity: Could you show the three versions of assembly code
- or if this is deemed too much Off Topic - sent them as private mail?
I'd really like to see what halves the time over a "straightforward"
assembly.
{ As used to clarify or discuss C++ implementation issues assembly code would
not be off-topic. -mod }
> VC8 array : 937ms
> VC8 vector (checked iterators) : 3484ms
> VC8 vector (checked iterators disabled) : 2391ms
> MinGW 4.1 : 2031ms
Andre'
Joshua...@gmail.com
> Did you correctly:
> - use a release and not a debug build
> - enable optimizations
> - disable secure stl mode
First do as Mathias Gaunard says.
Even then, as Hak...@gmail.com pointed out, your test is comparing
apples to oranges. std::vector stores its elements on the heap. Your
array is statically allocated on the stack. The vector test is getting
the heap memory management overhead, a.k.a. new[] and delete[] calls.
If you change your array to be new[]'ed and delete[]'ed, you should
see comparable results. A stack array will be much quicker than
allocating an array on the heap, as your test demonstrates. If you
know the size of the array at compile time, then use a stack array and
not a vector. If you need the utility of vector (such as insert,
erase, resize, etc.), and it's not performance critical, then use a
vector.
On Jul 21, 2:17 pm, Alberto Ganesh Barbati <AlbertoBarb...@libero.it>
wrote:
> These numbers are very suspicious. I don't expect to see any significant
> difference between the two. Actually, I expect to see no difference at
> all with a reasonably optimizing compiler.
Finally, I must qualify Alberto Ganesh Barbati. As mentioned in this
thread
http://groups.google.com/group/comp.lang.c++.moderated/browse_thread/thread/26ecf8b9844feed1#
there is more overhead in creating a vector than creating an array
because a vector must initialize its elements, whereas an array of POD
type comes in an uninitialized form.
kris...@yahoo.co.uk
have all been with release builds).
Strangely now the vector version outperforms array. This is because
the compiler generated assembly shows loop unwinding on vector
iteration, but surprisingly not the array one.
Francis Glassborow
> Even then, as Hak...@gmail.com pointed out, your test is comparing
> apples to oranges. std::vector stores its elements on the heap. Your
> array is statically allocated on the stack. The vector test is getting
> the heap memory management overhead, a.k.a. new[] and delete[] calls.
> If you change your array to be new[]'ed and delete[]'ed, you should
> see comparable results. A stack array will be much quicker than
> allocating an array on the heap, as your test demonstrates. If you
> know the size of the array at compile time, then use a stack array and
> not a vector. If you need the utility of vector (such as insert,
> erase, resize, etc.), and it's not performance critical, then use a
> vector.
>
I think if you look at his code you will find that the
construction/destruction overheads have been extracted and that the
measurements are done on existing objects.
--
Note that robinton.demon.co.uk addresses are no longer valid.
Alberto Ganesh Barbati
>
> On Jul 21, 2:17 pm, Alberto Ganesh Barbati <AlbertoBarb...@libero.it>
> wrote:
>> These numbers are very suspicious. I don't expect to see any significant
>> difference between the two. Actually, I expect to see no difference at
>> all with a reasonably optimizing compiler.
>
> Finally, I must qualify Alberto Ganesh Barbati. As mentioned in this
> thread
>
> http://groups.google.com/group/comp.lang.c++.moderated/browse_thread/thread/26ecf8b9844feed1#
> there is more overhead in creating a vector than creating an array
> because a vector must initialize its elements, whereas an array of POD
> type comes in an uninitialized form.
>
That's true, but the point here was only about the "access performances"
excluding the "setup" operations, which includes allocation and
initialization. "Setup" occurs only once and is thus amortizable and
less serious unless you are going to to create and destroy large vectors
in a tight loop. In fact the OP performed two different benchmarks with
and without the setup time...
Ganesh
Mirco Wahab
> I am experimenting with array and vector speeds using the following
> code snippets on Windows Visual Studio. The code accesses all elements
> of vector/array iterating several times.
> There appears to be significant performance difference between the
> array and the vector.
> Is this difference expected or am I missing something?
As you found out already, this depends on several factors
in Visual Studio. I tried to make some sense out of this
and made the arrays into a structure:
...
struct Testinf {
size_t size;
int a[SIZE];
std::vector<int> v;
Testinf() : size(SIZE), v(SIZE) {}
};
...
In Visual C++ 9, the element that comes first
in the struct "determines" which testing function
will be faster (the effect will be more pronounced
if you use smaller arrays w/more iterations.)
"array first" (as above), SIZE=1000000, MAX_ITER=1000:
TestArray 4.734 sec
TestVector 4.984 sec
"vector first", SIZE=1000000, MAX_ITER=1000:
TestArray 5.016 sec
TestVector 4.844 sec
(did three runs, took best result of each, Athlon-64/3200+, WinXP)
In gcc (Cygwin gcc 3.4.4, Linux gcc 4.3.2)
and Intel C++ (icc 10.1-32 Linux), there's not
much of a difference to be seen. I changed the
array sizes to *1000000* and the iteration count
to *1000*. Otherwise, the arrays would be too
small to get meaningful results (imho).
Cygwin gcc 3.4.4 (-O3, XP, Athlon 64/3200+):
TestArray 4.703 sec
TestVector 4.625 sec
Intel C++ 10.1 (-O3, Linux, P4/2666MHz)
TestArray 3.56 sec
TestVector 3.58 sec
GCC 4.3.2 (-O3, Linux, P4/2666MHz)
TestArray 3.6 sec
TestVector 3.6 sec
I'd think that memory alignment issues are
of much more importance here (compared to
vector<> vs. array considerations).
> I would also like to know if this code could be further simplified
> for instrumentation, by eliminating cout-s for example.
Out of curiosity, I tried to apply a well known "Perl-idiom"
to this problem ;-) See appendix.
Regards
Mirco
---- 8< ----
#define _SECURE_SCL 0
#include <ctime>
#include <vector>
#include <iostream>
int const SIZE = 1000000, MAX_ITER = 1000; // size of vector/array and ...
struct Testinf {
size_t size;
int a[SIZE];
std::vector<int> v;
Testinf() : size(SIZE), v(SIZE) {}
};
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
int TestArray(Testinf& t, size_t maxiter) // accessing array
{
t.a[0] = 3;
int r = 0;
for(size_t c=0; c<maxiter; ++c) {
for(size_t i=1; i<t.size; ++i) {
t.a[i] = t.a[i-1] + i;
r += t.a[i];
}
}
return r;
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
int TestVector(Testinf& t, size_t maxiter) // accessing vector
{
t.v[0] = 3;
int r = 0;
for(size_t c=0; c<maxiter; ++c) {
for(size_t i=1; i<t.size; ++i) {
t.v[i] = t.v[i-1] + i;
r += t.v[i];
}
}
return r;
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
struct Fu {
const char *t; // a literal name
int (*PTestF)(Testinf&, size_t); // and a function, set by ctor
Fu(int(*f)(Testinf&, size_t), const char *name) : t(name), PTestF(f) {}
};
void timethese(size_t maxiter, Fu f[], Testinf& t, size_t n); // tests an array of Fu
int main()
{
static Testinf t; // static in order to avert stack problems
Fu f[] = {
Fu(TestArray, "TestArray"),
Fu(TestVector, "TestVector")
};
size_t n = sizeof(f)/sizeof(*f);
timethese(MAX_ITER, f, t, n);
return 0;
}
double timethis(Fu f, Testinf& t, size_t maxiter)
{
time_t time = clock();
int x = 1 & (f.PTestF(t, maxiter) & ~0x1); // fool optimizer,
return double(clock()-time-x) / CLOCKS_PER_SEC; // x will be always 0
}
void timethese(size_t maxiter, Fu f[], Testinf& t, size_t n)
{
for(size_t i=0; i<n; i++)
std::cout << f[i].t << "\t"
<< timethis(f[i], t, maxiter) << " sec"
<< std::endl;
}
---- 8< ----
tni
> Out of curiosity: Could you show the three versions of assembly code
> - or if this is deemed too much Off Topic - sent them as private mail?
> I'd really like to see what halves the time over a "straightforward"
> assembly.
I changed the loop code slightly:
int a = 0;
for (int iter = 0; iter < max_iter; ++iter)
for(size_t i = 1; i < vec_size; ++i) {
v[i] = v[i-1] + 1;
a += v[i];
}
Inner loop:
VC8 (array, checked iterators disabled):
00401CB7 mov ecx,dword ptr [eax-8]
00401CBA add ecx,1
00401CBD lea edx,[ecx+1]
00401CC0 lea esi,[edx+1]
00401CC3 mov dword ptr [eax+4],esi
00401CC6 add esi,edx
00401CC8 add esi,ecx
00401CCA mov dword ptr [eax-4],ecx
00401CCD mov dword ptr [eax],edx
00401CCF add ebx,esi
00401CD1 add eax,0Ch
00401CD4 sub edi,1
00401CD7 jne TestArraySpeedHelper+27h (401CB7h)
Note that the loop is unrolled 3x. Two increments are using lea (which
will use the address calculation unit instead of the ALU).
VC8 (vector, checked iterators disabled):
00401135 mov edi,dword ptr [eax+edx-4]
00401139 add edi,1
0040113C mov dword ptr [eax+edx],edi
0040113F mov edx,dword ptr [esi+4]
00401142 mov edi,dword ptr [edx+eax]
00401145 add edx,eax
00401147 add ecx,edi
00401149 add edi,1
0040114C mov dword ptr [edx+4],edi
0040114F mov edx,dword ptr [esi+4]
00401152 mov edi,dword ptr [eax+edx+4]
00401156 add ecx,edi
00401158 add edi,1
0040115B mov dword ptr [eax+edx+8],edi
0040115F mov edx,dword ptr [esi+4]
00401162 add ecx,dword ptr [eax+edx+8]
00401166 add eax,0Ch
00401169 cmp eax,61A80h
0040116E jb TestVecSpeedHelper+25h (401135h)
The loop is also unrolled 3x. Note the unnecessary register reloads and
memory traffic.
MinGW 4.1 (array):
401370: mov eax,DWORD PTR [ecx+edx*4-4]
401374: inc eax
401375: mov DWORD PTR [ecx+edx*4],eax
401378: inc edx
401379: add ebx,eax
40137b: cmp edx,0x186a0
401381: jne 401370
Loop is not unrolled.
kris...@yahoo.co.uk
Looks like Visual Studio is not producing similar assembly code across
various versions.
Visual C++ 2008 Express Edition (Similar on 2005 Professional Edition)
Vector has loop unrolling
for (size_t i = 1; i < SIZE; ++i)
004011C0 mov eax,4
{
v[i] = v[i-1] + 1;
004011C5 mov ecx,dword ptr [esi+4]
004011C8 mov ebp,dword ptr [ecx+eax-4]
004011CC add ecx,eax
004011CE inc ebp
004011CF mov dword ptr [ecx],ebp
004011D1 mov ecx,dword ptr [esi+4]
004011D4 mov ebp,dword ptr [ecx+eax]
004011D7 add ecx,eax
004011D9 inc ebp
004011DA mov dword ptr [ecx+4],ebp
004011DD mov ecx,dword ptr [esi+4]
004011E0 mov ebp,dword ptr [eax+ecx+4]
004011E4 inc ebp
004011E5 mov dword ptr [eax+ecx+8],ebp
004011E9 add eax,0Ch
004011EC cmp eax,61A80h
004011F1 jb TestVecSpeedHelper+25h (4011C5h)
Array version has no such luxury:
for (size_t i = 1; i < SIZE; ++i)
00401130 mov eax,1
{
v[i] = v[i-1] + 1;
00401135 mov edx,dword ptr [esi+eax*4-4]
00401139 inc edx
0040113A mov dword ptr [esi+eax*4],edx
0040113D inc eax
0040113E cmp eax,186A0h
00401143 jb TestArraySpeedHelper+25h (401135h)
SIZE value is 100000. The vector is faster in this specific case. However,
loop unrolling can be sabotaged by using different SIZE, for exampple 100002.