Quote:Original post by Hodgman

Quote:Original post by cache_hit
He's trying to create a hypothetical example where the vector is going to do a lot of copying due to having to re-arrange lots of stuff. This is a pathological example of poor performance given the right circumstances and a sufficiently expensive-to-copy object. Regardless, the problem is non-existant with r-value references so there's no point in even discussing it IMO.

It's also non-existent if you simply decide not to copy the objects while sorting them. Just sort indices or pointers instead of the actual heavyweight objects...
Design choice is obviously more important than library choice here.

If you do the equivalent operations without the STL (i.e. copying a vector == malloc/free) I don't see how there's going to be any performance difference. In his example, he's solving it in a stupid way with the STL and a smart way without it -- this doesn't prove the STL is slow, it just proves that one design is stupid.

Obvious fallacy is obvious.

Quote:Original post by thatguyfromthething
You sorted a vector with a million classes on a random key value in the class, each containing a vector with 12 items in it in a few milliseconds without taking some kind of shortcut? Not that I don't believe you, but, I don't believe you because I've recently benchmarked it pretty thoroughly in VC++ and all benchmarks I see point to other implementations being about the same or even worse.

The results I get is it takes about 135ms to sort 1 million ints in STL.
Which to me is a pretty good result, but how often do you have a static array of a million ints?

It takes about 450ms if you use a vector instead of an array. Which is kind of crappy, but not enough to slit your wrists, but since this is the real world case for any large data it does kind of suck. Especially when you have sorting as part of a much more complex algorithm. A case that comes up again and again and again.

If you move to the scenario I describe it will be executing til the day you die unless you replace std:swap and optimize the copy constructor (and doing that for hundreds of classes is not a fun prospect). Which to me is kind of ridiculous. The interface here is bad enough to suffer, but aside from benchmarks almost everything you want to sort is going to be something more complicated. Like a linear octree node, a vertex, that kind of thing.

Quote:Original post by thatguyfromthething
The results I get is it takes about 135ms to sort 1 million ints in STL.
Which to me is a pretty good result, but how often do you have a static array of a million ints?

It takes about 450ms if you use a vector instead of an array.

#include <boost/timer.hpp>#include <boost/random.hpp>#include <algorithm>#include <iostream>#include <vector>int a[1000000]; // to avoid a stack crashint main() {	boost::mt19937 rng;	boost::variate_generator<boost::mt19937&, boost::uniform_int<>  > intrng   (rng, boost::uniform_int<>(0,99999999) );	std::vector<int> v(1000000);	std::generate( v.begin(), v.end()  , intrng );	std::copy( v.begin(), v.end(), a+0 );	boost::timer asort;	std::sort( a+0      , a+1000000 );	double asort_time = asort.elapsed();	boost::timer vsort;	std::sort( v.begin(), v.end() );	double vsort_time = vsort.elapsed();	std::cout << "Time to sort A: " << asort_time << "\n";	std::cout << "Time to sort V: " << vsort_time << "\n";}

Time to sort A: 0.117Time to sort V: 0.114Press any key to continue . . .

#include <boost/timer.hpp>#include <boost/random.hpp>#include <algorithm>#include <iostream>#include <vector>int a[1000000]; // to avoid a stack crashint main() {	boost::mt19937 rng;	boost::variate_generator<boost::mt19937&, boost::uniform_int<>  > intrng   (rng, boost::uniform_int<>(0,9) );	std::vector<int> v(1000000);	std::generate( v.begin(), v.end()  , intrng );	std::copy( v.begin(), v.end(), a+0 );	boost::timer asort;	std::sort( a+0      , a+1000000 );	double asort_time = asort.elapsed();	boost::timer vsort;	std::sort( v.begin(), v.end() );	double vsort_time = vsort.elapsed();	std::cout << "Time to sort A: " << asort_time << "\n";	std::cout << "Time to sort V: " << vsort_time << "\n";}

Time to sort A: 0.017Time to sort V: 0.017Press any key to continue . . .

