|
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.
|
|
|
|
|
CArray also has a size and max_size system. The problem is how it is exposed. CArray lacks the reserve and thus lacks some of the power of vector.
That vector initialization code won't work since you aren't updating the actual size of vector. However, if you used resize, it would work, but resize forces element contruction the same as CArray's SetSize.
Tim Smith
I'm going to patent thought. I have yet to see any prior art.
|
|
|
|
|
My point was:
If i declare a CArray and SetSize(), GetCount() and GetSize() returns the same value - the value set by SetSize(). Internally, the memory allocation for a SetAt is done just to cover the number of items required.
However, a vector allows me to reserve a size. Even if I don't reserve the insert causes a larger memory allocation, thereby not requiring resize, if I do not reserve.
Hence, if I want upto 150 items in a container and want to know how many items are there at a particular time, I use reserve(150) to reserve the maximum space and size() to get the actual number of params. The value returned by size is updated only if you use insert or push_back, and not the [] operator.
In a CArray, if i want to know the number of items that I added, i cannot find it if I used SetSize(). Instead, I have to rely on the default memory management of CArray which is to create memory for only the number of items that it needs.
vector can be used the same way by using reserve, and creating a pointer p that points to the start of the vector (T* p = &v[0]) and using p[i] to access the elements. But, there may be a number of free locations in between (CArray behaves the same way), there by eliminating the possibility of using any of the other STL algorithms.
SetSize() is similar to resize() and there is nothing corresponding to reserve(). The default memory allocation done when inserting a new item is better in vector, because it allocates more space so that subsequent inserts are faster.
My article on a reference-counted smart pointer that supports polymorphic objects and raw pointers
modified 29-Aug-18 21:01pm.
|
|
|
|
|
Using vector the way you talk about won't work since the destination objects have not been constructed. This normally isn't a problem for things such as int. But for a complicated class where you override the copy operator, the copy operator would have expected the destination to have been constructed. Using reserve and then accessing the elements through a pointer won't work properly.
This program shows why it doesn't work.
#include <assert.h>
#include <vector>
class test
{
public:
test ()
{
m_nInit = 1234567;
}
const test &operator = (const test &src)
{
assert (m_nInit == 1234567);
m_nInit = src .m_nInit;
return *this;
}
int m_nInit;
};
int main(int argc, char* argv[])
{
std::vector <test> v;
v .reserve (100);
test *p = &v [0];
p [0] = test ();
return 0;
}
Also, the size of the vector is never set. Thus "size" will always return 0 so the vector thinks it is empty. Doing a push_back will destroy the first element of the vector you just tried to initialize.
As for the other stuff. That is basically what I said. CArray lacks a reserve.
Tim Smith
I'm going to patent thought. I have yet to see any prior art.
|
|
|
|
|