Pointer To A Vector Elements While Still Adding

[Ivan Vecerina]

Do you mean, if that is true? If you mean that, yes it is true. But I feel
like you meant something else(?).

I just meant the obvious: yes, you are right, but only
if there is actually a need to iterate.
If not, I'd rather just keep it simple.

Well, a typedef can solve these issues.

No:
- the typedef helps for encapsulation, but not
for removing dependencies
- with std::deque, iterators are invalidated by
push_back() and co, but pointers are preserved.


[about using 90 char lines]

Are there Usenet servers that wrap their messages?

I talked about clients. But well, you'll see.
I just gave my opinion since you had asked for it

Cheers,
Ivan

 

[Ioannis Vranos]

I just meant the obvious: yes, you are right, but only
if there is actually a need to iterate.
If not, I'd rather just keep it simple.

No:
- the typedef helps for encapsulation, but not
for removing dependencies
- with std::deque, iterators are invalidated by
push_back() and co, but pointers are preserved.

Yes, however there are cases that pointers get invalidated too in deque case. Pointers
can't really encapsulate from this. And you can't depend on pointers to randomly access
members of a list for example or even the next element, so the algorithm that you will use
is entirely upon the choice of the containers. In all cases, pointers can only provide
"surface" encapsulation about the type of the target container used, and the same
"surface" encapsulation can be provided by a typedef of the iterator type used.

Plus in all cases, you can access the next and previous object in the container by using
operators -- and ++ of the iterator, for all types of target containers.



--
Ioannis Vranos

http://www23.brinkster.com/noicys

[I am using 90 characters word-wrapping - (800/640) *72= 90 or better described as:
(800/640) *80 - 10 for quotation= 90. If someone finds it inconvenient, please let me know].

 

[John Carson]

John Carson wrote:


Your code tweaked and improved:

By making start and finish of type clock_t, you make this line:

cout << (finish - start)/CLOCKS_PER_SEC << endl;

perform integer division, so you get an integer result. This is anything but
an improvement. Cast one of those terms to a double in order to get a
non-zero result for vector.

C:\c>temp
List elapsed time is 2
Vector elapsed time is 0

C:\c>


Of course if I had reserved enough space for vector before, they
would have the same performance.

