C / C++ / MFC

3-Jan-02 15:03

I thought STL was a bit more optimized than this. While I would expect and simple array to be faster I was surprised at the amount of difference. Using the two functions below I got the following timing results.

FooList: 0.0013247494 seconds
FooArray: 0.0000005587 seconds

std::list<DWORD> FooList()
{
	std::list<DWORD> list;
	for(int x = 0; x < 50; x++)
		list.push_back(x);

	return list;
}

void FooArray(DWORD* list)
{
	for(int x = 0; x < 50; x++)
		list[x] = x;
}

Christian Graus3-Jan-02 15:10

Christian Graus

3-Jan-02 15:10

It depends - what STL implimentation are you using ? I admit I've never done this sort of testing, but while I'd expect some overhead, I assume you're using the version that comes with VC for results as poor as this.

Christian

I have come to clean zee pooollll. - Michael Martin Dec 30, 2001

Sonork ID 100.10002:MeanManOzI live in Bob's HungOut now

Not Active4-Jan-02 1:18

4-Jan-02 1:18

I am using the VC version, never gave it a thought. What other implementations have you worked with?

Thomas Freudenberg4-Jan-02 1:45

Thomas Freudenberg

4-Jan-02 1:45

You are talking about arrays, but your sample uses std::list Confused | :confused:

Maybe you should change your code to following:

std::list<int> FooList()
{
    std::list<int> list;
    for(int x = 0; x < 50; x++)
        list.push_back(x);
    return list;
}

Regards
Thomas

Finally with Sonork id: 100.10453 Thömmi

Disclaimer:
Because of heavy processing requirements, we are currently using some of your unused brain capacity for backup processing. Please ignore any hallucinations, voices or unusual dreams you may experience. Please avoid concentration-intensive tasks until further notice. Thank you.

Tim Smith4-Jan-02 2:24

4-Jan-02 2:24

There is no way in hell a container class could ever be as optimized as an unbounded, well defined array fill.

Here are some of the differences between your FooArray and FooList.

1. As someone else pointed out, you are using a list and not a vector. A vector would be a more valid test.

2. std::vector does bounds checking and reallocates the data buffer using a doubling algorithm. Your FooArray routine does no bounds checking and is limited to only 50 elements.

3. Passing the list (or vector) is just a bit slower. You can double the performance by passing in a destination list into the routine via a reference.

4. Only runing the routine once is not a valid test. In my tests in release mode, executing each routine 10000 times yielded this information:

list - 6770 ms
vector - 841 ms
array - 30 ms

With the optimization of passing the list and vector into the routine:

list - 3175 ms
vector - 811 ms
array - 30 ms

If you don't destruct the list or vector each loop iteration and just invoke .clear on them, the numbers are as follows:

list - 3090 ms
vector - 290 ms
array - 30 ms

The final optimization I can think of is pre allocating the vector to size 50. However, that change made no difference. The reason being that the clear routine just sets the size back to zero and doesn't deallocate the vector data. Thus, since after the first pass the vector is already sized to 50, invoking reserve to preallocate the vector to 50 does nothing. Which shows the cost of all the memory allocation in vector. 800+ ms to 300 by removing all the allocations. Thus, vector has 270 ms of bookkeeping overhead that FooArray doesn't have.

5. Most optimizers can not handle deeply nested inlining well. It is very easy to optimize the hell out of FooArray. However, the compiler has much more trouble optimizing FooList since the implementation is deeply nested and more complex.

Tim Smith
Descartes Systems Sciences, Inc.

CodeGuy4-Jan-02 2:38

4-Jan-02 2:38

Great comments.

I wanted to point out on #2 that bounds checking with vector only happens if you use .at(). For the regular [] index method, there is no bounds checking with vector.

CodeGuy

The WTL newsgroup: over 1100 members! Be a part of it. http://groups.yahoo.com/group/wtl

Tim Smith4-Jan-02 7:20

4-Jan-02 7:20

Ah, you are right. I didn't know that.

Tim Smith
Descartes Systems Sciences, Inc.

Not Active4-Jan-02 9:46

4-Jan-02 9:46

I appreciate your comments.

Tim Smith wrote:
There is no way in hell a container class could ever be as optimized as an unbounded, well defined array fill.

I never expected to be able to accomplish this, merely get a little closer in performance. Using a vector instead of list does that. Wrong container on my part.

Tim Smith wrote:
2. std::vector does bounds checking and reallocates the data buffer using a doubling algorithm. Your FooArray routine does no bounds checking and is limited to only 50 elements.

Of course FooArray is only limited to 50 and does no bounds checking. This was only a simple example. Don't take it so seriously.

Tim Smith wrote:
4. Only runing the routine once is not a valid test. In my tests in release mode, executing each routine 10000 times yielded this information:

Who says I ran the test only once? I didn't think it necessary to post the results of each test run, only one to give as an example.

Tim Smith4-Jan-02 10:13

4-Jan-02 10:13

My point was that lists and vectors provide a rich feature set which have to come at some cost. From your reply it is obvious to me now this was something that you already understood. In the past I have run into many people who didn't understand this and thus the reason for my point.

As far as running the test routines multiple times, I was just trying to figure out why in your test, the list was a magnitude slower than the list in my tests. Maybe it was causes by differences between VC STL and STLPort that I use. I was thinking that you didn't run the test routines enough times in a tight loop. Another cause could have been debug instead of release build.

Tim Smith
Descartes Systems Sciences, Inc.

CodeGuy4-Jan-02 2:32

4-Jan-02 2:32

Why are you comparing apples and oranges? You need to compare vectors with arrays.

A fair comparison would be the following:

std::vector<int> FooVector()
{
std::vector<int> v(50);
for (int i=0; i<50; i++)
v[i] = i;

return v;
}

Also, on VC++, Herb Sutter has proved that deque is actually faster than vector, so you might consider trying comparisons with that as well.

CodeGuy

The WTL newsgroup: over 1100 members! Be a part of it. http://groups.yahoo.com/group/wtl

Tim Smith4-Jan-02 7:25

4-Jan-02 7:25

Hmm, I am going to have to look into DeQue and see how it stores the data (thus getting an idea of how it impacts resources and such.)

If you had to describe the data storage of DeQue in 100 words or less, how would you describe it?

Tim Smith
Descartes Systems Sciences, Inc.

CodeGuy4-Jan-02 8:12

4-Jan-02 8:12

Deque = double-ended queue.

It has the same basic functionality as vector, except it also has push_front function, for pushing data onto the front of the queue.

If you are interested in the Sutter article, it can be found at
http://www.gotw.ca/gotw/054.htm

CodeGuy

The WTL newsgroup: over 1100 members! Be a part of it. http://groups.yahoo.com/group/wtl

Tim Smith4-Jan-02 8:53

4-Jan-02 8:53

Ah, my first best guess was that deque was using some form of buckets. Smile | :)

It did look like his article didn't show that deques were faster than vectors, unless you used vectors in manners that specifically designed to perform better with deque (head inserts and deletes).

BUT, one thing I did like about deque is that it will generally have less wasted memory.

Tim Smith
Descartes Systems Sciences, Inc.

CodeGuy4-Jan-02 9:02

4-Jan-02 9:02

You're exactly right -- I didn't read the article closely enough. The performance advantages only come into play when you said: head inserts and deletes, which may not be necessary for most typical vector operations. Looking more closely, I guess his point was that deque was a better general-purpose container than a vector.

Thanks for keeping me straight.

CodeGuy

The WTL newsgroup: over 1100 members! Be a part of it. http://groups.yahoo.com/group/wtl

Not Active4-Jan-02 9:47