Qsort easily beats std::sort() 100+ times!

[AnthonyMai]

I keep hearing from folks saying that it is unsafe to call Qsort() or qsort() because it has no idea about the constructors or assignment operators of none-POD data types.

One has to realize that in sorting object, you don't need to create new ones, you don't need to destroy old ones. All you need to do is moving objects around in memory. Is there any operation safer to do, than merely moving an object from one memory location to another? Qsort does NOT need to know the constructors etc., because it doesn't need to create or destroy objects.

That's exactly where Qsort beats std::sort() by big time. By "big" I mean more than 100 times faster.

Just try it with sorting an array of 100000 objects of a very simple class where the data member is simply one pointer pointing to 4KB memory allocated upon object creation, and deleted upon object destruction, and memcpy()'ed when object is copied. Try to see how std::sort handles it and how qsort() does it, you will see a big difference.

Especially when memory usage is near full, std::sort() will be literally brought down to craw on the ground, desperately trying to create new objects, allocate memory, memcpy() memory, then destroy object, all in an effort that is un-necessary and wasted.

While as qsort() is flying, sorting objects by just swapping the 4 bytes pointer that represent the class object.

No wonder Qsort() can easily defeat std::sort() by 100+ times or even more in such case.

[AnthonyMai]

#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <string>

#define ELEMENT_COUNT 100000

#define BUFF_SIZE 4096

#define CUTOFF 8 /* testing shows that this is good value */

using namespace std;

class SomeClass
{
public:
SomeClass();
~SomeClass();

SomeClass(const SomeClass& src);
SomeClass& operator=(const SomeClass& src);

std::string fld1;
char* m_pBuff;
};


SomeClass::SomeClass()
{
m_pBuff = new char[BUFF_SIZE];
}

SomeClass::~SomeClass()
{
delete [] m_pBuff;
}


SomeClass::SomeClass(const SomeClass& src) :
fld1(src.fld1)
{
m_pBuff = new char[BUFF_SIZE];
memcpy(m_pBuff, src.m_pBuff, BUFF_SIZE);
}

SomeClass& SomeClass::operator=(const SomeClass& src)
{
fld1 = src.fld1;

memcpy(m_pBuff, src.m_pBuff, BUFF_SIZE);

return *this;
}


struct SortFld
{
inline bool operator() (const SomeClass& first, const SomeClass& second)
{
return strcmp(first.fld1.c_str(), second.fld1.c_str())<0?true:false;
}
};


typedef vector<SomeClass> intvec;

void randomise_vector(intvec& v)
{
srand(time(0));
char szBuf[15];
for (intvec::iterator i = v.begin(); i != v.end(); ++i)
{
sprintf(szBuf, "%d", 100 + (((unsigned int)rand())%999));
(*i).fld1 = szBuf;
strcpy((*i).m_pBuff, szBuf);
}
}

inline bool stllessfunc(const SomeClass& lhs, const SomeClass& rhs)
{
return strcmp(lhs.fld1.c_str(), rhs.fld1.c_str())<0?true:false;
}

inline int qscompare(const void* lhs, const void* rhs)
{
return strcmp(((SomeClass *)lhs)->fld1.c_str(), ((SomeClass *)rhs)->fld1.c_str());
}


void __cdecl Qsort (
void *base,
unsigned num,
unsigned width,
int (__cdecl *comp)(const void *, const void *)
);

int main()
{
srand(clock());
intvec v(ELEMENT_COUNT);

randomise_vector(v);

cout << "std::sort using functor: ";
clock_t start = clock();
sort(v.begin(), v.end(), SortFld());
clock_t stop = clock();
cout << stop - start << " ticks" << endl;

randomise_vector(v);

cout << "std::sort using function: ";
start = clock();
sort(v.begin(), v.end(), stllessfunc);
stop = clock();
cout << stop - start << " ticks" << endl;

randomise_vector(v);
cout << "Qsort: ";
start = clock();
//qsort(static_cast<void*>(&v[0]), ELEMENT_COUNT, sizeof(SomeClass), qscompare);
Qsort(static_cast<void*>(&v[0]), ELEMENT_COUNT, sizeof(SomeClass), qscompare);
stop = clock();
cout << stop - start << " ticks" << endl;

char c;
cin >> c;
return 0;
}