What? Your figures show vector with superior performance (infinitely
superior, actually, but I won't claim that) and you think that reserving
enough space for the vector would even things up?

Check the table in 17.1.2 on page 464 of TC++PL3.


Vectors have no additional time-cost advantage than lists for back
operations, list has O(1) while vector has O(1)+ (the + is when
reallocations take place). You have O(1) for back operations with
vector while its size() is smaller its capacity() (which can be
adjusted with reserve()).

You seem to be under the impression that O properties say all that is
relevant. All O results tell you is how time varies with n. They tell you
nothing about the base time when n==1. Two operations can both be O(1) yet
one operation can take a million times as long as the other.

As I understand it, when you add an element to the end of a list, memory is
allocated for that final element with a call to new. Calls to new are
expensive.

When you add an element to the end of a vector, there is no call to new if
there is sufficient capacity. This makes the vector operation quicker than
the list operation. If there is insufficient capacity in the vector, then
new memory is allocated and all elements need to be copied over from the old
memory to the new. This makes the vector operation slower than the list
operation.

You seem to be misunderstanding the meaning of O(1)+. This does not mean
"more than O(1)". It means, to quote Stroustrup, that "occasionally a
significant extra cost is incurred" --- extra relative to what normally
happens, not extra relative to what is required for O(1) performance.

To further explain: capacity is added to vectors by multiplying pre-existing
capacity by some constant factor. This means that the number of calls to new
diminishes relative to n as n increases, e.g., if you start with a capacity
of 1 and double each time, then you need 3 calls to get 8 elements, and 6
calls to get 64 elements. Thus with 8 elements, each element requires 3/8 of
a call to new, whereas with 64 elements each element requires 6/64 of a call
to new. With 1 million elements, each element requires roughly 1/50,000 of a
call to new. Thus this aspect of insertion is *less* than O(1). (This
argument assumes that calls to new cost the same regardless of the amount of
memory allocated which probably isn't true, especially when the vector gets
large; this qualification, however, doesn't seem sufficiently important to
overturn the conclusion in most cases.) The total amount of copying from old
memory to new is proportionate to n, so this aspect is O(1).

On two computers (a slow Pentium II and a fast laptop), I get a consistent
result that adding to the back of list takes around the same amount of time
regardless of whether it is 1 million elements to a single list or 100
elements to 10,000 lists.

With a vector, by contrast, adding 1 million elements to a single vector
takes about half the time it takes to add 100 elements to 10,000 vectors.
This is consistent with my "less than O(1)" argument above.

When the number of elements gets larger, the story becomes more complicated
(the peculiarities of the memory manager come into play and stack memory
becomes an issue, given that I declared the arrays on the stack, so it is
better to allocate them statically). Neither container seems to have O(1)
performance. However, it remains the case that

1. the vector is faster than the list.
2. the vector is 2-6 times faster when using a single large container than
when using multiple small containers for the same total capacity.

Of course, vector memory must be contiguous, so vectors may have problems if
memory becomes fragmented.

 

[Ioannis Vranos]

By making start and finish of type clock_t, you make this line:



perform integer division, so you get an integer result. This is anything
but
an improvement. Cast one of those terms to a double in order to get a
non-zero result for vector.

Or (better I think) we should not divide with CLOCKS_PER_SEC in the first place.

What? Your figures show vector with superior performance (infinitely
superior, actually, but I won't claim that) and you think that reserving
enough space for the vector would even things up?

Damn. I am a bit careless today!! On the other hand I was just experimenting with
vector vs deque (because if you check 17.1.2 container table of TC++PL 3, you will see
that deque has equal or better Big-O performance in equivalent operations, and in addition
it provides front operations with O(1) cost.

Still, *vector* is the currently suggested general-purpose container and not deque.
However my measurements for the same Back operations so far:


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

int main()
{
using namespace std;

clock_t start, finish, temp;

deque<int> d;
vector<int> v;

const unsigned long loopSize = numeric_limits<unsigned long>::max()/100;

// Wait to begin from a clear tick for accurate results
for(temp=start=clock(); start-temp!=0; start=clock())
;

for(unsigned long i=0; i<loopSize; ++i)
d.push_back(5);

finish = clock();

cout << "Deque elapsed time is ";
cout << finish - start <<"\n";

// Wait to begin from a clear tick for accurate results
for(temp=start=clock(); start-temp!=0; start=clock())
;

for(unsigned long i=0; i<loopSize; ++i)
v.push_back(5);

finish = clock();

cout << "Vector elapsed time is ";
cout << finish - start << "\n";
}


C:\c>temp
Deque elapsed time is 1241
Vector elapsed time is 2724

C:\c>


However in Big-O notation, you get equivalent performance with list as far as you do not
exceed capacity. I guess the top performance of them are different, since Big-O is about
performance in relation to the same operation itself since the beginning, and how it
scales on load.


I am going to measure more vector vs deque operations tomorrow.

You seem to be under the impression that O properties say all that is
relevant. All O results tell you is how time varies with n. They tell you
nothing about the base time when n==1. Two operations can both be O(1) yet
one operation can take a million times as long as the other.

Yes you are right.

As I understand it, when you add an element to the end of a list, memory is
allocated for that final element with a call to new. Calls to new are
expensive.

When you add an element to the end of a vector, there is no call to new if
there is sufficient capacity.

It has to do with allocators, about which I do not know much so far (chapter 19 of
TC++PL3). But the one used in vector, uses new by default.

In any case as far as I know, one new object gets created with copy constructor called. If
copy constructor is disabled, as in the following example, I can't understand the results:

#include <iostream>
#include <vector>

class SomeClass
{
public:
SomeClass() { std::cout<<"Default constructor called!\n"; }
//SomeClass(const SomeClass &) { std::cout<<"Copy Constructor called!\n"; }
~SomeClass() { std::cout<<"Destructor called!\n"; }
const SomeClass &operator=(const SomeClass &) { std::cout<<"Assignment operator
called!\n"; return *this; }
SomeClass &operator=(SomeClass &) { std::cout<<"Assignment operator called!\n";
return *this; }
};


int main()
{
using namespace std;

vector<SomeClass> vec;

SomeClass obj;

vec.push_back(obj);
}

C:\c>temp2
Default constructor called!
Destructor called!
Destructor called!

C:\c>


With VC++ 2003 things are more confusing:

C:\c>temp2
Default constructor called!
Destructor called!
Destructor called!
Destructor called!

C:\c>

This makes the vector operation quicker than
the list operation. If there is insufficient capacity in the vector, then
new memory is allocated and all elements need to be copied over from the
old
memory to the new. This makes the vector operation slower than the list
operation.

I agree with this in general.

You seem to be misunderstanding the meaning of O(1)+. This does not mean
"more than O(1)". It means, to quote Stroustrup, that "occasionally a
significant extra cost is incurred" --- extra relative to what normally
happens, not extra relative to what is required for O(1) performance.

Yes.


To further explain: capacity is added to vectors by multiplying
pre-existing
capacity by some constant factor.

As far as I can understand, this is not required by the standard, but I suppose you mean
it is what most/some implementations do.

This means that the number of calls to
new
diminishes relative to n as n increases, e.g., if you start with a capacity
of 1 and double each time, then you need 3 calls to get 8 elements, and 6
calls to get 64 elements. Thus with 8 elements, each element requires
3/8 of
a call to new, whereas with 64 elements each element requires 6/64 of a
call
to new. With 1 million elements, each element requires roughly 1/50,000
of a
call to new. Thus this aspect of insertion is *less* than O(1).

Yes. I assume the O(1) considered in TC++PL is the insertion at the end with enough
reserved space, considering reallocations something like an "extraordinary" event.

(This
argument assumes that calls to new cost the same regardless of the
amount of
memory allocated which probably isn't true, especially when the vector gets
large;

plus the copying cost.

this qualification, however, doesn't seem sufficiently important to
overturn the conclusion in most cases.) The total amount of copying from
old
memory to new is proportionate to n, so this aspect is O(1).

So the copying is O(n) I guess.

On two computers (a slow Pentium II and a fast laptop), I get a consistent
result that adding to the back of list takes around the same amount of time
regardless of whether it is 1 million elements to a single list or 100
elements to 10,000 lists.

With a vector, by contrast, adding 1 million elements to a single vector
takes about half the time it takes to add 100 elements to 10,000
vectors. This is consistent with my "less than O(1)" argument above.

When the number of elements gets larger, the story becomes more
complicated (the peculiarities of the memory manager come into play and
stack memory becomes an issue, given that I declared the arrays on the
stack, so it is better to allocate them statically).

What arrays?

Neither container
seems to have O(1) performance. However, it remains the case that

1. the vector is faster than the list.
2. the vector is 2-6 times faster when using a single large container
than when using multiple small containers for the same total capacity.

Of course, vector memory must be contiguous, so vectors may have
problems if
memory becomes fragmented.

In general we agree. vector's before-reallocation-performance seems to be better than
list's when compared, in the implementations we are using. Big-O notation is about how an
operation/algorithm scales in relation to load, and is not about performance among
separate algorithms.

Also the Big-O characteristics of deque are the same or better than vector's on the same
operations, while it also provides front operations with O(1) cost.


From the test of mine, mentioned in the beginning, it looks like deque is more efficient
than vector for back operations, in the implementations that I am using. I am going to
check the remaining operations tomorrow.




--
Ioannis Vranos

http://www23.brinkster.com/noicys

[I am using 90 characters word-wrapping - (800/640) *72= 90 or better described as:
(800/640) *80 - 10 for quotation= 90. If someone finds it inconvenient, please let me know].

 

[John Carson]

John Carson wrote:

int main()
{
using namespace std;

clock_t start, finish, temp;

deque<int> d;
vector<int> v;

const unsigned long loopSize = numeric_limits<unsigned
long>::max()/100;
// Wait to begin from a clear tick for accurate results
for(temp=start=clock(); start-temp!=0; start=clock())
;

for(unsigned long i=0; i<loopSize; ++i)
d.push_back(5);

finish = clock();

cout << "Deque elapsed time is ";
cout << finish - start <<"\n";

// Wait to begin from a clear tick for accurate results
for(temp=start=clock(); start-temp!=0; start=clock())
;

for(unsigned long i=0; i<loopSize; ++i)
v.push_back(5);

finish = clock();

cout << "Vector elapsed time is ";
cout << finish - start << "\n";
}


C:\c>temp
Deque elapsed time is 1241
Vector elapsed time is 2724

Have you tried reversing the order: vector first and then deque? When I do
this it reverses the result. I also find that the result is reversed if I
reduce the loopSize by a factor of 10 --- even with the original order of
deque first.

This suggests to me that, at least on my computer, your code gets to the
region where memory allocation is a bottleneck. Going first is a big
advantage in that case. Your computer has more memory than mine, so that may
not be the case for you. In any case, memory shortages may be more of a
problem for vector because of its requirement that its memory be contiguous.
Nevertheless, a fair test should really test the two containers separately.
(My original code had list go first and since list took longer than vector,
reversing the order could only reinforce the result.) When I test the two
containers separately, vector only takes about 2/3 as long as deque.

So the copying is O(n) I guess.

No, if you add n elements, then roughly n elements get copied during
re-allocation. Suppose we start with a single element vector and double
capacity each time. When we double to 2, we copy 1. When we double to 4 we
copy 2. When we double to 8, we copy 4. Thus the number of elements copied
is

1 + 2 + 4 + 8 + ... pow(2,n-1)

for a vector of final capacity pow(2,n). The sum of these terms equals
pow(2,n) - 1. Thus total copying is proportional to capacity, which means
that the cost per insertion is constant, hence O(1). (If the growth factor
is less than 2, then this means that the total number of elements copied is
some multiple greater than 1 of capacity, which means it is still
proportional to capacity.)

What arrays?

list<int> l_array[arraySize];

In general we agree. vector's before-reallocation-performance seems
to be better than list's when compared, in the implementations we are
using.

Why "before reallocation". My tests involve plenty of re-allocating since I
didn't use reserve() at all.

 

[Ioannis Vranos]

Have you tried reversing the order: vector first and then deque? When I
do this it reverses the result. I also find that the result is reversed
if I reduce the loopSize by a factor of 10 --- even with the original
order of deque first.

When I use vector first and then deque the same results remain here:

C:\c>temp
Vector elapsed time is 2393
Deque elapsed time is 1512

C:\c>


Are you sure you did not make some mistake? Try with this simpler code:


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



template<class T>
inline clock_t TestBackOperation(const std::size_t LOOPSIZE)
{
using namespace std;

T container;

// Value assigned
typename T::value_type value= 1;

clock_t start, finish, temp;

// Performs the test.
// Wait to begin from a clear tick for accurate results
for(temp=start=clock(); start-temp!=0; start=clock())
;

for(size_t i=0; i<LOOPSIZE; ++i)
container.push_back(value++);

finish = clock();

return finish - start;
}


int main()
{
using namespace std;

const size_t LOOPSIZE= numeric_limits<size_t>::max()/100;

clock_t vectorTiming= TestBackOperation< vector<int> >(LOOPSIZE);
cout << "vector<int> elapsed time is " << vectorTiming << "\n";

clock_t dequeTiming= TestBackOperation< deque<int> >(LOOPSIZE);
cout << "deque<int> elapsed time is " << dequeTiming<< "\n";

cout<<"CLOCKS_PER_SEC= "<<CLOCKS_PER_SEC<<"\n";
}


In my system this outputs:

C:\c>temp
vector<int> elapsed time is 2423
deque<int> elapsed time is 1432
CLOCKS_PER_SEC= 1000

C:\c>



I am not sure if some test suite about relative standard container performance of an
implementation exists, but I may write some basic one these days.

This suggests to me that, at least on my computer, your code gets to the
region where memory allocation is a bottleneck. Going first is a big
advantage in that case. Your computer has more memory than mine, so that
may not be the case for you. In any case, memory shortages may be more
of a problem for vector because of its requirement that its memory be
contiguous. Nevertheless, a fair test should really test the two
containers separately. (My original code had list go first and since
list took longer than vector, reversing the order could only reinforce
the result.) When I test the two containers separately, vector only
takes about 2/3 as long as deque.

In the above code you may adjust the LOOPSIZE, however comparing results less than
CLOCKS_PER_SEC is unreliable.

No, if you add n elements, then roughly n elements get copied during
re-allocation. Suppose we start with a single element vector and double
capacity each time. When we double to 2, we copy 1. When we double to 4
we copy 2. When we double to 8, we copy 4. Thus the number of elements
copied is

1 + 2 + 4 + 8 + ... pow(2,n-1)

for a vector of final capacity pow(2,n). The sum of these terms equals
pow(2,n) - 1.

And if I am not mistaken the above means that our worst case *reallocation* performance is
O(2^n).

Thus total copying is proportional to capacity, which
means that the cost per insertion is constant, hence O(1).

plus the reallocation performance, that's why it is mentioned O(1)+ in TC++PL3.

What arrays?

list<int> l_array[arraySize];
vector<int> v_array[arraySize];

I do not understand what you mean here. list (which is not an array) and vector are
allocated on the stack, however their elements are stored in the free store.




--
Ioannis Vranos

http://www23.brinkster.com/noicys

[I am using 90 characters word-wrapping - (800/640) *72= 90 or better described as:
(800/640) *80 - 10 for quotation= 90. If someone finds it inconvenient, please let me know].

 

[Ioannis Vranos]

Try with this simpler code:

A bit improved version also testing std::string and a user-defined type:


#include <vector>
#include <deque>
#include <ctime>
#include <iostream>
#include <limits>
#include <list>
#include <string>

class SomeClass;


template<class ContainerType, class ValueType>
inline clock_t TestBackOperation(const ValueType &value, const std::size_t LOOPSIZE)
{
using namespace std;

ContainerType container;

clock_t start, finish, temp;

// Performs the test.
// Wait to begin from a clear tick for accurate results
for(temp=start=clock(); start-temp!=0; start=clock())
;

for(size_t i=0; i<LOOPSIZE; ++i)
container.push_back(value);

finish = clock();

return finish - start;
}


class SomeClass
{
std::string s;

public:
SomeClass(const std::string &value): s(value) {}
};


int main()
{
using namespace std;

const size_t LOOPSIZE= numeric_limits<size_t>::max()/100;

cout<<"CLOCKS_PER_SEC= "<<CLOCKS_PER_SEC<<"\n";

clock_t timing= TestBackOperation< vector<int> >(1, LOOPSIZE);
cout << "vector<int> elapsed time is " << timing << "\n";

timing= TestBackOperation< deque<int> >(1, LOOPSIZE);
cout << "deque<int> elapsed time is " << timing<< "\n";

timing= TestBackOperation< list<int> >(1, LOOPSIZE);
cout << "list<int> elapsed time is " << timing << "\n";

timing= TestBackOperation< string >(1, LOOPSIZE);
cout << "string elapsed time is " << timing << "\n";


timing= TestBackOperation< vector<SomeClass>, string >("Test String", LOOPSIZE);
cout << "vector<SomeClass> elapsed time is " << timing << "\n";

timing= TestBackOperation< deque<SomeClass>, string >("Test String", LOOPSIZE);
cout << "deque<SomeClass> elapsed time is " << timing<< "\n";

timing= TestBackOperation< list<SomeClass>, string >("Test String", LOOPSIZE);
cout << "list<SomeClass> elapsed time is " << timing << "\n";
}


In my system with MINGW GCC 3.4.2, it outputs:

C:\c>temp
CLOCKS_PER_SEC= 1000
vector<int> elapsed time is 2273
deque<int> elapsed time is 1151
list<int> elapsed time is 36552
string elapsed time is 5718
vector<SomeClass> elapsed time is 29663
deque<SomeClass> elapsed time is 14201
list<SomeClass> elapsed time is 50633

C:\c>





--
Ioannis Vranos

http://www23.brinkster.com/noicys

[I am using 90 characters word-wrapping - (800/640) *72= 90 or better described as:
(800/640) *80 - 10 for quotation= 90. If someone finds it inconvenient, please let me know].

 

[John Carson]

When I use vector first and then deque the same results remain here:

C:\c>temp
Vector elapsed time is 2393
Deque elapsed time is 1512

C:\c>


Are you sure you did not make some mistake? Try with this simpler
code:

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



template<class T>
inline clock_t TestBackOperation(const std::size_t LOOPSIZE)
{
using namespace std;

T container;

// Value assigned
typename T::value_type value= 1;

clock_t start, finish, temp;

// Performs the test.
// Wait to begin from a clear tick for accurate results
for(temp=start=clock(); start-temp!=0; start=clock())
;

for(size_t i=0; i<LOOPSIZE; ++i)
container.push_back(value++);

finish = clock();

return finish - start;
}


int main()
{
using namespace std;

const size_t LOOPSIZE= numeric_limits<size_t>::max()/100;

clock_t vectorTiming= TestBackOperation< vector<int> >(LOOPSIZE);
cout << "vector<int> elapsed time is " << vectorTiming << "\n";

clock_t dequeTiming= TestBackOperation< deque<int> >(LOOPSIZE);
cout << "deque<int> elapsed time is " << dequeTiming<< "\n";

cout<<"CLOCKS_PER_SEC= "<<CLOCKS_PER_SEC<<"\n";
}


In my system this outputs:

C:\c>temp
vector<int> elapsed time is 2423
deque<int> elapsed time is 1432
CLOCKS_PER_SEC= 1000

C:\c>

On my system (VC++ 7.1, Windows XP, 512 Mb memory) it outputs:

vector<int> elapsed time is 2713
deque<int> elapsed time is 4457
CLOCKS_PER_SEC= 1000

Reversing the order doesn't save deque:

deque<int> elapsed time is 4526
vector<int> elapsed time is 2874
CLOCKS_PER_SEC= 1000

And if I am not mistaken the above means that our worst case
*reallocation* performance is O(2^n).

If by "reallocation performance", you mean the cost of a single insertion
when re-allocation takes place at that insertion, then you are correct. The
other side is that such re-allocation becomes less frequent at the same rate
as it becomes more costly.

plus the reallocation performance, that's why it is mentioned O(1)+
in TC++PL3.

Average cost per insertion, including reallocation cost, is constant (unless
you start to run out of memory). Having an occasional very costly insertion
may nevertheless be a problem for some applications. As Stroustrup remarks:
"I added the + for the benefit of programmers who care about predictability
in addition to average performance."

What arrays?

list<int> l_array[arraySize];
vector<int> v_array[arraySize];

I do not understand what you mean here. list (which is not an array)
and vector are allocated on the stack, however their elements are
stored in the free store.

list<int> l_array[arraySize];

is an array of lists. Using VC++ 7.1, sizeof (list<int>) is 12 and
sizeof(vector<int>) is 16. This means that if you have an array of 100,000
list<int> and an array of 100,000 vector<int>, then you are allocating
2,800,000 bytes on the stack *before* you have added *any* elements. This
exceeds the default stack size on VC++.

 

[Ioannis Vranos]

On my system (VC++ 7.1, Windows XP, 512 Mb memory) it outputs:

vector<int> elapsed time is 2713
deque<int> elapsed time is 4457
CLOCKS_PER_SEC= 1000

Reversing the order doesn't save deque:

deque<int> elapsed time is 4526
vector<int> elapsed time is 2874
CLOCKS_PER_SEC= 1000

Yes the same with Intel C++ 8.1. However in MINGW GCC 3.4.2 deque is faster than all.


BTW the most recent version of the test program, I will be using version numbers from now
on for convenience, this is 0.2:


// 0.2

#include <vector>
#include <deque>
#include <ctime>
#include <iostream>
#include <limits>
#include <list>
#include <string>

class SomeClass;


template< template<class> class ContainerTemplate, class ValueType>
inline clock_t TestBackOperation(const ValueType &value, const std::size_t LOOPSIZE)
{
using namespace std;

ContainerTemplate<ValueType> container;

clock_t start, finish, temp;

// Performs the test.
// Wait to begin from a clear tick for accurate results
for(temp=start=clock(); start-temp!=0; start=clock())
;

for(size_t i=0; i<LOOPSIZE; ++i)
container.push_back(value);

finish = clock();

return finish - start;
}


class SomeClass
{
std::string s;

public:
SomeClass(const std::string &value): s(value) {}
};


int main()
{
using namespace std;

const size_t LOOPSIZE= numeric_limits<size_t>::max()/100;

cout<<"\nCLOCKS_PER_SEC= "<<CLOCKS_PER_SEC<<"\n\n";

clock_t timing= TestBackOperation<basic_string, char>(1, LOOPSIZE);
cout << "string elapsed time is " << timing << "\n";

timing= TestBackOperation<vector, int>(1, LOOPSIZE);
cout << "vector<int> elapsed time is " << timing << "\n";

timing= TestBackOperation<deque, int>(1, LOOPSIZE);
cout << "deque<int> elapsed time is " << timing<< "\n";

timing= TestBackOperation<list, int>(1, LOOPSIZE);
cout << "list<int> elapsed time is " << timing << "\n";


timing= TestBackOperation<vector, SomeClass>(string("Test String"), LOOPSIZE);
cout << "\nvector<SomeClass> elapsed time is " << timing << "\n";

timing= TestBackOperation<deque, SomeClass>(string("Test String"), LOOPSIZE);
cout << "deque<SomeClass> elapsed time is " << timing<< "\n";

timing= TestBackOperation<list, SomeClass>(string("Test String"), LOOPSIZE);
cout << "list<SomeClass> elapsed time is " << timing << "\n";
}


Compiled with MINGW GCC 3.4.2 it outputs:

C:\c>temp

CLOCKS_PER_SEC= 1000

string elapsed time is 5457
vector<int> elapsed time is 2374
deque<int> elapsed time is 1081
list<int> elapsed time is 37604

vector<SomeClass> elapsed time is 21691
deque<SomeClass> elapsed time is 6619
list<SomeClass> elapsed time is 42512

C:\c>



What I can not understand here is the performance of list. Why it has such a big cost in
the first place. Deque is also using pointers inside its implementation.

I do not understand what you mean here. list (which is not an array)
and vector are allocated on the stack, however their elements are
stored in the free store.

list<int> l_array[arraySize];

is an array of lists. Using VC++ 7.1, sizeof (list<int>) is 12 and
sizeof(vector<int>) is 16. This means that if you have an array of
100,000 list<int> and an array of 100,000 vector<int>, then you are
allocating 2,800,000 bytes on the stack *before* you have added *any*
elements. This exceeds the default stack size on VC++.

May you provide an example where sizeof operator returns 2,800,000 bytes?

A vector<list<int> > just stores list<int> in the free store which also store their ints
in the free store.



--
Ioannis Vranos

http://www23.brinkster.com/noicys

[I am using 90 characters word-wrapping - (800/640) *72= 90 or better described as:
(800/640) *80 - 10 for quotation= 90. If someone finds it inconvenient, please let me know].

 

[John Carson]

Yes the same with Intel C++ 8.1. However in MINGW GCC 3.4.2 deque is
faster than all.

So, compared to Intel C++ 8.1, does MINGW GCC 3.4.2 have a fast deque or a
slow vector or both?

Compiled with MINGW GCC 3.4.2 it outputs:

C:\c>temp

CLOCKS_PER_SEC= 1000

string elapsed time is 5457
vector<int> elapsed time is 2374
deque<int> elapsed time is 1081
list<int> elapsed time is 37604

vector<SomeClass> elapsed time is 21691
deque<SomeClass> elapsed time is 6619
list<SomeClass> elapsed time is 42512

C:\c>



What I can not understand here is the performance of list. Why it has
such a big cost in the first place. Deque is also using pointers
inside its implementation.

I think it is because list calls new for each insertion, whereas vector and
deque only do it occasionally.

May you provide an example where sizeof operator returns 2,800,000
bytes?

So as not to exceed the stack capacity, I will declare the arrays at global
scope:

#include <iostream>
#include <vector>
#include <list>

using namespace std;

const size_t arraySize = 100000;

list<int> l_array[arraySize];
vector<int> v_array[arraySize];

int main()
{
cout << "sizeof(l_array) is " << sizeof(l_array)<< " bytes\n";
cout << "sizeof(v_array) is " << sizeof(v_array)<< " bytes\n";
cout << "total size is " << sizeof(l_array)+sizeof(v_array) << "
bytes\n";
}

Outputs:

sizeof(l_array) is 1200000 bytes
sizeof(v_array) is 1600000 bytes
total size is 2800000 bytes

A vector<list<int> > just stores list<int> in the free store which
also store their ints in the free store.

Yes, but I didn't use a vector, I used an array.

 

[Ioannis Vranos]

So, compared to Intel C++ 8.1, does MINGW GCC 3.4.2 have a fast deque or a
slow vector or both?

Basically I guess we are concerned about the relevant performance of containers in an
implementation and not comparison between them. However for the code (which uses smaller
number of elements so as to increase test run-time and space):


// 0.26

#include <vector>
#include <deque>
#include <ctime>
#include <iostream>
#include <limits>
#include <list>
#include <string>
#include <exception>

class SomeClass;


template<class ContainerType, class ValueType>
clock_t TestBackOperation(const ValueType &value, const std::size_t LOOPSIZE)
{
using namespace std;

ContainerType container;

clock_t start, finish, temp;

// Performs the test.
// Wait to begin from a clear tick for accurate results
for(temp=start=clock(); start-temp!=0; start=clock())
;

for(size_t i=0; i<LOOPSIZE; ++i)
container.push_back(value);

finish = clock();

return finish - start;
}


class SomeClass
{
std::string s;

public:
SomeClass(const std::string &value): s(value) {}
};


int main() try
{
using namespace std;

const size_t LOOPSIZE= numeric_limits<size_t>::max()/1000;

cout<<"\nCLOCKS_PER_SEC= "<<CLOCKS_PER_SEC<<"\n\n";

clock_t timing= TestBackOperation<string>(1, LOOPSIZE);
cout << "string elapsed time is " << timing << "\n";

timing= TestBackOperation<vector<int> >(1, LOOPSIZE);
cout << "vector<int> elapsed time is " << timing << "\n";

timing= TestBackOperation<deque<int> >(1, LOOPSIZE);
cout << "deque<int> elapsed time is " << timing<< "\n";

timing= TestBackOperation<list<int> >(1, LOOPSIZE);
cout << "list<int> elapsed time is " << timing << "\n";


timing= TestBackOperation<vector<SomeClass> >(string("Test String"), LOOPSIZE);
cout << "\nvector<SomeClass> elapsed time is " << timing << "\n";

timing= TestBackOperation<deque<SomeClass> >(string("Test String"), LOOPSIZE);
cout << "deque<SomeClass> elapsed time is " << timing<< "\n";

timing= TestBackOperation<list<SomeClass> >(string("Test String"), LOOPSIZE);
cout << "list<SomeClass> elapsed time is " << timing << "\n";
}


catch(std::exception &e)
{
std::cerr<<e.what()<<"\n";
}


with MINGW GCC 3.4.2 it outputs:

C:\c>temp

CLOCKS_PER_SEC= 1000

string elapsed time is 560
vector<int> elapsed time is 261
deque<int> elapsed time is 120
list<int> elapsed time is 3315

vector<SomeClass> elapsed time is 3255
deque<SomeClass> elapsed time is 1392
list<SomeClass> elapsed time is 4487

C:\c>


and VC++ 2003 (with /EHsc /O2 /G6):


C:\c>temp

CLOCKS_PER_SEC= 1000

string elapsed time is 640
vector<int> elapsed time is 311
deque<int> elapsed time is 611
list<int> elapsed time is 2013

vector<SomeClass> elapsed time is 6058
deque<SomeClass> elapsed time is 3395
list<SomeClass> elapsed time is 3695

C:\c>


You can use them to draw your conclusions.



We should note that the list timings have been improved with the smaller number of
elements, so I presume memory starvation was causing larger timings before.

Also when using the user-defined type SomeClass, deque is faster in both compilers.



--
Ioannis Vranos

http://www23.brinkster.com/noicys

[I am using 90 characters word-wrapping - (800/640) *72= 90 or better described as:
(800/640) *80 - 10 for quotation= 90. If someone finds it inconvenient, please let me know].

 

[Ioannis Vranos]

However
for the code (which uses smaller number of elements so as to
decrease

test run-time and space):

--
Ioannis Vranos

http://www23.brinkster.com/noicys

[I am using 90 characters word-wrapping - (800/640) *72= 90 or better described as:
(800/640) *80 - 10 for quotation= 90. If someone finds it inconvenient, please let me know].

 

[John Carson]

with MINGW GCC 3.4.2 it outputs:

C:\c>temp

CLOCKS_PER_SEC= 1000

string elapsed time is 560
vector<int> elapsed time is 261
deque<int> elapsed time is 120
list<int> elapsed time is 3315

vector<SomeClass> elapsed time is 3255
deque<SomeClass> elapsed time is 1392
list<SomeClass> elapsed time is 4487

C:\c>


and VC++ 2003 (with /EHsc /O2 /G6):


C:\c>temp

CLOCKS_PER_SEC= 1000

string elapsed time is 640
vector<int> elapsed time is 311
deque<int> elapsed time is 611
list<int> elapsed time is 2013

vector<SomeClass> elapsed time is 6058
deque<SomeClass> elapsed time is 3395
list<SomeClass> elapsed time is 3695

C:\c>


You can use them to draw your conclusions.

Interesting. My conclusion is that MINGW GCC 3.4.2 has a very fast deque
implementation.

We should note that the list timings have been improved with the
smaller number of elements, so I presume memory starvation was
causing larger timings before.

The picture seems rather complicated to me. List does pretty badly storing
ints and improves relatively when storing SomeClass, which requires a lot
more memory (see below). The effect of memory starvation on the relative
speed of the different containers doesn't appear to be monotonic, if indeed
memory starvation is behind the variation.

Also when using the user-defined type SomeClass, deque is faster in
both compilers.

Yes, I get the same result with VC++ 7.1 (I had to reduce the number of
loops because the program was "exiting abnormally" with the original count).
This appears to be a matter of the size of the object stored rather than
anything to do with constructors etc. sizeof(SomeClass) is 28. If you
replace int with the POD type:

struct IntArray
{
int array[7];
};

to create a 28 byte object, then deque has a similar performance advantage
with IntArray to the one it has with SomeClass.

 

[Ioannis Vranos]

Yes, I get the same result with VC++ 7.1 (I had to reduce the number of
loops because the program was "exiting abnormally" with the original
count).

And you are probably using an older version than the provided. What you get is bad_alloc
thrown, and the last version displays this.

This appears to be a matter of the size of the object stored
rather than anything to do with constructors etc. sizeof(SomeClass) is
28.

Yes, you are running out of heap.

If you replace int with the POD type:

struct IntArray
{
int array[7];
};

to create a 28 byte object, then deque has a similar performance
advantage with IntArray to the one it has with SomeClass.

Yes.


--
Ioannis Vranos

http://www23.brinkster.com/noicys

[I am using 90 characters word-wrapping - (800/640) *72= 90 or better described as:
(800/640) *80 - 10 for quotation= 90. If someone finds it inconvenient, please let me know].

 

[Ioannis Vranos]

And you are probably using an older version

of the code

than the provided. What you
get is bad_alloc thrown, and the last version displays this.

This appears to be a matter of the size of the object stored rather
than anything to do with constructors etc. sizeof(SomeClass) is 28.

Yes, you are running out of heap.

If you replace int with the POD type:

struct IntArray
{
int array[7];
};

to create a 28 byte object, then deque has a similar performance
advantage with IntArray to the one it has with SomeClass.

Yes.

--
Ioannis Vranos

http://www23.brinkster.com/noicys

[I am using 90 characters word-wrapping - (800/640) *72= 90 or better described as:
(800/640) *80 - 10 for quotation= 90. If someone finds it inconvenient, please let me know].