CArray vs. std::vector

[ovidiucucu]

A lightning fast application in 100% standard C++ is much better.

Indeed, somethng like

#include <iostream>
int main()
{
   std::cout << "Hello world!" << std::endl;
   return 0;
}

...is much better than the equivalent "non-standard" MFC implementation.
However, if you want to do more, like showing something user friendly, print something, let user push something and so on, the "100% standard C++" doesn't help you so much.

They wouldn't get away with a crappy implementation. And if Microsoft implemented it themselves I don't think they would have anything to gain from making their C++ standard libraries inferior on purpose to promote the MFC?

Yeah, I know... The Microsoft's Mondial Conspiracy... Kelly, the Al Bundy's blonde daughter, has told me about it...

I've heard claims like this over and over again in forums and each time when the benchmarks are finally posted the only thing they prove conclusively is that the poster doesn't know what he's doing.

"Life on Venus is much more comfortable than life on Mercury"
Is that true? I think, you can just presume but don't exactly know until make a try.

[superbonzo]

I knew that.
Ok, seems to be logical and good to add "no additional run-time checking, means more speed" in Programmer's Holy Book.
However, until seeing somethig is really real, I'm Thomas The Unbeliever Programmer so I said: "Let's try it!".
I was expecting a significant speed increasing by disabling run-time iterators checking (setting _SECURE_SCL=0), but... surprise: the result was quite the same.
Or course, would be stupid to generalize and take that as a generally true statement.
In other non-trivial cases, the result may be as "canonically" expected.
Maybe I was wrong, then you can try it. That program is not tabu and doesn't bite. .

actually, your code gives an unfair comparison; in the line

qsort(arr.GetData(), size, sizeof(CString*), CompareStrings);

you are treating a CString as a POD of the same size and content of a TCHAR*, so basically, you are sorting an array of char pointers; whereas in the line

std::sort( v.begin(), v.end() );

you are sorting a vector of CString objects, which is obviously slower; the two happens to give the same results only because you are using a Microsoft compiler.

Now, in order to make a fair comparison, you should pass the CString's to std::sort as a sequence of pod objects, as in the following adaptation of your code sample:

#include "stdafx.h"
#include "array.h" 

#include <boost/iterator/transform_iterator.hpp>

namespace details
{
	template< class T, class PodT >
	struct AsPod: std::unary_function<T&,PodT&>
	{
		BOOST_STATIC_ASSERT( sizeof(T) == sizeof(PodT) );

		PodT& operator()( T& v ) const {
			return *(PodT*)(&v);
		}
	};
}

template< class PodT, class Iter >
boost::transform_iterator< details::AsPod<typename Iter::value_type, PodT>, Iter >
	make_pod_iterator( Iter it )
{
	return boost::make_transform_iterator( it, details::AsPod<typename Iter::value_type, PodT>() );
}

struct CompareStrings
{
	bool operator()( TCHAR* left, TCHAR* right)
	{
		return ((CString&)left).Compare((CString&)right) < 0;
	}
};

int _tmain(int argc, _TCHAR* argv[])
{
	ShowWindow(::GetConsoleWindow(), SW_HIDE);
	const size_t size = GetArraySize();
	LARGE_INTEGER begin, end, freq;
	::QueryPerformanceFrequency(&freq);

	::QueryPerformanceCounter(&begin);

	std::vector<CString> v;
	v.resize(size);
	
	for(size_t index = 0; index < size; index++)
	{
		v[index] = g_strings[index];
	}

	::QueryPerformanceCounter(&end);
	double fill = ((double)end.QuadPart - begin.QuadPart) * 1000.0 / freq.QuadPart; 

	::QueryPerformanceCounter(&begin);

	std::sort( make_pod_iterator<TCHAR*>( v.begin() ), make_pod_iterator<TCHAR*>( v.end() ), CompareStrings() );

	::QueryPerformanceCounter(&end);
	double sort = ((double)end.QuadPart - begin.QuadPart) * 1000.0 / freq.QuadPart;

	CString strResult;
	strResult.Format(_T("Array size: &#37;u")
					 _T("\nFill time: %lf ms.")
					 _T("\nSort time: %lf ms.\n"),
					 size, fill, sort);
	::MessageBox(NULL, strResult, _T("STL WAY"), MB_OK);
	
	return 0;
}

the line

std::sort( make_pod_iterator<TCHAR*>( v.begin() ), make_pod_iterator<TCHAR*>( v.end() ), CompareStrings() );

gives the true semantically equivalent version of the line

qsort(arr.GetData(), size, sizeof(CString*), CompareStrings);

and my results for sorting ( with _SECURE_SCL = 0, array size = 59956 ( I doubled the original array to make it to take longer ) ) are

MFC: ~35 ms
STL: ~18 ms

( PS: I quickly tested the code above, hope there's no error )

moreover, note that not only the STL version seems faster, my pod_iterator also supports checked vector iterators in debug builds ...

EDIT: I just want to precise that both the qsort and pod_iterator versions are acceptable because we suppose that CString can be treated as a POD in VC++. BTW, note that the STL version makes also much more clear that we are doing something out-of-standard ...

EDIT 2: of course, if you don't like all the make_pod_iterator template stuff and you don't care of having a consistent iterator interface, you can simply write

std::sort( (TCHAR**)&v[0], (TCHAR**)&v[ v.size() - 1 ], CompareStrings() );

instead of "std::sort( make_pod_iterator ..."; but IMHO, this is less clear and dangerous; moreover the speed seems the same ...

[ovidiucucu]

std::sort( (TCHAR**)&v[0], (TCHAR**)&v[ v.size() - 1 ], CompareStrings() );

I have to recognize, this one is really speedy.

[superbonzo]

I have to recognize, this one is really speedy.

actually, I wrote the TCHAR** version quickly and there is an error: it ignores the last CString; you should change "(TCHAR**)&v[ v.size() - 1 ]" to "((TCHAR**)&v[0]) + v.size()" to get the correct code. Anyway, as I said above, I like more the make_pod_iterator version which has the same speed of the TCHAR** code and offer more safety for free ( ... and it's more C++-esque ! ).

[jwbarton]

Using std::string instead of CString with the VS2010 compiler can produce faster results without needing to rely on tricks (treating the CString as a POD).

The std::string object in VS2010 supports the move constructors, while the CString object doesn't (at least as far as I can tell).

This results in sort() being able to perform better on a vector<std::string> than on a vector<CString>, assuming no POD tricks.

My system (using modified versions of the previously posted code) produced the following results:

qsort on vector<CString>: 41.18 ms
sort on vector<CString> with function comparator: 138.9 ms
sort on vector<CString> with functor comparator: 129.2 ms
sort on vector<std::string> with function comparator: 43.6 ms
sort on vector<std::string> with functor comparator: 35.5 ms

For the qsort, I simply duplicated the original test. I don't really consider this test valid as it does treat the CString as a POD, but I wanted to include it as a comparison.

For the other tests, std::sort is used with either a function comparator or a functor comparator. There are no POD tricks being done - the comparator simply compares the 2 strings. Since std::string supports move constructors in VS2010, this results in better performance than the vector with CString.