void __cdecl Qsort (
void *base,
unsigned num,
unsigned width,
int (__cdecl *comp)(const void *, const void *)
)
{
char *lo, *hi;
char *mid;
char *loguy, *higuy;
unsigned size;
char *lostk[30], *histk[30];
int stkptr;

/* Note: the number of stack entries required is no more than
1 + log2(size), so 30 is sufficient for any array */

if (num < 2 || width == 0)
{
return;
}

stkptr = 0;

lo = (char*)base;
hi = (char *)base + width * (num-1);

recurse:

size = (hi - lo) / width + 1;

if (size <= CUTOFF)
{
char *p, *max;

while (hi > lo)
{
max = lo;
for (p = lo+width; p <= hi; p += width)
{
if (comp(p, max) > 0)
{
max = p;
}
}

if ( max != hi )
{
register int w2 = width;

if (w2 < 4)
{
do {
char tmp = max[w2];
max[w2] = hi[w2];
hi[w2] = tmp;
} while ((w2--) & 3);
}
else
{
while (w2 >= 4)
{
w2 -= 4;
int tmp = *(int*)(&max[w2]);
*(int*)(&max[w2]) = *(int*)(&hi[w2]);
*(int*)(&hi[w2]) = tmp;
}
}
}

hi -= width;
}

}
else
{
mid = lo + (size / 2) * width;

if ( mid != lo )
{
register int w2 = width;

while ((w2--) & 3)
{
char tmp = mid[w2];
mid[w2] = lo[w2];
lo[w2] = tmp;
}
while (w2 >= 4)
{
w2 -= 4;
int tmp = *(int*)(&mid[w2]);
*(int*)(&mid[w2]) = *(int*)(&lo[w2]);
*(int*)(&lo[w2]) = tmp;
}
}

loguy = lo;
higuy = hi + width;

for (;;)
{
do {
loguy += width;
} while (loguy <= hi && comp(loguy, lo) < 0);

do {
higuy -= width;
} while (higuy > lo && comp(higuy, lo) > 0);

if (higuy < loguy)
{
break;
}

if ( loguy != higuy )
{
register int w2 = width;

while ((w2--) & 3)
{
char tmp = loguy[w2];
loguy[w2] = higuy[w2];
higuy[w2] = tmp;
}
while (w2 >= 4)
{
w2 -= 4;
int tmp = *(int*)(&loguy[w2]);
*(int*)(&loguy[w2]) = *(int*)(&higuy[w2]);
*(int*)(&higuy[w2]) = tmp;
}
}
}

if ( lo != higuy )
{
register int w2 = width;

while ((w2--) & 3)
{
char tmp = lo[w2];
lo[w2] = higuy[w2];
higuy[w2] = tmp;
}
while (w2 >= 4)
{
w2 -= 4;
int tmp = *(int*)(&lo[w2]);
*(int*)(&lo[w2]) = *(int*)(&higuy[w2]);
*(int*)(&higuy[w2]) = tmp;
}
}

if ( higuy - 1 - lo >= hi - loguy )
{
if (lo + width < higuy)
{
lostk[stkptr] = lo;
histk[stkptr] = higuy - width;
++stkptr;
}

if (loguy < hi)
{
lo = loguy;
goto recurse;
}
}
else
{
if (loguy < hi)
{
lostk[stkptr] = loguy;
histk[stkptr] = hi;
++stkptr;
}

if (lo + width < higuy)
{
hi = higuy - width;
goto recurse;
}
}
}

--stkptr;
if (stkptr >= 0)
{
lo = lostk[stkptr];
hi = histk[stkptr];
goto recurse;
}

return;
}

[AnthonyMai]

Well I just finished the testing. Here is the result:

number of objects: 100000
BUFF_SIZE: 4096 (bytes)

std::sort using functor: 1989240 ticks
std::sort using function: 222950 ticks
Qsort: 2035 ticks

See the big difference?

I am running the test on a PII 500MHz machine, 256 MB memory. With 4 IE windows and VisualStudio running. No other applications running.

[amag]

You might want to rethink your class design in this case. Of course qsort() is faster since your semantics for using std::sort and qsort() are different. For qsort you just copy the ptr not the data inside whereas your assignment operator for SomeClass copies the actual data (in addition to allocating space for it), that is very time consuming. I recommend that you use std::auto_ptr or boost::shared_ptr instead of copying the data.

Your qsort must really suck if it's just 100 times faster than std::sort in that case.

[AnthonyMai]

Sorting just 10000 elements:

std::sort using functor: 6870ticks
std::sort using function: 6640 ticks
Qsort: 50 ticks

See the difference?

[Gabriel Fleseriu]

