The Qsort challenge

[AnthonyMai]

A while ago, I posted my Qsort code and explained why it can be used to sort any object arrays or vectors, just like any POD data types. The code works on all compilers I can lay my hands on. And it is much faster than std::sort when the object is none trivial.

There was one, unsubstantiate claim that when a specific compiler was used, and when sorting a specific type of objects, Qsort does not give the right result. That claim was un-substantiated because it was not verified by any one else that uses that specific compiler, nor did the original poster provide any file to back it up.

So here is the challenge, I am posting my Qsort code again. And if the original challenge do believe it doesn't work for a specific object type on a specific compiler, please compile the stuff with assembly output enabled, and zip all the file up, and post it here. So every one can verify the result.

Here is my Qsort code:

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

#define ELEMENT_COUNT	10000 //00

#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);
    stop = clock();
    cout << stop - start << " ticks" << endl;

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


// 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;
}

[Yves M]

Well, try this

#define ELEMENT_COUNT  10000000

typedef vector<int> intvec;

void randomise_vector(intvec& v)
{
    srand(time(0));
    char szBuf&#091;15&#093;;
    for (intvec::iterator i = v.begin(); i != v.end(); ++i)
    {
    *i = rand();
    }
}

inline int qscompareint(const void* lhs, const void* rhs)
{
    return (*((int *) lhs) < (*(int *)rhs));
}

