vector acces by index/iterator

[Hagen]

Hello,

in a recent thread "speed of vector vs array" I read about the problem
of the slow acces by addressing vector elements by indexing,
unfortunately I see no workaround in my case.

My case:

class A
{
private:
vector<int> vec;
public:
...
}

\\at first I had the private element declared as array, so I always
accessed the parts by index: vec

\\now in order to avoid the slowdown when accessing a vector by index I
want to use iterators, the following problem occurs when I want to
access an A object in a function, example:

void function(const A& a)
{
vector<int>::iterator const p( a.vec.begin() );
...
}


When compiling this I get the error message:
invalid conversion from 'const int* const' to 'int*'

I could avoid this problem by not giving the parameter as const, but I'm
afraid to do so because I would have to change throughout the whole
program and maybe destroy some data when referring to parameters by
reference. And by just having "void function(A a)" I lose a lot of time
because everytime a copy-constructor would be called, instead of losing
the time by slow vector-index-accessment.

I hope there is a way I can access the elements in a vector as fast as
in an array without turning my program upside down. So thanks in advance
for your help.

Hagen

 

[lallous]

Hello,

in a recent thread "speed of vector vs array" I read about the problem
of the slow acces by addressing vector elements by indexing,
unfortunately I see no workaround in my case.

My case:

class A
{
private:
vector<int> vec;
public:
...
}

\\at first I had the private element declared as array, so I always
accessed the parts by index: vec

\\now in order to avoid the slowdown when accessing a vector by index I
want to use iterators, the following problem occurs when I want to
access an A object in a function, example:

void function(const A& a)
{
vector<int>::iterator const p( a.vec.begin() );
...
}


When compiling this I get the error message:
invalid conversion from 'const int* const' to 'int*'

I could avoid this problem by not giving the parameter as const, but I'm
afraid to do so because I would have to change throughout the whole
program and maybe destroy some data when referring to parameters by
reference. And by just having "void function(A a)" I lose a lot of time
because everytime a copy-constructor would be called, instead of losing
the time by slow vector-index-accessment.

I hope there is a way I can access the elements in a vector as fast as
in an array without turning my program upside down. So thanks in advance
for your help.

Hello

Why not access the vector using pointer as:
(since vector elements are guaranteed to be sequential in memory)

void function(const A& a)
{
int *i = &a.vec[0];

// access using pointers:
cout << "first element's value:" << *i << endl;
i++;
cout << "second element's value:" << *i << endl;

// or as if arrays:
cout << "first element's value:" << i[0] << endl;
cout << "second element's value:" << i[1] << endl;
}

 

[John Harrison]

Hello,

in a recent thread "speed of vector vs array" I read about the problem
of the slow acces by addressing vector elements by indexing,
unfortunately I see no workaround in my case.

My case:

class A
{
private:
vector<int> vec;
public:
...
}

\\at first I had the private element declared as array, so I always
accessed the parts by index: vec

\\now in order to avoid the slowdown when accessing a vector by index I
want to use iterators, the following problem occurs when I want to
access an A object in a function, example:

void function(const A& a)
{
vector<int>::iterator const p( a.vec.begin() );

Do it like this

...
}

john

 

[John Harrison]

Hello,

in a recent thread "speed of vector vs array" I read about the problem
of the slow acces by addressing vector elements by indexing,
unfortunately I see no workaround in my case.

My case:

class A
{
private:
vector<int> vec;
public:
...
}

\\at first I had the private element declared as array, so I always
accessed the parts by index: vec

\\now in order to avoid the slowdown when accessing a vector by index I
want to use iterators, the following problem occurs when I want to
access an A object in a function, example:

void function(const A& a)
{
vector<int>::iterator const p( a.vec.begin() );
...
}


When compiling this I get the error message:
invalid conversion from 'const int* const' to 'int*'

I could avoid this problem by not giving the parameter as const, but I'm
afraid to do so because I would have to change throughout the whole
program and maybe destroy some data when referring to parameters by
reference. And by just having "void function(A a)" I lose a lot of time
because everytime a copy-constructor would be called, instead of losing
the time by slow vector-index-accessment.

I hope there is a way I can access the elements in a vector as fast as
in an array without turning my program upside down. So thanks in advance
for your help.

Hello

Why not access the vector using pointer as:
(since vector elements are guaranteed to be sequential in memory)