I have read both this and the other thread (" The fear of the misterious "). I'm not quite sure I understand what is what you want to prove -- i.e. what exactly is your statement ?

[amag]

Anyway I rewrote your code so the semantics would be a bit closer to each other and on my machine it's more than 4:1 rather than 100+:1

std::sort using functor: 531 ticks
std::sort using function: 530 ticks
Qsort: 120 ticks

I haven't even tried to optimise any code and thinking of it this may be a fair price to pay to have nice-behaving code rather than code that may or may not work, depending on compiler vendor/version etc..

[PaulWendt]

Does anyone else get an access violation with this code? I think I copied it incorrectly [this webpage puts a lot of weird symbols inside embedded code if you use ; : ) and other characters too close together]. With the code I have, Qsort produces an access violation, whereas qsort does not.

[Paul McKenzie]

Originally posted by amag
Anyway I rewrote your code so the semantics would be a bit closer to each other and on my machine it's more than 4:1 rather than 100+:1

std::sort using functor: 531 ticks
std::sort using function: 530 ticks
Qsort: 120 ticks

I haven't even tried to optimise any code and thinking of it this may be a fair price to pay to have nice-behaving code rather than code that may or may not work, depending on compiler vendor/version etc.. amag, can you post your version? I'd like to take a look at it.

Regards,

Paul McKenzie

[Philip Nicoletti]

1) I ran your code on pgCC, for the Qsort() case I got the folowing
error message : "Segmentation fault (core dumped)"

2) I changed your main as given below. I took out the std::sort()
section, and put {} around the Qsort() section ...

On Visual C++ version 5, I got the following error window :

The instruction at "0x77164d8a" referenced memory at "0x002147dd". The
memory could not be "read".

Maybe version 6 will not have this problem ? Also, if I set BUFF_SIZE
smaller, I do not get the error.



int main()
{
srand(clock());

clock_t start,stop;

{
intvec v(ELEMENT_COUNT);
randomise_vector(v);
cout << "Qsort: ";
start = clock();
//qsort(static_cast<void*>(&v[0]), ELEMENT_COUNT, sizeof(SomeClass), qscompare);
Qsort(static_cast<void*>(&v[0]), ELEMENT_COUNT, sizeof(SomeClass), qscompare);
stop = clock();
cout << stop - start << " ticks" << endl;
}

return 0;
}

[PaulWendt]

Philip said:
>>>>>>>>
On Visual C++ version 5, I got the following error window :

The instruction at "0x77164d8a" referenced memory at "0x002147dd". The
memory could not be "read".

Maybe version 6 will not have this problem ? Also, if I set BUFF_SIZE
smaller, I do not get the error
<<<<<<<<

I have VC 6.0 SP5 and I get that window popping up as well. I noticed that he has cin >> c prompting for input at the end; that delays the program. I thought he was doing that for unix platforms, but then I realized that with the __cdecl he's probably not moving it to other platforms anyway. The problem only occurs during the delete statement; he's clearly screwing up memory somewhere in his Qsort(). qsort(), on the other hand, isn't screwing anything up [at least that I've seen so far] ... and it is producing some good results. Unfortunately, I'm not willing to depend on it; I'd rather use std::sort and another method of sorting as another poster suggested [like keeping a list who internally sorts its members as they're inserted].

In case anyone else cares, the Qsort() function core dumps on hp-ux using the gcc-3.1 compiler [whereas qsort() works fine].

--Paul

[Philip Nicoletti]

Also, I ran the following on a somewhat high-end computer.
(I don't know the exact specs, but it is about a year old
and was pretty much top of the line at that time and had lots
of memory (maybe a gigabyte)) :

1) std::sort() using indirect sorting : 233 ticks
2) std::sort() using direct sorting : 13625 ticks
2) Qsort using direct sorting : 265 ticks (but get the error
message from the previous post).

On a much slower computer, Qsort() did outperform even the
indirect std:sort by about 3 to 1, but again, I got the
error window.

[Paul McKenzie]

On VC 6.0, the fault occurs in the destructor of SomeClass right before the termination of the program.

Regards,

Paul McKenzie

[AnthonyMai]

Funny. Paul claimed my code doesn't work on VC++ 6.0. I tested it (both release and debug) on VC++ 6.0 and it works just fine. And now I copy and paste my own posted code and tested it on a different machine, and it still works fine.

So far I tested it on both VC++6.0 enterprise edition and standard edition. Both works just fine.

Maybe Paul has a defective copy of VC++ 6.0?

