|
I'm sure this topic has been discussed to death, I know I've read a number of posts arguing both sides. But I would like some solid evidence supporting both arguments. So, what I've decided to do is write up some routines that will test the collections in both MFC and STL on the same ground. If anyone has knows of similar tests that are on the web or elsewhere, I would greatly appreciate the references.
The output of my tests are below and I would be happy to submit the code if desired. As I am just getting into learning STL (I purchased "The Standard C++ Library" by Nicolai M. Josuttis resently) I am only testing vector against CArray at the moment and only under add and remove of integer values.
There were 6 tests. I first tested vector<int> without reserving any space, then with reserving an equal number of elements as loops - both previous tests using .push_back() - and the third reserving and accessing each element with [].
The next 3 tests were with CArray<int, int>; first without using .SetSize() and using .Add(), the next using .SetSize() and .Add() and the final using .SetSize() and .SetAt().
All values added were the element number * rand()
Are my tests poorly devised? Thank you for any input you can offer.
John
These tests were done with VC6 SP5 on a 1ghz Celeron with 256 megs of RAM
Performing test with 1000000 loops
Added without reserve to Vector<int> in 1.36 seconds
Removed all Vector<int> elements in 0.14 seconds
Added with reserve and push_back to Vector<int> in0.922 seconds
Removed all Vector<int> elements in 0.141 seconds
Added with reserve and [] to Vector<int> in 0.203 seconds
Removed all Vector<int> elements in 0 seconds
Added without SetSize to CArray<int, int> in 252.828 seconds
Removed all CArray elements in 0.031 seconds
Added with SetSize and Add to CArray<int, int> in 768.796 seconds
Removed all CArray elements in 0.047 seconds
Added with SetSize and SetAt to CArray<int, int> in 0.156 seconds
Removed all CArray elements in 0.031 seconds
These tests were performed on a 800MHz Duron with 256 megs of RAM
Performing test with 1000000 loops
Added without reserve to Vector<int> in 1.852 seconds
Removed all Vector<int> elements in 0.181 seconds
Added with reserve and push_back to Vector<int> in1.272 seconds
Removed all Vector<int> elements in 0.18 seconds
Added with reserve and [] to Vector<int> in 0.29 seconds
Removed all Vector<int> elements in 0 seconds
Added without SetSize to CArray<int, int> in 317.226 seconds
Removed all CArray elements in 0.02 seconds
Added with SetSize and Add to CArray<int, int> in 927.173 seconds
Removed all CArray elements in 0.04 seconds
Added with SetSize and SetAt to CArray<int, int> in 0.2 seconds
Removed all CArray elements in 0.02 seconds
|
|
|
|
|
I decided to go ahead and include the test code so anyone can tell me if it is alright or not.
void main()
{
int iLoop = 1000000;
cout << "Performing test with " << iLoop << " loops\r\n";
vector<int> TestVector;
// TestVector.reserve(iLoop);
clock_t Start = clock();
for(int i = 0; i < iLoop; i++){
TestVector.push_back(i * rand());
}
clock_t Finish = clock();
double Time = (double) (Finish - Start) / CLOCKS_PER_SEC;
cout << "Added without reserve to Vector<int> in " << Time << " seconds\r\n";
Start = clock();
TestVector.clear();
Finish = clock();
Time = (double) (Finish - Start) / CLOCKS_PER_SEC;
cout << "Removed all Vector<int> elements in " << Time << " seconds\r\n";
/////////////////////////////
TestVector.reserve(iLoop);
Start = clock();
for(i = 0; i < iLoop; i++){
TestVector.push_back(i * rand());
}
Finish = clock();
Time = (double) (Finish - Start) / CLOCKS_PER_SEC;
cout << "Added with reserve and push_back to Vector<int> in" << Time << " seconds\r\n";
Start = clock();
TestVector.clear();
Finish = clock();
Time = (double) (Finish - Start) / CLOCKS_PER_SEC;
cout << "Removed all Vector<int> elements in " << Time << " seconds\r\n";
/////////////////////////////
TestVector.reserve(iLoop);
Start = clock();
for(i = 0; i < iLoop; i++){
TestVector[i] = i * rand();
}
Finish = clock();
Time = (double) (Finish - Start) / CLOCKS_PER_SEC;
cout << "Added with reserve and [] to Vector<int> in " << Time << " seconds\r\n";
Start = clock();
TestVector.clear();
Finish = clock();
Time = (double) (Finish - Start) / CLOCKS_PER_SEC;
cout << "Removed all Vector<int> elements in " << Time << " seconds\r\n";
/////////////////////////////
CArray<int, int> TestCArray;
Start = clock();
for(int j = 0; j < iLoop; j++){
TestCArray.Add(j * rand());
}
Finish = clock();
Time = (double) (Finish - Start) / CLOCKS_PER_SEC;
cout << "Added without SetSize to CArray<int, int> in " << Time << " seconds\r\n";
Start = clock();
TestCArray.RemoveAll();
Finish = clock();
Time = (double) (Finish - Start) / CLOCKS_PER_SEC;
cout << "Removed all CArray elements in " << Time << " seconds\r\n";
/////////////////////////////
// TestCArray.SetSize(iLoop);
// Start = clock();
// for(j = 0; j < iLoop; j++){
// TestCArray.Add(j * rand()); //add's to the end after the .SetSize() elements are added
// }
// Finish = clock();
// Time = (double) (Finish - Start) / CLOCKS_PER_SEC;
// cout << "Added with SetSize and Add to CArray<int, int> in " << Time << " seconds\r\n";
// Start = clock();
// TestCArray.RemoveAll();
// Finish = clock();
// Time = (double) (Finish - Start) / CLOCKS_PER_SEC;
// cout << "Removed all CArray elements in " << Time << " seconds\r\n";
/////////////////////////////
TestCArray.SetSize(iLoop);
Start = clock();
for(j = 0; j < iLoop; j++){
TestCArray.SetAt(j, j * rand());
}
Finish = clock();
Time = (double) (Finish - Start) / CLOCKS_PER_SEC;
cout << "Added with SetSize and SetAt to CArray<int, int> in " << Time << " seconds\r\n";
Start = clock();
TestCArray.RemoveAll();
Finish = clock();
Time = (double) (Finish - Start) / CLOCKS_PER_SEC;
cout << "Removed all CArray elements in " << Time << " seconds\r\n";
}
|
|
|
|
|
Speed is not the only issue, or even the main one. Time how long it takes to write code for a vector that gets sorted, or shuffled, or partitioned around a point. Now time the same for CArray.
Christian
No offense, but I don't really want to encourage the creation of another VB developer.
- Larry Antram 22 Oct 2002
C# will attract all comers, where VB is for IT Journalists and managers - Michael
P Butler 05-12-2002
Again, you can screw up a C/C++ program just as easily as a VB program. OK, maybe not
as easily, but it's certainly doable. - Jamie Nordmeyer - 15-Nov-2002
|
|
|
|
|
Which are you insinuating being faster? Obviously, these types of sorting functions have been implemented already in the different algorythms (I am still reading the book) and to my knowledge nothing has been done about the MFC collections in this regard. So certainly, for this purpose vector would be coded quicker. But I am trying to compare their relative features (you can't serialize a vector without adding the extra code can you?). And to me, if you can predefine the size of the array and move relatively contiguously down its elements, it appears that it is actually faster using the CArray::SetAt() than vector. This is the purpose of my excersize, to see where the benefits are so I can choose my usage wisely.
Has anyone done tests of this nature and published the results and code?
Thank you
John
|
|
|
|
|
lpvoid wrote:
(you can't serialize a vector without adding the extra code can you?).
No, but the code is trivial, and in fact would use one of those algorithms, foreach.
lpvoid wrote:
This is the purpose of my excersize, to see where the benefits are so I can choose my usage wisely.
And my point is that the benefits of vector strip CArray pretty quickly because STL is extensible, compatible ( all containers expose the same sort of iterators ), flexible ( full of function objects which can be extended and modified ), etc.
lpvoid wrote:
Has anyone done tests of this nature and published the results and code?
As I said, I think you need to look at feature lists more than code.
Christian
No offense, but I don't really want to encourage the creation of another VB developer.
- Larry Antram 22 Oct 2002
C# will attract all comers, where VB is for IT Journalists and managers - Michael
P Butler 05-12-2002
Again, you can screw up a C/C++ program just as easily as a VB program. OK, maybe not
as easily, but it's certainly doable. - Jamie Nordmeyer - 15-Nov-2002
|
|
|
|
|
Watch out using STL algorithms. They often highly degrade performance. Handwritten loops are much more stable from a performance standpoint. In my tests, STL algorithms can degrade performance by 100-200% over hand written loops. I have rarely seen it perform better than handwritten loops. The problem is in the optimizer and not STL specifically.
Tim Smith
I'm going to patent thought. I have yet to see any prior art.
|
|
|
|
|
Christian,
I understand what you are saying and appreciate your responses. I will continue learning STL because quite frankly, it can't hurt to know it. I see there is a great deal of functionality in the library but at present, I don't have a use for hardly any of it. As for the extensibility of vector (and STL in general), CArray (and MFC in general) is extensible as well.
Thank you for your time and comments,
John
|
|
|
|
|
lpvoid wrote:
As for the extensibility of vector (and STL in general), CArray (and MFC in general) is extensible as well.
I was not thinking of deriving classes, you can do that most of the time in C++. I was thinking of being able to create a container, which can then interact with all the stl containers, creating a function object and being able to modify several functions with it, across several containers. MFC containers are not even compatibile with each other.
Christian
No offense, but I don't really want to encourage the creation of another VB developer.
- Larry Antram 22 Oct 2002
C# will attract all comers, where VB is for IT Journalists and managers - Michael
P Butler 05-12-2002
Again, you can screw up a C/C++ program just as easily as a VB program. OK, maybe not
as easily, but it's certainly doable. - Jamie Nordmeyer - 15-Nov-2002
|
|
|
|
|
Oh, I see what you mean now, and when I learn more about the STL I may even understand it 
Thanks,
John
|
|
|
|
|
But how often will you be creating a vector and filling it with 1000000 elements? .01 seconds here and there isn't going to kill anything. Also, the length of your tests are so short, that I question the reliability of the numbers. On my system, std::vector and ATL7 CAtlArray performed about the same.
Tim Smith
I'm going to patent thought. I have yet to see any prior art.
|
|
|
|
|
|
I think CArray with reserve was faster. Don't recall if he used reserve on vector at all though.
Christian
No offense, but I don't really want to encourage the creation of another VB developer.
- Larry Antram 22 Oct 2002
C# will attract all comers, where VB is for IT Journalists and managers - Michael
P Butler 05-12-2002
Again, you can screw up a C/C++ program just as easily as a VB program. OK, maybe not
as easily, but it's certainly doable. - Jamie Nordmeyer - 15-Nov-2002
|
|
|
|
|
yes.. i see a 0.29 to 0.20 s difference in a million operations. In most cases, I would neglect that performance increase for better managability of code.
Also, how many times are we actually able to use reserve for the largest sizes. Considering the SetSize/Add time being so dramatically off around a 1000 seconds, I guess we are just confirming that STL performs better on an average case, where we cannot exactly predict the number of items in a container, and in what order and time sequence insertions/deletes occur.
My article on a reference-counted smart pointer that supports polymorphic objects and raw pointers
modified 29-Aug-18 21:01pm.
|
|
|
|
|
Christian,
The tests I performed were indeed unlikely and too limited to be of an substantial value, I was looking to see, as my first set of tests, in fact, the very first code I ever wrote using vector and I was blown away. I started off with a thousand random numbers being stuffed into both vector and CArray, there was no difference, so went up to 10,000; small difference. So I said "Hell, a million iterations should have very visible results." A guy passing by my office gave me an odd look and I starting adding these mini tests. I will explain my results below.
Added without reserve to Vector<int> in 1.36 seconds
Removed all Vector<int> elements in 0.14 seconds
I added 1 million random numbers to a freshly declared vector<int>, it took 1.36 seconds and
.14 seconds to dump them all again
Added with reserve and push_back to Vector<int> in0.922 seconds
Removed all Vector<int> elements in 0.141 seconds
This time, I used vector.reserve() to reserve the memory first and the time was reduced.
(I used push_back to add the elements)
Added with reserve and [] to Vector<int> in 0.203 seconds
Removed all Vector<int> elements in 0 seconds
This time I reserved the memory and did direct access [] to each element to insert the integers
It was even quicker.
Added without SetSize to CArray<int, int> in 252.828 seconds
Removed all CArray elements in 0.031 seconds
Now I repeat the above but with CArray; the freshly declared array obviously bungles its way
around reallocating memory.
Added with SetSize and Add to CArray<int, int> in 768.796 seconds
Removed all CArray elements in 0.047 seconds
This test was screwed up because I forgot that SetSize() really sets the size of the array
and if you use CArray.Add(), you add still increase the size of the array, so it was insanely
longer.
Added with SetSize and SetAt to CArray<int, int> in 0.156 seconds
Removed all CArray elements in 0.031 seconds
But, using set SetSize and adding the elements with SetAt was the absolute fastest of them all.
My interpretation of the results are that if you are going to add elementes to a dynamically allocating array with an as yet undertermined size, use STL::vector. But, if you know what size the array must be and it will NEVER get bigger, CArray wins my vote. But, if the section of code is not GUI related, I don't think I am going to be using MFC anyway, I don't think less than 8/10ths of a second is going to be that crucial - I hope 
And just so you know, I am not here to prove or disprove anything to anyone but myself. I taught myself C++ in a hurry so I could fill an emergency roll as software developer 6 years ago. And I've been there ever since, even after a hostile takeover. Now I want to start learning the best way to do things. For me, comparing tests like this against what I already know is a great method of learning the tech and reinfocing its value.
Thank you for all your inpout and I hope you'll humor me further down the road.
John
|
|
|
|
|
lpvoid wrote:
But, if you know what size the array must be and it will NEVER get bigger, CArray wins my vote.
If I have a fixed size array and speed matters, I will just create an array and have no overhead. Unlike vector, CArray does nothin useful beyond being an array AFAIK.
Christian
No offense, but I don't really want to encourage the creation of another VB developer.
- Larry Antram 22 Oct 2002
C# will attract all comers, where VB is for IT Journalists and managers - Michael
P Butler 05-12-2002
Again, you can screw up a C/C++ program just as easily as a VB program. OK, maybe not
as easily, but it's certainly doable. - Jamie Nordmeyer - 15-Nov-2002
|
|
|
|
|
Well OK, you make a good point.
John
|
|
|
|
|
What you are seeing is a difference in allocation systems. STL uses a doubler while ATL/MFC uses an incremental growth. Personally, I like the doubler better but ATL7 containers a much more lightweight than STL.
Christian is right about the other stuff. If you find you are using all those other STL features, it would be silly to use ATL/MFC containers. The extra bloat in STL is specifically for all those nice features.
Tim Smith
I'm going to patent thought. I have yet to see any prior art.
|
|
|
|
|
Tim,
What you and Christian have said makes a lot of sense, I guess I just need more experience before I can really do proper testing and investigation as to which to use and when.
Thanks,
John
|
|
|
|
|
I recommend STL because it is extensible, i.e. it goes where C++ goes.
Kuphryn
|
|
|
|
|
Maybe I don't know what that means. I always thought 'extensible' meant you could extend its functionality, not its portability. At present, all of my development work is on Windows machines so the portability is not an issue to me (for the immediate that is). You can certainly extend MFC just as you can STL, so I don't see this as being a viable argument. Granted, I am not a highly paid engineer with degrees mounted on my walls, so please do not take offense to my statement that it doesn't make much sense to claim superior extensibility when this hardly seems the issue.
Thank you,
John
|
|
|
|
|
In any given software design, the developer should always design and implement it such that it is as portible as possible. Yes, you are set on Windows, but how about Win32 console when Microsoft releases something better than MFC? Note you will have to reimplement the software for MFC is not C++ standard tool.
For extending functionalities, STL definitely tops MFC. STL offers many more tools than MFC has to offer. For example, STL offers the std::pair key/value element type for all containers.
Kuphryn
|
|
|
|
|
Yes, you are correct, I should have developed my current project (and others in the past) more modular and less dependant on current technology and more reusable, which is one of the reasons I am investigating STL. As my current work is essentially a wash anyway, I am not concerned about it, but my next project, which replaces this one in the market, will follow these ideals to the best of my ability. The problem is that my work is almost 100% GUI and MFC is the best choice for that right now - unless you know of "better" alternatives.
Thank you for you advice,
John
|
|
|
|
|
MFC is an essential solution for Windows applications especially the GUI components. Other than the GUI component, I recommend other tools beside MFC. Top of the list is STL. Other tools depends on the project such as graphics, network, databases, etc.
Kuphryn
|
|
|
|
|
Once you get familiar with STL containers, I guess you would never use MFC containers again. Atleast, that was the case with me.
First of all, generic algorithms exist. As Tim pointed out, they may not give you the best performance possible - but, how many times do you need that performance - I would say a very negligible fraction.
For example, I had a loop that executed 10000 times a second, and had some container operations on it. Using a custom allocator, I was able to speed up the operations dramatically. This shows the flexibility that STL hands you in improving performance of pre-written code. To give another example, the hash_map in the STL that comes with VC7 is highly configurable - including the hash function, where as CMapStringToPtr does not allow me to customize the hash function.
Another thing that I would like to emphasize is the detachment of core logic from UI. I suggest that you never write algorithms and stuff in window classes, rather have a generic class hold the data and multiple inherit the target window from the MFC window class the the generic class that holds the data. This way, you can repalce your windowing with say wxWindows easily because your window classes do not have any core implementation.
Thomas
My article on a reference-counted smart pointer that supports polymorphic objects and raw pointers
modified 29-Aug-18 21:01pm.
|
|
|
|
|
A thing to consider.
vector does not change its item count, if you do not use push_back or insert. Hence adding items with [] operator in a random manner after reserve is practically unusable.
But, CArray has a bigger problem. Once you do SetSize(), GetCount() always returns the size set by SetSize(). CArray is therefore a very close implementation to a C array, where as vector has a max_size and a size, max_size is the value you set with reserve. size represents the actual number of items you inserted into the vector.
Just observations that I made. Anyway, you can do the folllowing too, to speed up vector in your sample.
vector<int > vint;
vint.reserve(1000000);
int* p = &vint[0];
for (int i = 0; i < 1000000; ++i)
{
*(p + i) = i;
}
Using rand is also not correct. I would recommend leaving it out, because rand does not seem to be a constant time operation.
My article on a reference-counted smart pointer that supports polymorphic objects and raw pointers
modified 29-Aug-18 21:01pm.
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
