Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Access performance : array, vector, basic_string

3 views
Skip to first unread message

Alex Vinokur

unread,
Mar 26, 1999, 3:00:00 AM3/26/99
to

Hi,

Performance of accesses to elements
in C-array,
STL vector and
STL basic_string
was measured.

Average time-cost of execution was obtained.
The results of the experiment are shown below.

Main conclusions :
1. char_array < char_string < char_vector;
2. int_array < int_vector << int_string.
Note! The "<" symbol means "faster".
The "<<" symbol means "much faster".

3. The faster hierarchies are different
for *int* and *char* data structures (Why?)

4. Access to basic_string<unsigned int>
takes a lot of time (Why?)

Thanks,
Alex

P.S. Here are the results of the experiment.


//########################################################
//------------------- C++ code : BEGIN -------------------

//=================================================
#include <string>
#include <vector>
#include <sys/time.h>

//=======================
void print_status (
int testNo_i,
hrtime_t& t_start_i,
hrtime_t& t_end_i,
int array_size_i,
int iters_i,
const string& name_i
)
{
cout << "Test#"
<< testNo_i
<< " ["
<< name_i.c_str ()
<< "]"
<< "\t: "
<< "\tAverage time = "
<< (((t_end_i - t_start_i)/array_size_i)/iters_i)
<< " nsec"
<< endl;
}
//=======================
#define PRINT(testNo_i, object_i) \
print_status ( \
testNo_i, \
time_start, \
time_end, \
ARRAY_SIZE, \
TOTAL_Iterations, \
#object_i)

//####################################################
int main()
{
//=======================
const unsigned int TOTAL_Tests = 5;
const unsigned int TOTAL_Iterations = 10000;
const unsigned int ARRAY_SIZE = 500;

//=======================
hrtime_t time_start;
hrtime_t time_end;
//=======================
unsigned int int_array [ARRAY_SIZE];
vector<unsigned int> int_vector;
basic_string<unsigned int> int_string;
//----------
char char_array [ARRAY_SIZE];
vector<char> char_vector;
string char_string;
//=======================

unsigned int curTestNo;
unsigned int curIndex;
unsigned int curIteration;
unsigned int intValue = 25;
char charValue = 'Z';

for (curIndex = 0;
curIndex < ARRAY_SIZE;
curIndex++)
{
//========
int_array [curIndex] = intValue;
int_vector.push_back (intValue);
int_string += intValue;
//========
char_array [curIndex] = charValue;
char_vector.push_back (charValue);
char_string += charValue;
//========
}

//======================

for (curTestNo = 1;
curTestNo <= TOTAL_Tests;
curTestNo++)
{
//=======================
cout << endl
<< "\t"
<< "##### Test#"
<< curTestNo
<< " (access)"
<< " #####"
<< endl;

//############ int #################
//=======================================
//======= int_array ================
time_start = gethrtime();
for (curIteration = 1;
curIteration <= TOTAL_Iterations;
curIteration++)
{
for (curIndex = 0;
curIndex < ARRAY_SIZE;
curIndex++)
{
int_array [curIndex];
}
}
time_end = gethrtime();
PRINT (curTestNo, int_array);
//===============================

//===================================
//======= int_vector ================
time_start = gethrtime();
for (curIteration = 1;
curIteration <= TOTAL_Iterations;
curIteration++)
{
for (curIndex = 0;
curIndex < ARRAY_SIZE;
curIndex++)
{
int_vector [curIndex];
}
}
time_end = gethrtime();
PRINT (curTestNo, int_vector);
//===============================


//===================================
//======= int_string ================
time_start = gethrtime();
for (curIteration = 1;
curIteration <= TOTAL_Iterations;
curIteration++)
{
for (curIndex = 0;
curIndex < ARRAY_SIZE;
curIndex++)
{
int_string [curIndex];
}
}
time_end = gethrtime();
PRINT (curTestNo, int_string);
//===============================


cout << endl;
//############ char #################
//=======================================
//======= char_array ================
time_start = gethrtime();
for (curIteration = 1;
curIteration <= TOTAL_Iterations;
curIteration++)
{
for (curIndex = 0;
curIndex < ARRAY_SIZE;
curIndex++)
{
char_array [curIndex];
}
}
time_end = gethrtime();
PRINT (curTestNo, char_array);
//===============================

//===================================
//======= char_vector ================
time_start = gethrtime();
for (curIteration = 1;
curIteration <= TOTAL_Iterations;
curIteration++)
{
for (curIndex = 0;
curIndex < ARRAY_SIZE;
curIndex++)
{
char_vector [curIndex];
}
}
time_end = gethrtime();
PRINT (curTestNo, char_vector);
//===============================


//===================================
//======= char_string ================
time_start = gethrtime();
for (curIteration = 1;
curIteration <= TOTAL_Iterations;
curIteration++)
{
for (curIndex = 0;
curIndex < ARRAY_SIZE;
curIndex++)
{
char_string [curIndex];
}
}
time_end = gethrtime();
PRINT (curTestNo, char_string);
//===============================

} // for (curTestNo = 1; curTestNo <= TOTAL_Tests; curTestNo++)
//======================
return 0;
}

//------------------- C++ code : END ---------------------


//#########################################################
//------------------- Running Results : BEGIN -------------


##### Test#1 (access) #####
Test#1 [int_array] : Average time = 90 nsec
Test#1 [int_vector] : Average time = 354 nsec
Test#1 [int_string] : Average time = 1076 nsec

Test#1 [char_array] : Average time = 103 nsec
Test#1 [char_vector] : Average time = 422 nsec
Test#1 [char_string] : Average time = 262 nsec

##### Test#2 (access) #####
Test#2 [int_array] : Average time = 84 nsec
Test#2 [int_vector] : Average time = 362 nsec
Test#2 [int_string] : Average time = 1078 nsec

Test#2 [char_array] : Average time = 83 nsec
Test#2 [char_vector] : Average time = 422 nsec
Test#2 [char_string] : Average time = 277 nsec

##### Test#3 (access) #####
Test#3 [int_array] : Average time = 86 nsec
Test#3 [int_vector] : Average time = 365 nsec
Test#3 [int_string] : Average time = 1234 nsec

Test#3 [char_array] : Average time = 108 nsec
Test#3 [char_vector] : Average time = 445 nsec
Test#3 [char_string] : Average time = 266 nsec

##### Test#4 (access) #####
Test#4 [int_array] : Average time = 83 nsec
Test#4 [int_vector] : Average time = 359 nsec
Test#4 [int_string] : Average time = 1160 nsec

Test#4 [char_array] : Average time = 135 nsec
Test#4 [char_vector] : Average time = 437 nsec
Test#4 [char_string] : Average time = 300 nsec

##### Test#5 (access) #####
Test#5 [int_array] : Average time = 94 nsec
Test#5 [int_vector] : Average time = 344 nsec
Test#5 [int_string] : Average time = 1160 nsec

Test#5 [char_array] : Average time = 106 nsec
Test#5 [char_vector] : Average time = 440 nsec
Test#5 [char_string] : Average time = 255 nsec

//------------------- Running Results : END ---------------

//#########################################################
//------------------- Compiler & System ------------------

g++ -v : gcc version egcs-2.91.57 19980901
(egcs-1.1 release)

uname -a : SunOS <nodename> 5.6 Generic_105181-09
sun4m sparc SUNW,SPARCstation-5

psrinfo -v : -> The sparc processor operates at 110 MHz

//---------------------------------------------------------


//#########################################################

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own

[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
[ about comp.lang.c++.moderated. First time posters: do this! ]

Siemel Naran

unread,
Mar 27, 1999, 3:00:00 AM3/27/99
to
On 26 Mar 1999 10:23:54 -0500, Alex Vinokur

> ##### Test#1 (access) #####
>Test#1 [int_array] : Average time = 90 nsec
>Test#1 [int_vector] : Average time = 354 nsec
>Test#1 [int_string] : Average time = 1076 nsec

>//#########################################################
>//------------------- Compiler & System ------------------
>
>g++ -v : gcc version egcs-2.91.57 19980901
> (egcs-1.1 release)
>
>uname -a : SunOS <nodename> 5.6 Generic_105181-09
> sun4m sparc SUNW,SPARCstation-5
>
>psrinfo -v : -> The sparc processor operates at 110 MHz

What optimization levels did you use? I did a similar test,
using builtin fixed-sized arrays (the fastest that can be)
double[N], and std::vector<double>(N). I found that with no
optimization, the fixed size array method was definitely
faster. But with -O1 optimization (which does inlining),
both methods were about the same.

Also, the vector::iterator method for repeated access is
usually faster than the vector::operator[] method. Unless
you use -O2 (or was it -O3), in which case both methods
are identical.

--
----------------------------------
Siemel B. Naran (sbn...@uiuc.edu)
----------------------------------

sa...@bear.com

unread,
Mar 28, 1999, 3:00:00 AM3/28/99
to
In article <7ddm1q$je9$1...@nnrp1.dejanews.com>,

Alex Vinokur <alexande...@telrad.co.il> wrote:
>
>
> Hi,
>
> Performance of accesses to elements
> in C-array,
> STL vector and
> STL basic_string
> was measured.
>
> Average time-cost of execution was obtained.
> The results of the experiment are shown below.
>
> Main conclusions :
> 1. char_array < char_string < char_vector;
> 2. int_array < int_vector << int_string.
> Note! The "<" symbol means "faster".
> The "<<" symbol means "much faster".
>
> 3. The faster hierarchies are different
> for *int* and *char* data structures (Why?)
>
> 4. Access to basic_string<unsigned int>
> takes a lot of time (Why?)
>
> Thanks,
> Alex

Did you measure them with optimization turned on?

>From Lippman's "Inside the C++ Object Model" book:

"Without the optimizer turned on, it is extremely difficult to guess at
the performance characteristics of a program, since the code is potentially
hostage to the 'quirk(s) of code generation ... unique to a particular
compiler.' Before one begins source level 'optimizations' to speed up a
program, one should always do actual performance measurements rather
than relying on speculation and common sense."

Another place in his book:

"It is worth noting that with the optimizer off, performance(which common
sense says should be the same (direct member access versus inline access),
is in practice slower in the case of inline functions."

-- Saroj Mahapatra

Alex Vinokur

unread,
Mar 28, 1999, 3:00:00 AM3/28/99
to
In article <slrn7fnj6q....@bardeen.ceg.uiuc.edu>,

sbn...@KILL.uiuc.edu wrote:
> On 26 Mar 1999 10:23:54 -0500, Alex Vinokur
>
> > ##### Test#1 (access) #####
> >Test#1 [int_array] : Average time = 90 nsec
> >Test#1 [int_vector] : Average time = 354 nsec
> >Test#1 [int_string] : Average time = 1076 nsec
>
[snip]

>
> What optimization levels did you use? I did a similar test,
> using builtin fixed-sized arrays (the fastest that can be)
> double[N], and std::vector<double>(N). I found that with no
> optimization, the fixed size array method was definitely
> faster. But with -O1 optimization (which does inlining),
> both methods were about the same.
>
> Also, the vector::iterator method for repeated access is
> usually faster than the vector::operator[] method. Unless
> you use -O2 (or was it -O3), in which case both methods
> are identical.
>
[snip]

Hi,

Here are the experiment results using O0, O1, O2 and O3
optimization level (egcs compiler).

Alex.


//#########################################################
//---------- The results of the running : BEGIN -----------

### Test#1 (access to data element) ###
### Average time in nsec ###
===============================================
| : egcs optimization level |
| Data Type :---------------------------|
| : O0 : O1 : O2 : O3 |
|-----------------:------:------:------:------|
| int_array[i] : 88 : 20 : 29 : 33 |
| int_vector[i] : 393 : 24 : 33 : 43 |
| int_string[i] : 1252 : 925 : 105 : 135 |
| |
| char_array[i] : 100 : 18 : 32 : 31 |
| char_vector[i] : 409 : 18 : 34 : 34 |
| char_string[i] : 268 : 98 : 112 : 102 |
===============================================


### Test#2 (access to data element) ###
### Average time in nsec ###
===============================================
| : egcs optimization level |
| Data Type :---------------------------|
| : O0 : O1 : O2 : O3 |
|-----------------:------:------:------:------|
| int_array[i] : 113 : 23 : 33 : 31 |
| int_vector[i] : 390 : 20 : 33 : 32 |
| int_string[i] : 1148 : 856 : 100 : 105 |
| |
| char_array[i] : 109 : 19 : 27 : 30 |
| char_vector[i] : 371 : 21 : 28 : 31 |
| char_string[i] : 276 : 110 : 94 : 101 |
===============================================

### Test#3 (access to data element) ###
### Average time in nsec ###
===============================================
| : egcs optimization level |
| Data Type :---------------------------|
| : O0 : O1 : O2 : O3 |
|-----------------:------:------:------:------|
| int_array[i] : 94 : 21 : 27 : 31 |
| int_vector[i] : 408 : 20 : 32 : 36 |
| int_string[i] : 1216 : 853 : 122 : 94 |
| |
| char_array[i] : 92 : 18 : 27 : 27 |
| char_vector[i] : 366 : 20 : 27 : 27 |
| char_string[i] : 279 : 113 : 105 : 93 |
===============================================


### Test#4 (access to data element) ###
### Average time in nsec ###
===============================================
| : egcs optimization level |
| Data Type :---------------------------|
| : O0 : O1 : O2 : O3 |
|-----------------:------:------:------:------|
| int_array[i] : 87 : 21 : 30 : 31 |
| int_vector[i] : 395 : 20 : 32 : 36 |
| int_string[i] : 1205 : 881 : 107 : 94 |
| |
| char_array[i] : 93 : 23 : 33 : 30 |
| char_vector[i] : 374 : 21 : 32 : 30 |
| char_string[i] : 324 : 132 : 104 : 108 |
===============================================

### Test#5 (access to data element) ###
### Average time in nsec ###
===============================================
| : egcs optimization level |
| Data Type :---------------------------|
| : O0 : O1 : O2 : O3 |
|-----------------:------:------:------:------|
| int_array[i] : 93 : 19 : 29 : 29 |
| int_vector[i] : 402 : 20 : 31 : 30 |
| int_string[i] : 1210 : 868 : 98 : 109 |
| |
| char_array[i] : 98 : 18 : 33 : 31 |
| char_vector[i] : 376 : 18 : 32 : 32 |
| char_string[i] : 300 : 105 : 104 : 105 |
===============================================


//---------- The results of the running : END -------------

Anatoli

unread,
Mar 29, 1999, 3:00:00 AM3/29/99
to
In article <7dl5vc$s84$1...@nnrp1.dejanews.com>,
Alex Vinokur <alexande...@telrad.co.il> wrote:
[snip experiment results]

I repeated the experiment with EGCS-1.1.1, SGI Octane+IRIX6.4, -O4.
Vector is as fast as array (within 1-2% to either side)
while string is 2-3 times slower.

I've then modified basic_string<T> access to const basic_string<T>.
The access time become as fast as that of array or vector, again within
1-2%. I suspect it has to do with the copy-on-write implementation of
basic_string: before actual non-const access is done, basic_string<>
must check that reference count is 1, and if not, make a copy. The
slowdown is the direct result of this check.

I can't verify this by the instruction-level profiling, as my profiler chokes
on EGCS output :(
--
Regards
Anatoli (anatoli <at> ptc <dot> com) opinions aren't

Bill Wade

unread,
Mar 30, 1999, 3:00:00 AM3/30/99
to

Alex Vinokur wrote in message <7dl5vc$s84$1...@nnrp1.dejanews.com>...

> ### Average time in nsec ###
>===============================================
>| : egcs optimization level |
>| Data Type :---------------------------|
>| : O0 : O1 : O2 : O3 |
>|-----------------:------:------:------:------|
>| int_array[i] : 88 : 20 : 29 : 33 |
>| int_vector[i] : 393 : 24 : 33 : 43 |
>| int_string[i] : 1252 : 925 : 105 : 135 |
>| |
>| char_array[i] : 100 : 18 : 32 : 31 |
>| char_vector[i] : 409 : 18 : 34 : 34 |
>| char_string[i] : 268 : 98 : 112 : 102 |
>===============================================

>
> [ Why are string accesses so slow with optimized code? ]

I'd guess that your system uses a copy on write (COW) implementation for
string, but not for vector. Accessing non-const operator[] for COW
implementations involve at least an extra test (has this string been marked
unsharable yet?). For poorly written multi-threaded implementations it may
involve much more. Consider changing

char_string x;
TimeAccess(x);

to

char_string x;
const char_string& y = x;
TimeAccess(y);

and see what happens. The deeper answer to the "why" is that the
implementors probably thought that for vector it was important to optimize
op[], but for string it was more important to optimize copies. Try timing a
bunch of array, vector and string copies to see if they were successful.

0 new messages