The rest of reader groups can test for themselves on VC++ 6.0.

My test on a PIII 1700 MHz machine with 512 MB memory, using VC++ 6.0 standard edition:

std::sort using functor: 8656 ticks
std::sort using function: 8719 ticks
Qsort: 282 ticks

Try to increase the element count until your machine is using nearly all the memory and see what happens?

std::sort() would be crawing and Qsort() will still fly. Because the later doesn't need to allocate any memory.

[jfaust]

Actually, I got the same result with VC++ 6.0. I thought maybe something it was only happening in a debug build and that's why you didn't see it, but I checked, and it's happening in both.

[PaulWendt]

AnthonyMai: you probably missed that two other people are reporting the same problem, not just PaulMckenzie. Your Qsort() routine is messing something up because I don't notice the same behavior with qsort(). The problem occurs, as PaulMcKenzie reported, in your SomeObject destructor at the delete statement. Obviously, just deleting a pointer won't cause an access violation; my guess is that your routine garbled something up.

When Visual Studio is done, I usually hit Control+C ... so I didn't notice this at first; you won't notice it either because you have the following at the bottom of your main() :

char c;
cin >> c;


This is causing the program to wait for user-input; then, if you hit Control+c, the window disappears and the program terminates ... all without calling SomeObject's destructor. So, take out the cin statement; you ought to see an access violation.

I have Visual Studio 6.0 with Service Pack 5; I've tested the code on HP-UX 10.20 with gcc-3.1. Philip Nicoletti experienced this problem with Visual Studio 5.0. Paul McKenzie experienced this problem with Visual Studio 6.0. It's not an isolated incident, here.

--Paul [Wendt]

[Paul McKenzie]

Wow, I wish I could tell my customers that "their copy of VC 6.0 is broken, 'cause I don't get it here" when they get a GPF. Yep, that will go over very well.

Do you really play me for a fool? You have a defective program. There is nothing wrong with my copy of VC++ 6.0, SP 5. You played with fire, and you got burned.

And note, I was not the only one that reported the problem. Other persons reported the same thing, on different compilers no yet.

It can't be your program, right? This is getting too ridiculous.

Regards,

Paul McKenzie

[AnthonyMai]

Looks like I was copying the original Qsort from some where which contains a bug. But even that doesn't explain why it doesn't work on Paul's machine. Because I compiled the same thing and it works, for both debug and release.

Another test result:

std::sort using functor: 8938 ticks
std::sort using function: 8906 ticks
Qsort: 297 ticks


Here is the correct Qsort() function:


