C / C++ / MFC

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

Not Active

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