void function(const A& a)
{
int *i = &a.vec[0];

const int* i = &a.vec[0];

It's quite possible for an implementation to make a vector iterator a
typedef for a pointer. In that case using an iterator and using a pointer
would be the same.

john

 

[John Harrison]

It's quite possible for an implementation to make a vector iterator a
typedef for a pointer. In that case using an iterator and using a pointer
would be the same.

In fact the OP's error message indicates that he is using an implementation
where vector iterators and pointers are the same.

john

 

[Jeff Flinn]

Hello,


void function(const A& a)
{
vector<int>::iterator const p( a.vec.begin() );

I think you ( and the compiler ) want:

vector<int>::const_iterator p( a.vec.begin() );

Jeff F

 

[Alex Vinokur]

I hope there is a way I can access the elements in a vector as fast as
in an array without turning my program upside down. So thanks in advance
for your help.

[snip]

Here are some results of comparative performance measurement
performed with using C/C++ Program Perfometer
* http://alexvn.freeservers.com/s1/perfometer.html
* http://sourceforge.net/projects/cpp-perfometer


#====================================================
# An access to an element
#----------------------------------------------------
# Total repetitions : 5000000
# Performance metrics : clock / 5000000 repetitions
#====================================================
: ====================================================
: --- array ---
: operator[] - array (size = 10) -> 20 ms
: operator[] - array (size = 100) -> 20 ms
: operator[] - array (size = 1000) -> 20 ms
:
: --- vector ---
: operator[] - vector (size = 10) -> 297 ms
: operator[] - vector (size = 100) -> 300 ms
: operator[] - vector (size = 1000) -> 303 ms
:
: iterator - vector (size = 10) -> 40 ms
: iterator - vector (size = 100) -> 40 ms
: iterator - vector (size = 1000) -> 40 ms
:
: pointer - vector (size = 10) -> 20 ms
: pointer - vector (size = 100) -> 16 ms
: pointer - vector (size = 1000) -> 20 ms
:
: at method - vector (size = 10) -> 714 ms
: at method - vector (size = 100) -> 721 ms
: at method - vector (size = 1000) -> 727 ms
:
: --- string ---
: operator[] - string (size = 10) -> 90 ms
: operator[] - string (size = 100) -> 220 ms
: operator[] - string (size = 1000) -> 96 ms
:
: iterator - string (size = 10) -> 50 ms
: iterator - string (size = 100) -> 46 ms
: iterator - string (size = 1000) -> 46 ms
:
: pointer - string (size = 10) -> 20 ms
: pointer - string (size = 100) -> 20 ms
: pointer - string (size = 1000) -> 20 ms
:
: at method - string (size = 10) -> 90 ms
: at method - string (size = 100) -> 220 ms
: at method - string (size = 1000) -> 90 ms
: ====================================================

 

[Alex Vinokur]

I hope there is a way I can access the elements in a vector as fast as
in an array without turning my program upside down. So thanks in advance
for your help.

[snip]

Here are some results of comparative performance measurement

[snip]

Environment

 

[Peter van Merkerk]

I hope there is a way I can access the elements in a vector as fast as
in an array without turning my program upside down. So thanks in advance
for your help.

[snip]

Here are some results of comparative performance measurement
performed with using C/C++ Program Perfometer
* http://alexvn.freeservers.com/s1/perfometer.html
* http://sourceforge.net/projects/cpp-perfometer


#====================================================
# An access to an element
#----------------------------------------------------
# Total repetitions : 5000000
# Performance metrics : clock / 5000000 repetitions
#====================================================
: ====================================================
: --- array ---
: operator[] - array (size = 10) -> 20 ms
: operator[] - array (size = 100) -> 20 ms
: operator[] - array (size = 1000) -> 20 ms
:
: --- vector ---
: operator[] - vector (size = 10) -> 297 ms
: operator[] - vector (size = 100) -> 300 ms
: operator[] - vector (size = 1000) -> 303 ms
:
: iterator - vector (size = 10) -> 40 ms
[snip]

Since you did not specify the platform, compiler, compiler settings and
the standard library implementation that were used to obtain these
results, these numbers are quite meaningless.

 

[SaltPeter]

[snip]
I hope there is a way I can access the elements in a vector as fast as
in an array without turning my program upside down. So thanks in advance
for your help.

[snip]

Here are some results of comparative performance measurement
performed with using C/C++ Program Perfometer
* http://alexvn.freeservers.com/s1/perfometer.html
* http://sourceforge.net/projects/cpp-perfometer

Hilarious. Try running your tests in release mode with optimization. You'll
throw the array out the door. The larger the data set, the farther the array
will fall.

#====================================================
# An access to an element
#----------------------------------------------------
# Total repetitions : 5000000
# Performance metrics : clock / 5000000 repetitions
#====================================================
: ====================================================
: --- array ---
: operator[] - array (size = 10) -> 20 ms
: operator[] - array (size = 100) -> 20 ms
: operator[] - array (size = 1000) -> 20 ms
:
: --- vector ---
: operator[] - vector (size = 10) -> 297 ms
: operator[] - vector (size = 100) -> 300 ms
: operator[] - vector (size = 1000) -> 303 ms
:
: iterator - vector (size = 10) -> 40 ms
: iterator - vector (size = 100) -> 40 ms
: iterator - vector (size = 1000) -> 40 ms
:
: pointer - vector (size = 10) -> 20 ms
: pointer - vector (size = 100) -> 16 ms
: pointer - vector (size = 1000) -> 20 ms
:
: at method - vector (size = 10) -> 714 ms
: at method - vector (size = 100) -> 721 ms
: at method - vector (size = 1000) -> 727 ms
:
: --- string ---
: operator[] - string (size = 10) -> 90 ms
: operator[] - string (size = 100) -> 220 ms
: operator[] - string (size = 1000) -> 96 ms
:
: iterator - string (size = 10) -> 50 ms
: iterator - string (size = 100) -> 46 ms
: iterator - string (size = 1000) -> 46 ms
:
: pointer - string (size = 10) -> 20 ms
: pointer - string (size = 100) -> 20 ms
: pointer - string (size = 1000) -> 20 ms
:
: at method - string (size = 10) -> 90 ms
: at method - string (size = 100) -> 220 ms
: at method - string (size = 1000) -> 90 ms
: ====================================================

 

[DaKoadMunky]

Hilarious. Try running your tests in release mode with optimization. You'll

throw the array out the door. The larger the data set, the farther the array
will fall.

Are you saying that a vector could actually end up being faster than an array
with respect to retrieving items through operator[]?

I have seen the results of performance tests that seem to indicate this
possibility.

I am wondering how this is possible though.

My thinking is that since both an array and a vector use a single contiguous
block of memory and that to access an individual element in either an array or
vector requires the same pointer arithmetic that the performance would be
comparable in the presence of inlining for the vector operator[].

Could you illustrate a scenario in which a vector might be faster?

 

[Kai-Uwe Bux]

Hilarious. Try running your tests in release mode with optimization.
You'll throw the array out the door. The larger the data set, the farther
the array will fall.

Are you saying that a vector could actually end up being faster than an
array with respect to retrieving items through operator[]?

I have seen the results of performance tests that seem to indicate this
possibility.

I am wondering how this is possible though.

My thinking is that since both an array and a vector use a single
contiguous block of memory and that to access an individual element in
either an array or vector requires the same pointer arithmetic that the
performance would be comparable in the presence of inlining for the vector
operator[].

Could you illustrate a scenario in which a vector might be faster?

Hi,


just whipped up some test code. Sorry for including the sys/timeb.h header.
Does someone know a standard way of doing this?


#include <vector>
#include <iostream>
#include <sys/timeb.h>

long int time_diff ( timeb a, timeb b ) {
return( ( a.time - b.time )*1000 + ( a.millitm - b.millitm ) );
}

int main ( void ) {
const unsigned long l = 50000000;
{
std::vector< int > v ( l );
timeb loop_start, loop_end;
ftime( &loop_start );
for ( unsigned long i = 0; i < l; ++i ) {
v = 5;
}
ftime( &loop_end );
std::cout << time_diff( loop_end, loop_start ) << std::endl;
}
{
int* v = new int [ l ];
timeb loop_start, loop_end;
ftime( &loop_start );
for ( unsigned long i = 0; i < l; ++i ) {
*( v + i ) = 5;
}
ftime( &loop_end );
std::cout << time_diff( loop_end, loop_start ) << std::endl;
}
}


just a measurement on my machine (2.4GH, g++3.4.0 -O3):

a.out

457
601

Thus, std::vector<int> was faster than int[].


I have observed oftentimes that g++ procudes better optimization with
templated code. I have no explanation, though.


Best

Kai-Uwe Bux

 

[Alex Vinokur]

Since you did not specify the platform, compiler,

See http://groups.google.com/[email protected]

compiler settings

$ g++ -mno-cygwin *.cpp

and the standard library implementation

What information about standard library implementation for g++ version 3.3.1 (cygming special) should be supplied?

that were used to obtain these results, these numbers are quite meaningless.

[snip]

 

[SaltPeter]

Hilarious. Try running your tests in release mode with optimization. You'll
throw the array out the door. The larger the data set, the farther the array
will fall.

Are you saying that a vector could actually end up being faster than an array
with respect to retrieving items through operator[]?

I have seen the results of performance tests that seem to indicate this
possibility.

I am wondering how this is possible though.

My thinking is that since both an array and a vector use a single contiguous
block of memory and that to access an individual element in either an array or
vector requires the same pointer arithmetic that the performance would be
comparable in the presence of inlining for the vector operator[].

The standard guarentees that *any* element of the vector container is
accessed using a constant time period (so any element is accessed with the
same access period as the container's first element). There is a
misconception out there that a vector is like a list where each element
pointing to the next. This is not the case. Vectors use random iterators.
These aren't available to either the array or std::list. And the array
doesn't even have a conception of what an iterator is.

The problem with the vector is that once it's reserved size has been
reached, it needs to copy its elements in the background to the new resized
container. To be fair, the case is much more restrictive with an array since
one must define the array's size at compile time and then code the copy
during a resize which the programmer needs to manage.

Note that some STL containers, like a std::deque, do not displace their
original elements upon a resize of the container.

Could you illustrate a scenario in which a vector might be faster?

Here is program based on clock ticks with the ctime header. This isn't an
accurate count by any means. But you'll notice the vector is accessed faster
than an array when running in release mode. If you were to expand the
program to provide randomized access, the array gets blasted into
hyperspace.

ticks while indexing array in sequence: 500
ticks while indexing vector in sequence: 490
ticks while indexing deque in sequence: 500

your numbers will vary...

#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
#include <ctime>

int main()
{
// initiliazation
const int count = 100000;
int i = 0;

// the contenders
int u_array[count];
std::vector<int> v;
std::deque<int> d;

std::vector<int>::iterator viter;
std::deque<int>::iterator diter;

// array:
for (i = 0; i < count; ++i)
{
u_array = i;
}

// vector:
for (i = 0; i < count; ++i)
{
v.push_back(i);
}

for (i = 0; i < count; ++i)
{
d.push_back(i);
}

// output file stream
std:fstream ofs;
ofs.open("test.dat", std::ios:ut);
if (!ofs)
std::cout << "error opening output file stream.\n";

// array: indexing access
clock_t ticks = clock();
for(i = 0; i < count; ++i)
{
ofs << u_array;
}
ofs << "\n\n";
ticks = clock() - ticks;
std::cout << "\nticks while indexing array in sequence: " << ticks;

// vector: indexing access
ticks = clock();
for(viter = v.begin(); viter != v.end(); ++viter)
{
ofs << *viter;
}
ofs << "\n\n";
ticks = clock() - ticks;
std::cout << "\nticks while indexing vector in sequence: " << ticks;

// deque: indexing access
ticks = clock();
for(diter = d.begin(); diter != d.end(); ++diter)
{
ofs << *diter;
}
ofs << "\n\n";
ticks = clock() - ticks;
std::cout << "\nticks while indexing deque in sequence: " << ticks <<
std::endl;

ofs.close();

return 0;
}

 

[Karl Heinz Buchegger]

Hilarious. Try running your tests in release mode with optimization.
You'll throw the array out the door. The larger the data set, the farther
the array will fall.

Are you saying that a vector could actually end up being faster than an
array with respect to retrieving items through operator[]?

I have seen the results of performance tests that seem to indicate this
possibility.

I am wondering how this is possible though.

My thinking is that since both an array and a vector use a single
contiguous block of memory and that to access an individual element in
either an array or vector requires the same pointer arithmetic that the
performance would be comparable in the presence of inlining for the vector
operator[].

Could you illustrate a scenario in which a vector might be faster?

Hi,

just whipped up some test code. Sorry for including the sys/timeb.h header.
Does someone know a standard way of doing this?

just a measurement on my machine (2.4GH, g++3.4.0 -O3):

a.out

457
601

Same here: VC++ 6.0, 2.4 Ghz

Debug:
vector 3485
array 581

Release:
vector 511
array 761

 

[Richard Herring]

news:[email protected]... [...]

My thinking is that since both an array and a vector use a single contiguous
block of memory and that to access an individual element in either an array or
vector requires the same pointer arithmetic that the performance would be
comparable in the presence of inlining for the vector operator[].

The standard guarentees that *any* element of the vector container is
accessed using a constant time period (so any element is accessed with the
same access period as the container's first element). There is a
misconception out there that a vector is like a list where each element
pointing to the next. This is not the case.

It's not a misconception I've noticed. YMMV.

Vectors use random iterators.
These aren't available to either the array or std::list.

Arrays have random-access iterators. They're called pointers.

A {random-access, bidirectional, forward, input, output} iterator is
anything satisfying the requirements of {random-access, bidirectional,
forward, input, output} iterator (24.1). A pointer into an array does
everything that's needed for a random-access iterator, therefore it is
one. As witness the fact that many implementations of std::vector use
raw pointers as their iterators.

And the array
doesn't even have a conception of what an iterator is.

The only iterator-related things that arrays lack are the functions
which return them.

[...]

 

[Peter van Merkerk]

See http://groups.google.com/[email protected]



$ g++ -mno-cygwin *.cpp

What??? No optimizations???
That makes the results you posted not very representative for many
people. It will almost always make the container classes look worse that
the C style constructs.

What information about standard library implementation for g++ version 3.3.1 (cygming special) should be supplied?

Just the fact that you use it. The compiler and the standard library
implementation that comes with it are not one and the same thing. One
might decide not to use the standard library implementation that comes
with the compiler but a third party one instead.

Please don't take my criticism the wrong way. It is very difficult to
make a realistic and representative benchmark that produces generally
meaningful results. There are so many variables that may affect the
outcome a benchmark that it is likely your choices for those variables
are not representative for my situation or the next guy. Changing some
of those variables, like compiling with optimization or a different
compiler, can have a very drastic effect on the results and may even
turn the tables around. This is why it is so crucial to know exactly how
and under what conditions the benchmark numbers were obtained, before
drawing any conclusions from it. A good benchmark should include enough
information so someone else can independantly reproduce similar results.

 

[Peter van Merkerk]

The standard guarentees that *any* element of the vector container is
accessed using a constant time period (so any element is accessed with the
same access period as the container's first element).

"constant time" should not be taken too literally on many platforms.
Thanks to caching and virtual memory accessing of raw memory isn't a
constant time operation. Consequently it cannot be guaranteed that
accessing a element of a vector (or a C style array for that matter)
takes a fixed amount of time. I.e. accessing one element may take in the
order of nanoseconds, while accesing another element in the same vector
or array may take tens of milliseconds if it triggers a page fault. This
is concern when working with large datasets that don't fit into the
cache or physical memory.

 

[Rob Williscroft]

SaltPeter wrote in in
comp.lang.c++:

The standard guarentees that *any* element of the vector container is
accessed using a constant time period (so any element is accessed with
the same access period as the container's first element).

All this means is there is a *fixed* upper bound on access time, and also
that this upper bound is independant of the number of elements in the
container (*), it doesn't imply that access to specific elements might
not be faster than access to others.

For example on a 64 bit machine with 32 bit int's std::vector< int >
(or int array[ N ]) might have access to odd elements taking twice the
time as access to even elements. In such a case its the time to access
the odd elements that determines the fixed upper bound.

*) As Peter van Merkerk explains else-thread, even this shouldn't be
taken too literally.

Rob.

 

[SaltPeter]

news:[email protected]... [...]

My thinking is that since both an array and a vector use a single contiguous
block of memory and that to access an individual element in either an array or
vector requires the same pointer arithmetic that the performance would be
comparable in the presence of inlining for the vector operator[].

The standard guarentees that *any* element of the vector container is
accessed using a constant time period (so any element is accessed with the
same access period as the container's first element). There is a
misconception out there that a vector is like a list where each element
pointing to the next. This is not the case.

It's not a misconception I've noticed. YMMV.

Vectors use random iterators.
These aren't available to either the array or std::list.

Arrays have random-access iterators. They're called pointers.

A {random-access, bidirectional, forward, input, output} iterator is
anything satisfying the requirements of {random-access, bidirectional,
forward, input, output} iterator (24.1). A pointer into an array does
everything that's needed for a random-access iterator, therefore it is
one. As witness the fact that many implementations of std::vector use
raw pointers as their iterators.

And the array
doesn't even have a conception of what an iterator is.

The only iterator-related things that arrays lack are the functions
which return them.

Yep, well i deserved that response.

What i was refering to was the support for the said iterators as your last
comment mentions. In other words, an array doesn't have an end().

[...]