// This is Anthony's improved version of qsort -A.Mai 7/18/2002
void __cdecl Qsort (
void *base,
unsigned num,
unsigned width,
int (__cdecl *comp)(const void *, const void *)
)
{
char *lo, *hi;
char *mid;
char *loguy, *higuy;
unsigned size;
char *lostk[30], *histk[30];
int stkptr;

if (num < 2 || width == 0)
{
return;
}

stkptr = 0;

lo = (char*)base;
hi = (char *)base + width * (num-1);

recurse:

size = (hi - lo) / width + 1;

if (size > CUTOFF)
{
mid = lo + (size / 2) * width;

{
register int w2 = width;

if (w2 < 4)
{
do
{
char tmp;

w2 --;
tmp = mid[w2];
mid[w2] = lo[w2];
lo[w2] = tmp;
} while (w2 > 0);
}
else
{
int tmp;

tmp = *(int*)(&mid[w2-4]);
*(int*)(&mid[w2-4]) = *(int*)(&lo[w2-4]);
*(int*)(&lo[w2-4]) = tmp;
w2--;
w2 &= -4;
while (w2 >= 4)
{
w2 -= 4;
tmp = *(int*)(&mid[w2]);
*(int*)(&mid[w2]) = *(int*)(&lo[w2]);
*(int*)(&lo[w2]) = tmp;
}
}
}

loguy = lo;
higuy = hi + width;

for (;;)
{
do {
loguy += width;
} while (loguy <= hi && comp(loguy, lo) < 0); // <=

do {
higuy -= width;
} while (higuy > lo && comp(higuy, lo) > 0); // >=

if (higuy < loguy)
{
break;
}

{
register int w2 = width;

if (w2 < 4)
{
do
{
char tmp;

w2 --;
tmp = loguy[w2];
loguy[w2] = higuy[w2];
higuy[w2] = tmp;
} while (w2 > 0);
}
else
{
int tmp;

tmp = *(int*)(&loguy[w2-4]);
*(int*)(&loguy[w2-4]) = *(int*)(&higuy[w2-4]);
*(int*)(&higuy[w2-4]) = tmp;
w2--;
w2 &= -4;
while (w2 >= 4)
{
w2 -= 4;
tmp = *(int*)(&loguy[w2]);
*(int*)(&loguy[w2]) = *(int*)(&higuy[w2]);
*(int*)(&higuy[w2]) = tmp;
}
}
}
}

{
register int w2 = width;

if (w2 < 4)
{
do
{
char tmp;
w2 --;
tmp = lo[w2];
lo[w2] = higuy[w2];
higuy[w2] = tmp;
} while (w2 > 0);
}
else
{
int tmp;

tmp = *(int*)(&lo[w2-4]);
*(int*)(&lo[w2-4]) = *(int*)(&higuy[w2-4]);
*(int*)(&higuy[w2-4]) = tmp;
w2--;
w2 &= -4;
while (w2 >= 4)
{
w2 -= 4;
int tmp = *(int*)(&lo[w2]);
*(int*)(&lo[w2]) = *(int*)(&higuy[w2]);
*(int*)(&higuy[w2]) = tmp;
}
}
}

if ( higuy - 1 - lo >= hi - loguy )
{
if (lo + width < higuy)
{
lostk[stkptr] = lo;
histk[stkptr] = higuy - width;
++stkptr;
}

if (loguy < hi)
{
lo = loguy;
goto recurse;
}
}
else
{
if (loguy < hi)
{
lostk[stkptr] = loguy;
histk[stkptr] = hi;
++stkptr;
}

if (lo + width < higuy)
{
hi = higuy - width;
goto recurse;
}
}
}
else
{
char *p, *max;

while (hi > lo)
{
max = lo;
for (p = lo+width; p <= hi; p += width)
{
if (comp(p, max) > 0)
{
max = p;
}
}

if ( max != hi )
{
register int w2 = width;

if (w2 < 4)
{
do {
char tmp;

w2 --;
tmp = max[w2];
max[w2] = hi[w2];
hi[w2] = tmp;
} while (w2 > 0);
}
else
{
int tmp;

tmp = *(int*)(&max[w2-4]);
*(int*)(&max[w2-4]) = *(int*)(&hi[w2-4]);
*(int*)(&hi[w2-4]) = tmp;
w2--;
w2 &= -4;
while (w2 >= 4)
{
w2 -= 4;
tmp = *(int*)(&max[w2]);
*(int*)(&max[w2]) = *(int*)(&hi[w2]);
*(int*)(&hi[w2]) = tmp;
}
}
}

hi -= width;
}
}


--stkptr;
if (stkptr >= 0)
{
lo = lostk[stkptr];
hi = histk[stkptr];
goto recurse;
}

return;
}

[Paul McKenzie]

Take the smiley's out of your post by clicking "Disable Smilies in This Post".

I tried your code on the modified pointer version from the other thread, and it now sorts correctly, but is slower than std::sort.

Regards,

Paul McKenzie

[AnthonyMai]

PaulWendt
Thanks for pointing out. Yes the cin>>c is what prevented me from seeing the crash. After removing that line, I was able to re-produce the problem. And it was the fault of an older version of Qsort() being used, as I pointed in my last message.
I accept that as my fault.

I changed to my new version of Qsort(), which I just posted, and it works fine, both release and debug version.

Please try the new Qsort() and see how it works.

[AnthonyMai]

Paul:

Look, you know that's not true. Qsort() is at least 30 times or even more faster than std::sort(), depends on the memory status of the machine. My orignal Qsort has a bug. I accept that, I corrected it. The new result still shows Qsort 1 or 2 orders of magnitude faster in sorting the SomeClass I posted.

Practically there is just no way std::sort() can win over Qsort() in this case. Qsort doesn't have to construct or copy any object, but std::sort() has to. So I don't know where and how you get your data.

The rest of user group can testify.

[amag]

HELLO??!?! Anthony??? Are you even reading peoples posts?

You are comparing apples and bananas. There's nothing that says you need to reallocate and copy the buffer in the assignment operator of SomeClass. Use std::auto_ptr or even better boost::shared_ptr to just copy the pointer.

Paul: I only changed the pointer to std::auto_ptr and removed the allocation from the ctor of SomeClass. I don't have the code here, but I can post it tomorrow if you still want to look at it.

[Paul McKenzie]

Oooh..