int main()
{
  srand(clock());
    vecor<int> v(ELEMENT_COUNT);

    randomise_vector(v);

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

    randomise_vector(v);
    cout << "Qsort: ";
    start = clock();
    Qsort(static_cast<void*>(&v&#091;0&#093; ), ELEMENT_COUNT, sizeof(int), qscompareint);
    stop = clock();
    cout << stop - start << " ticks" << endl;

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

It's not sorting classes, only sorting integers, but I can see which version is faster

[PaulWendt]

I eagerly wait for Philip's response, but in the meantime, there
have already been ways people mentioned to get beyond the
copy constructor. It's not that std::sort is any slower; it's that it
calls the copy constructor, which your method doesn't do. You say
that you can use a memcpy() [or the equivalent] to swap
elements ... and that behavior is undefined in the standard.
Maybe your code will work on every compiler known to man; then
again, maybe it won't.

Like many people said in the last thread, instead of sorting items
that require costly copy constructors to be called, make the
container hold pointers instead of objects by value. If I recall
correctly, tests run in those conditions had std::sort performing
at around the same speed as your QSort() [I can't recall, but
std::sort might have been negligably faster].

The point is that you're using non-standard behavior and a
flawed methodology to "prove" that your sort is superior. It
doesn't take a PhD to realize that calling copy constructors will
be costly; most C++ programmers who've been at things a while
will recognize this and make changes appropriately. Of course,
a container of objects by value is the rare case anyway. In many
C++ applications, we want to deal with objects as a base class
so that we can utilize polymorphism effectively.

--Paul

[Paul McKenzie]

The code works on all compilers I can lay my hands on

Famous last words for those who stray from the standard, and find out that their compiler lets them get away with it. Just like calling "delete" on a "new[]" object works on many compilers.

And it is much faster than std::sort when the object is none trivial.

And if it is non-trivial, then what? Cross your fingers and hope the program doesn't core dump or GPF?

There was one, unsubstantiate claim that when a specific compiler was used, and when sorting a specific type of objects, Qsort does not give the right result. That claim was un-substantiated because it was not verified by any one else that uses that specific compiler, nor did the original poster provide any file to back it up.

That's because no one wants to waste their time. Also, all of this is your job, not ours. You are the one making the wild claims that your sort is so great, you do the research. You're kidding if you think that a failure in your code is going to make the person zip up assembly language to you. What for? It failed, just as what we stated could happen.

We boldly stated that what you were doing is undefined as per ANSI specifications. Everyone from people here at CodeGuru to comp.lang.c++ to the head of the ANSI committee. All stated that qsort or your QSort is not guaranteed to work for non-POD objects types, most likely objects derived from virtual base classes. You didn't listen and you got burned. Do you need more convincing? Post your code to comp.std.c++. Let them have a laugh. Or are all of them wrong too?

If it's so great and you're so sure of the soundness of your code, why haven't you submitted any of it to any C++ magazine, expert, periodical, whatever to have them replace the std::sort algorithm with your sort? What are you afraid of? www.boost.org takes submittals, why not submit it there?

Listen, most are really tired of debating this with you and we know that you lost this debate a long time ago. Instead, you should be spending your efforts coming up with a faster std::sort, and forget about this q/QSort debacle.

Regards,

Paul McKenzie

[Zeeshan]

Again useless discuss started by AnthonyMai.

Regardless of all the technical details which are given to AnthonyMai i want to add one more claim in this thread.

BMW is better than CAR.

Well what is the significance of this claim? Nothing i m comparing totally two different things. If i said BMW is batter than FARARI regardless claim is right or wrong (Although Formula 1 just prove opposite ) it at least make scence. But in the above claim i compare apples with oranges.

Now AnthonyMai can you tell me what is std::sort? What algo does it follow? Where in standard it is written that library vendor has to use this algo to implement std::sort?

std::sort is just an specification now it is upto library vendor to implement it with suitable algorithm. So you are comparing qsort with just specification.

If you said qsort is better than this implementation of std::sort then at least this claim made sence (it doesnt mean claim is right claim is still wrong on POD)

If you still claim you are right and all of us are wrong then dont waste you time on us and publish your ideas on some magzine rather than start comparing this useless stuff after every few weeks.

[Paul McKenzie]

Originally posted by Zeeshan
Again useless discuss started by AnthonyMai.

Regardless of all the technical details which are given to AnthonyMai i want to add one more claim in this thread.

BMW is better than CAR.

Believe it or not I got a chuckle when you stated that It is exactly what this is -- comparing a sorting method with a specification.

Now AnthonyMai can you tell me what is std::sort? What algo does it follow? Where in standard it is written that library vendor has to use this algo to implement std::sort?

Which is why it makes more sense to improve std::sort, but I've stated this over and over but it goes in one ear and out the other.

If you still claim you are right and all of us are wrong then dont waste you time on us and publish your ideas on some magzine rather than start comparing this useless stuff after every few weeks.

You cannot get away with posting or submitting this stuff anywhere else without being humiliated. I posted Mai's qsort claim on comp.lang.c++, and it was a good thing I posted just a few of the responses. Yves (he wasn't the moderator back then, but if he was) would have been "snipping" away and placing asterisks on many of the words. One guy got so frustrated with trying to explain everything we are trying to explain, he just let loose with some choice words.

Regards,

Paul McKenzie

[Gabriel Fleseriu]

It is trivial to write a class that, without having any practical use, will break Qsort.

[AnthonyMai]

It is trivial to write a class that, without having any practical use, will break Qsort.

Talking is cheap. Oh I am sure you can write a bizillion different classes that will break Qsort. Can you actually come up with one and post the source code as well as the compilation result here? Without seeing that, and without seeing the original challenger who claimed that Qsort didn't work on his compiler posting his compiler output to back up his claim, it's all cheap talks.

BTW, std::sort doesn't work on a lot of things, too. Try throw in a couple of private constructors or private destructors. Or try to throw in some auto pointers. Or try to put in some pointers that point to other instances of the object.

Basically std::sort is broken whenever you have some class where appropriate copy constructors can not be written.

There is one case where std::sort would not work, and Qsort would work perfectly. One concept that is some people's favorable is the so called Int2Type concept, You instantiate a different object type, based on different value of an integer or enum passed in as template parameter. std::sort would not be able to operate on a continuous array of such objects, since each instance of the object is all of different type, based on the different integers used to instantiate them. However, since all these objects have the same size and data structure internally, Qsort would work on them without a problem!!!

[Gabriel Fleseriu]

class SomeClass
{
public:
	SomeClass():val_(0){self_=this;}
	~SomeClass(){};
	SomeClass(const SomeClass& src){self_=this; val_=src.val_;}
	SomeClass& operator=(const SomeClass& src){	val_=src.val_; self_=this; return *this;};
	int get_val()const{return self_->val_;}
	void set_val(int i){self_->val_=i;}
private:
	   SomeClass *self_;
	   int val_;

};

[Yves M]

Originally posted by Paul McKenzie
Which is why it makes more sense to improve std::sort

I've been thinking about this. The basic problem in this case is that copying and swapping "values" is expensive and I guess introsort doesn't handle this well. Element comparison is not expensive though. What other sorting algorithm would do less swaps ?

Then again, I wonder whether this problem is worth solving at all, since the case where you would put large chunks directly into a container as opposed to pointers is probably rare.

Maybe there is a need for specific "indirect" containers ? Like a indirect_vector which would only store reference counted pointers to objects ?

[jfaust]

Maybe there is a need for specific "indirect" containers ? Like a indirect_vector which would only store reference counted pointers to objects ?

That's generally what I do for such containers:

typedef boost::shared_ptr<MyClass> MyPtr;
typedef std::vector<MyPtr> MyClassVector;

MyClassVector v;

// memory released automatically after use
v.push_back(MyPtr(new MyClass));

Now, when templated typedefs are added to the standard, you could do something like:

// Not C++ yet, but fingers are crossed:
template<typename T>
typedef std::vector<boost::shared_ptr<T> > SharedVector;

typedef SharedVector<MyClass> MyClassVector;

You could even templatize the container...

Jeff

[Paul McKenzie]

Originally posted by AnthonyMai


Talking is cheap.

Again, post this nonsense in a peer group of C++ experts and see how far you get. You keep saddling us with this junk, it's time for you to stop the "cheap talk" and show your code and explain it to experts.

Regards,

Paul McKenzie

[jfaust]

Again, post this nonsense in a peer group of C++ experts and see how far you get.

Yes, Anthony, why don't you take the gloves off and post this where you can be properly ridiculed?

Jeff

[Yves M]

Originally posted by jfaust
Now, when templated typedefs are added to the standard, you could do something like:

Arg, I would love templated typedefs The workarounds are not always pretty

But well, vector_indirect would not satisfy the property of vector that all elements are stored contigously :/

P.S. Please don't get into flame-wars This thread (and the last one on qsort) is interesting, so it's best not to get too personal. I would hate to have to close this thread :/

[jfaust]

But well, vector_indirect would not satisfy the property of vector that all elements are stored contigously :/

Insofar as you can access the elements as an array, the elements (pointers) are contiguous. I think this is what really matters--constant time access to elements.

Jeff