Quote:Original post by Zahlman

Quote:Original post by thatguyfromthething
You sorted a vector with a million classes on a random key value in the class, each containing a vector with 12 items in it in a few milliseconds without taking some kind of shortcut? Not that I don't believe you, but, I don't believe you because I've recently benchmarked it pretty thoroughly in VC++ and all benchmarks I see point to other implementations being about the same or even worse.

The results I get is it takes about 135ms to sort 1 million ints in STL.
Which to me is a pretty good result, but how often do you have a static array of a million ints?

It takes about 450ms if you use a vector instead of an array. Which is kind of crappy, but not enough to slit your wrists, but since this is the real world case for any large data it does kind of suck. Especially when you have sorting as part of a much more complex algorithm. A case that comes up again and again and again.

If you move to the scenario I describe it will be executing til the day you die unless you replace std:swap and optimize the copy constructor (and doing that for hundreds of classes is not a fun prospect). Which to me is kind of ridiculous. The interface here is bad enough to suffer, but aside from benchmarks almost everything you want to sort is going to be something more complicated. Like a linear octree node, a vertex, that kind of thing.

Stop posturing and offering vague descriptions, and post your benchmark code.

At the risk of overstepping ApochPiQ's authority: I'm saying that in my Moderator Voice(TM). Put your money where your mouth is, or get out of the thread.

Other people posted actual code and results that disagree with your assertions. So far you have only words.

I do not like disinformation and rumour-mongering.

#include "stdafx.h"#include <Windows.h>#include <vector>#include <algorithm>#include <numeric>#include <iostream>#include <time.h>using namespace std;LARGE_INTEGER freq;struct unmoveable_foo{public:	unmoveable_foo()	{		for (int i=0; i < 10; ++i)			vec_.push_back(rand());	}	vector<int> vec_;	int sum() const { return std::accumulate(vec_.begin(), vec_.end(), 0); }	bool operator<(const unmoveable_foo& other) const	{		return sum() < other.sum();	}};struct moveable_foo{	moveable_foo()	{		for (int i=0; i < 10; ++i)			vec_.push_back(rand());	}	moveable_foo(moveable_foo&& other)		: vec_(std::move(other.vec_))	{ }	moveable_foo& operator=(moveable_foo&& other)	{		vec_ = std::move(other.vec_);		return *this;	}	vector<int> vec_;		int sum() const { return std::accumulate(vec_.begin(), vec_.end(), 0); }	bool operator<(const moveable_foo& other) const	{		return sum() < other.sum();	}};struct rand_int{	rand_int() : i(rand()) {}	int i;	bool operator<(const rand_int& other) const	{		return i < other.i;	}};template<class T>void test_sort(){	cout << "Testing sort of " << typeid(T).name() << endl;	LARGE_INTEGER start;	LARGE_INTEGER stop;	std::cout << "Initializing vector..." << std::endl;	vector<T> vec(1000000);	std::cout << "Initializing array..." << std::endl;	T* array = new T[1000000];	std::cout << "Sorting..." << std::endl;	::QueryPerformanceCounter(&start);	sort(vec.begin(), vec.end());	::QueryPerformanceCounter(&stop);	cout << "vector: " << (float)(stop.QuadPart - start.QuadPart) / (float)freq.QuadPart << " seconds" << endl;	::QueryPerformanceCounter(&start);	sort(array, array+1000000);	::QueryPerformanceCounter(&stop);	cout << "array: " << (float)(stop.QuadPart - start.QuadPart) / (float)freq.QuadPart << " seconds" << endl;}int _tmain(int argc, _TCHAR* argv[]){	::QueryPerformanceFrequency(&freq);	srand(time(0));	test_sort<rand_int>();	test_sort<moveable_foo>();	test_sort<unmoveable_foo>();	std::cin.get();	return 0;}

Quote:Original post by thatguyfromthething
I don't believe you because I've recently benchmarked it pretty thoroughly in VC++