A vector of auto_ptrs is supposed to be dangerous, correct? That's why boost came up with their version. I would switch to the boost version and retest.

Regards,

Paul McKenzie

[Paul McKenzie]

Originally posted by AnthonyMai
Paul:

Look, you know that's not true. Qsort() is at least 30 times or even more faster than std::sort(), depends on the memory status of the machine. My orignal Qsort has a bug. I accept that, I corrected it. The new result still shows Qsort 1 or 2 orders of magnitude faster in sorting the SomeClass I posted.

Practically there is just no way std::sort() can win over Qsort() in this case. Qsort doesn't have to construct or copy any object, but std::sort() has to. So I don't know where and how you get your data.

The rest of user group can testify. When you change to sorting a container of pointers, the difference is minimal, with std::sort using the functor being faster than using the std::sort using a function or QSort().

Regards,

Paul McKenzie

[amag]

Actually I didn't have a vector of auto_ptr:s I changed the SomeClass to this:

class SomeClass
{
public:
SomeClass();
~SomeClass();
void Allocate();

SomeClass(const SomeClass& src);
SomeClass& operator=(const SomeClass& src);

std::string fld1;
std::auto_ptr<char> m_pBuff;
};

I did the allocation of memory in Allocate() so I would only need to allocate the memory once. The vector I left alone.

[Gabriel Fleseriu]

Originally posted by Paul McKenzie
Oooh..

A vector of auto_ptrs is supposed to be dangerous, correct? That's why boost came up with their version. I would switch to the boost version and retest.

Regards,

Paul McKenzie

AFAIK, an auto_ptr<> holding a vector is dangerous, and not vice-versa. That is because the auto_ptr will call delete (w/o []) on the pointer it holds. I might be wrong, though.

[amag]

Ok my final results running with the latest Qsort in release build for 10000 elements (I only have 256 Mb memory so 100000 won't work):

std::sort using functor: 40 ticks
std::sort using function: 50 ticks
Qsort: 40 ticks

Since my std::vector still consists of objects (not ptrs) I guess the reason that std::sort isn't faster is due to the object construction (although I have taken out the allocation of 4k from the ctor and only do it once for a fair comparison).

Still if speed matters much to you Anthony, you should consider sorting ptrs instead and doing that with std::sort since it's obviously faster in that case!

Since you refuse to respond to my claim that your comparison is seriously flawed I'll go away and let you wrestle with your buggy code. Good luck with getting the code to work with the Pacific Group C++ compiler!

[Graham]

Gabriel: auto_ptr must not be used in STL containers - its unusual copy semantics mean that things go seriously wrong if you try to construct a container of auto_ptrs. In fact, it's supposed to produce a compile error.

[Gabriel Fleseriu]

Originally posted by Graham
Gabriel: auto_ptr must not be used in STL containers - its unusual copy semantics mean that things go seriously wrong if you try to construct a container of auto_ptrs. In fact, it's supposed to produce a compile error.

Oh, yes, of course. I was thinking of auto_ptr holding a C-style vector. Thx for pointing that out. I'll have to take a look to the docu of auto_ptr again, I guess :)

[AnthonyMai]

AMAG:

A few weeks ago I already said on this board that when the structure of object becomes complicated, it would be best to sort index instead of sorting objects directly. At that time Paul accused me of "pulling a fast one" that I am comparing index sorting using qsort() with direct object sorting with std::sort(). I agreed it is not the same thing.

When doing index sorting, both qsort and std::sort() are equally safe, because no object is moved or copies. Just the index to them are swapped. Comparing the best qsort() result witht the best std::sort() using functor result, std::sort() using functor beats qsort with a small margin. Then I discovered some problem with the original qsort, and come up with my own Qsort, which is several times faster, so in another test of index sorting, Qsort clearly beats std::sort() using functor significantly, some times by as much as 2-3 times.

And now you folks are also pulling a fast one by comparing my direct object sorting using Qsort, against index sorting using std::sort(). It's not the same thing Where as possible, people want to do direct object sorting, since if you do index sorting, the objects themselves are still not sorted, and you have to access the objects indirectly through its indexes, which is extra trouble.

Qsort() beats std::sort() in direct object sorting on the count that it can swap objects (which involves merely shifting objects in memory) without actually creating new ones or destroy old ones in the process. std::sort() can not do that by its very design. Fundamentally, there shouldn't be a need to replicate objects in order to move them to a different location.

AMAG is changing the problem by replacing a pointer to a private buffer with an auto-pointer to a shared buffer. In real life, most of time when you have separate objects, you want them to store different data, instead of share a pointer and store the same data. And when you are telling me you have a 256 MB machine, yet you can't sort more than 10000 pieces of data, you are in big trouble with the usability of your product.

As for the Portland compiler. Obvious the original Qsort I posted was from a backed up and unfinished old version, which contains a bug. The latest Qsort should work for Portland compiler in the way I described, since qsort works, too!

[jfaust]

The point is you can obtain the same or better performance results by choosing your data structure correctly, and as an added bonus, you don't have to ignore the C++ standard to accomplish it.

Jeff

[AnthonyMai]

Wow, I thought you guys believe std::sort can sort ANY data type because it is type safe.

Now, I see, if the object you sort contains an auto_ptr, std::sort() does not work. So what other stuff std::sort() can not sort?

And surprise, surprise, surprise! I can use Qsort to sort any class objects that contains auto_ptr without a problem!!!

I discussed previously that of an object's state depends on its data members solely and does not depend on its own memory location, then the object can be moved to a different memory in whole piece without a problem, And Qsort would work on such objects.

And IF an object's state DOES depend on its own location, then such object can not be copied to a different memory location without being changed. In such case NO proper copy constructor or assignment operator can be written for such object. Since std::sort rely on the existence of proper copy constructor or assignment operator, std::sort will NOT work on such object.

Why Qsort works on auto_ptr, but std::sort doesn't? auto_ptr's state does not depend on its own memory location. That's why Qsort can swap it without a problem.

However location-independent does NOT exactly mean the object can be copied. auto_ptr happen to be the sort of NONE-COPYABLE objects I meantioned. By its very design, when you assign an auto_ptr or create a temporary copy of it, the reference count changes and it is no longer in the same state.

So NO appropriate copy constructor or assignment operator can be written for auto_ptr for std::sort() purpose. By saying "appropriate...for std::sort()" I mean proper operations that copies or assigns the object, without changing it.

It's beginning to show that Qsort() has a much wider fit-for-use domain than std::sort() does. If you think it again. There are many many examples of NONE-COPYABLE objects in real life. You can swap them, but you can't copy them. Qsort can do swap without copying, std::sort must make copies to swap objects.

[amag]

AMAG is changing the problem by replacing a pointer to a private buffer with an auto-pointer to a shared buffer. In real life, most of time when you have separate objects, you want them to store different data, instead of share a pointer and store the same data.

This is exactly what you do in your Qsort, just copies the ptr. Don't go around blowing the whistle how unsafe my code is when yours is inherently unsafe and dependant on undefined behaviour! Besides in real life you may very well want to share the ptr. Do you think boost::shared_ptr exists just for fun?


And when you are telling me you have a 256 MB machine, yet you can't sort more than 10000 pieces of data, you are in big trouble with the usability of your product.

I can sort more than 10000, but since all other results either were 10000 or 100000 and I could only do the former. Why? 100000 * 4096 ~ 390Mb > 256 Mb. So all the sorts would perform very bad because of huge amounts of swapping, thus the numbers from that test wouldn't be worth much. And besides it's YOUR product and it has big troubles!

[jfaust]

Are we just regurgitating the same arguments back to you? Do you really think that the ridiculous and dangerous Qsort should be used in place of std::sort? Are you completely blind to the problems with it? Or are you merely so stubborn you refuse to see the sense in it? I just don't get it. It's ludicrous. I refuse to argue this anymore. Many others, with more sense and C++ knowlegde than yourself, have explained in detail the error of your ways, but you refuse to see. There is no helping you. You aren't here to learn anything. You have no care for what other people say. You are here to preach. The problem is your sermon is just simply wrong.

This is my last post on this subject.

Your ignorance is only shadowed by your arrogance.

Jeff

[Paul McKenzie]

Originally posted by AnthonyMai
As for the Portland compiler. Obvious the original Qsort I posted was from a backed up and unfinished old version, which contains a bug. The latest Qsort should work for Portland compiler in the way I described, since qsort works, too! You have the library used by the Portland compiler? How do you know this? Again, Phillip Nicoletti had since the time this post was made, is still having trouble with qsort on the Portland compiler. Read his message again.

To be more accurate, Phillip is not having any trouble with qsort, it's doing what it's supposed to do -- perform undefined behavior for non-POD types. And what if another compiler falls flat on its face with your code or qsort? You have nothing to back up your claims to the compiler vendor as to why their qsort doesn't work for your classes. Absolutely nothing. If std::sort breaks, we have everything to back up our claims that it is broken, and that is the ANSI/ISO C++ standard.

If you were to attend a conference of C++ experts from around the country, and stood up and made all of these claims you're making, you'd be laughed out of the conference hall.

Regards,

Paul McKenzie

[Philip Nicoletti]

Then I discovered some problem with the original qsort, and come up
with my own Qsort, which is several times faster, so in another test
of index sorting, Qsort clearly beats std::sort() using functor
significantly, some times by as much as 2-3 times.




Hi Anthony, could you post your testing code ? I ran
tests, using indirect sort for both std::sort and Qsort()
and found std::sort to be slightly faster. Here are
some typical results. (Visual C++ version 5).

A) On a lower-end computer :

a1) N = 30000 ... Creates data in 6516 ticks
std::sort : 78 ticks , Qsort : 109 ticks

a2) N = 50000 ... Creates data in 18000 ticks
std::sort : 156 ticks , Qsort : 188 ticks

a3) N = 60000 ... Creates data in 88000 ticks ("thrashed" computer before sorting started)
std::sort : 510 ticks , Qsort : 610 ticks


B) on higher-end computer

b1) N = 100000 ... Creates data in 1500 ticks
std::sort : 260 ticks , Qsort : 303 ticks

b2) N = 200000 ... Creates data in 3000 ticks
std::sort : 620 ticks , Qsort : 755 ticks

b3) N = 250000 ... Creates data in 70100 ticks ("thrashed" computer before sorting started)
std::sort : 2359 ticks , Qsort : 2640 ticks

[Philip Nicoletti]

As for the Portland compiler. Obvious the original Qsort I posted was from a backed up and unfinished old version, which contains a bug. The latest Qsort should work for Portland compiler in the way I described, since qsort works, too!


No. Your latest Qsort() also failed on the structure given
in the previous thread. (As did the qsort() that shipped
with the Portland Group compiler). Which version of
the Portland Group compiler did you test qsort() on ?

I am not sure which version we have (I did not install it),
but I think it is about 6 months old.

[cup]

Just as a matter of interest, is this qsort Hoare's 1962 Quicksort or Scowen's 1965 Quickersort. There is also Sedgewick's Sedgesort which is faster than Quicksort for large amounts of data but that has probably got nothing to do with this thread.

There is a library of sorting techniques at
http://www.yendor.com/programming/sort/ if you really want to compare techniques.

[AnthonyMai]

CUP:

There is NO difference mathematically between Qsort(), qsort() or std::sort(), they all use the same mathematic algorithm underneath.

What makes them different the OVERHEAD of data manipulation, copying and swapping. Qsort() and qsort does not have the overhead of calling object constructor, assignment operator and destroctor, where as std::sort construct temporary objects and destory them in order to swap objects. When objects are complicated to create or copy, this overhead can slow things down to a complete craw.

Another overhead is the passing of parameters. All parameters passed to Qsort/qsort() are pointers and they are easy to pass.

When using std::sort() with a functor, the third parameter passed in is an object passed in by value, i.e., temporary copy of that object. If that object is none-trivial to copy, it brings a huge performance hit.

One example I cited a number of times, is some code Paul posted to show me how to do index sorting using std::sort(). His functor is a class that contains a vector which contains all the data he is sorting. So copying this functor along is an order of N operation. Multiple with number of parameter passing, which is a in the order of N*logN, the total complexity is N*N*logN, that's even slower than bubble sort's N*N.

Direct object passing by value could often result in big performance hit. That is especially true if functions are called in a recursive way. Any competent C++ programmer SHOULD know that. Unfortunately most C++ programmer, even those with several decades of experience, often doesn't know or simply forget it altogether. A lot of the STL source code could have used object references, but used direct object copying instead, that can be blamned for the frequent performance problem that STL users see daily.

[Zeeshan]

There is NO difference mathematically between Qsort(), qsort() or std::sort(), they all use the same mathematic algorithm underneath.


Again you are going to compare apples with oranges, compare algorithm wit specification. std::sort() is not an algorithm it is an specification, so how can you compare this. Its implementation is dependend on vendor of STL. So compare qsort with std::sort is totally useless, (you can compare qsort with VC implementation of std::sort() but cant with specification of std::sort )

I know you dont like that anyone advice you to read what, but still i again recommand you one more book

Efficient C++
By
Dov Bulka
David Mayhew

To get most of your questions's answer related to temporary, STL, ctor, copy ctor, virtual function, function object etc