The fear of the misterious

Quote:

---

Originally posted by AnthonyMai

The problem is you may FORGET! There are a lot of things that will cause you to forget to write the copy constructor or assignment constructor. And nothing in the compiler will remind you that you missed something. Maybe you initially don't need one, and later you modified something and you need to add one on, but you forget. It's a quite possible scenary.

The problem is, if you see a line of your own code where you assign one object to another, you might remind yourself to check
to make sure you coded the assignment operator. But if you don't do any copying and assigning yourself, what would remind you to make sure that you have provided every thing to baby-sit the ATL underneath, which doesn't even cry when you missed something?

---

Please do not presume to know how I go about my coding. Part of the design process (before coding starts) is to determine whether copying is a valid operation for the class. If it is not, then the copy ctor and copy assignment operator are declared private. This way, contrary to what you presume, the compiler most definitely will tell me if I attempt to make a copy. On the other hand, if the initial design says that copying is valid, then any modification to the members of the class necessitates a review of the copy ctor/copy assign (and destructor and default ctor).

No, I don't code an assignment, then make a note to check the assignment operator - the decision has been made. If I (erroneously) code an assignment for a class that can't be assigned, then the compiler will throw out an error, and I can review the situation. However, since my classes tend to be well designed, this is rarely an issue, since the decision to disable copying usually implies that there will never be a need to copy, so I probably wouldn't even consider trying to assign one to another.

Your reply suggests that you take a very piecemeal approach to coding, trying things to see if they work, tweaking here and there, making up the design as you go. I take a somewhat different approach - my classes are designed with an end in mind, that means that most of the major decisions have been made before Visual Studio has even been fired up.

In short: No, I won't forget about such important things, and I make sure that if I accidentally do something that I've determined isn't allowed, then the compiler will tell me that I've done something wrong.

Jeff:

Funny that There's never been an maintainability issue with my code. I just write once, get it work frawlessly, and my code are usually left un-touched for months or years. Because it just works and there is no need for any bug fix, nor there is any for for performance improvement.

It is with code that written by some poor programmers, that constantly needs a bug fix now and then, that maintainability becomes an issue. Not me.

And, remember, maintainability is not an issue when usability becomes an issue. Now some home work. I have a class which is rather simple. But it dynamically allocate a buffer of about 4 KB (the exact size is unknow until run time), and deallocate the buffer upon destruction.

What I want you to do, is I have an array 100,000 such objects. And I want you to write a piece of code using std::sort() to sort it. I want you to sort by the string fld1.

I can sort using Qsort() in under a second, I don't want you to std::sort() in one second. I want you to get it done in one minute. Can you get it done?

The class looks like this:

Code:

---

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

---

Graham:

When I said "You will forget". The "you" is not meant to be Graham or any specific person. The "you" means the general programming public and an average programmer. I am sure you Graham is more qualified than an average programmer. But we are not here to discuss how Graham or Anthony should be writting their code. We are discussing general coding practice that applies to every one.

Your suggestion of ALWAYS code a copy constructor and make it private when you deemed it should not be called is a good one. But when it comes to the general public, you have to admit it happens frequently that people forget to code copy constructors quite a lot.

Quote:

---

Originally posted by jfaust
"Relying on undefined behavior is wrong. It feels ridiculous that I even have to argue such a simple point.

Jeff

---

That sums it all up. All of this "I can beat this, and I can beat that" doesn't mean a hill of beans given your quote above.

I've mentioned this before, but this thread and others are almost to a tee the same threads on comp.lang.c++ started by someone who claimed that their "string class was faster than std::string". I think the poster was someone named "Peter Olcott". If you check that thread out (you can probably find it on google), and check the messages back and forth between the experts and Mr. Olcott, you will say to yourself (pardon my language) "Oh s*it! This *is* the same thing!", even down to the personality of Olcott.

There is one difference -- at least Olcott posted his messages there and took his lumps. You should check the back-and-forth between Olcott and PJ Plauger! It is very interesting reading.

Regards,

Paul McKenzie

Quote:

---

You are un-necessarily creating new objects here, maybe to slow qsort() down a bit to make it look bad? You could have done this;

code:--------------------------------------------------------------------------------
inline int qsortCompare(const void *a , const void *b)
{
return ( ((D*)a)->ia - ((D*)b)->ia);
}
--------------------------------------------------------------------------------


Second, what causes it fail on pgCC is the third parameter on this line

code:--------------------------------------------------------------------------------
qsort(&v1[0],v1.size(),sizeof(v1[0]),qsortCompare);
--------------------------------------------------------------------------------


What do you suppose sizeof(v1[0]) to be? Looks to me, v1[0] is a reference to a D object, NOT an instance of D object. Hence sizeof of it evaluate to 4 bytes, which is NOT the size of D object. That's why it fails. You are fortunate that VC interpreted v1[0] differently when it evaluate the sizeof.

Change it to sizeof(D), try again. I am pretty sure it will work then. But let me and others know what is your finding.

---

1) I was not comparing performance, so I just wanted to get
the comparison function correct. However, I made that change.

2) changed to sizof(D) ... same problem occurred.
(both sizeof( ...) = 24 on pgCC

"What I want you to do, is I have an array 100,000 such objects."

When deciding on what data structure to use, you must account for how it is to be used. You can't foresee everything, but you can have a pretty good idea.

If there's a performance issue, using undefined behavior is not the solution. There are better solutions that will outperform your ridiculous Qsort. One option is to have a container of pointers instead of objects, and write a comparison functor to handle the comparison correctly. Another option would be to use a container that maintains the list as sorted.

The correct choice depends on the data and how it is used.

Jeff

Quote:

---

Originally posted by Philip Nicoletti


1) I was not comparing performance, so I just wanted to get
the comparison function correct. However, I made that change.

2) changed to sizof(D) ... same problem occurred.
(both sizeof( ...) = 24 on pgCC

---

Phillip, just as a test -- did you check to see if qsort() on the Portland compiler works with plain old data types? If so, then (snicker). Pardon my language again, but "ain't undefined behavior a b*tch?"

So far Phillip, you've sorted successfully with std::sort, but qsort() still has problems. I guess it's time to dig out the source code to pgCC's qsort() implementation and look at the code, while your colleague at work has sorted the data and is now working on the GUI component of your app :)

I checked their website. It looks like the cost of the compiler is $300. I suggest the OP pay for his own and figure out what's wrong with qsort(). I mean, isn't the OP the one making the claims of qsort() safety on non-trivial objects?

Regards,

Paul McKenzie

Quote:

---

Originally posted by AnthonyMai
Your suggestion of ALWAYS code a copy constructor and make it private when you deemed it should not be called is a good one. But when it comes to the general public, you have to admit it happens frequently that people forget to code copy constructors quite a lot.

---

Please don't put words in my mouth. I did not say "always code a copy constructor". I said "always consider the copy constructor". If the compiler-generated ctor is sufficient for the class, and I don't need to disable it, then I won't bother writing one. But that omission will be a considered opinion, not a mistake. I do not subscribe to the view that you should always write out in full what the compiler would have generated anyway.

Quote:

---

Originally posted by jfaust
"What I want you to do, is I have an array 100,000 such objects."

When deciding on what data structure to use, you must account for how it is to be used. You can't foresee everything, but you can have a pretty good idea.

If there's a performance issue, using undefined behavior is not the solution. There are better solutions that will outperform your ridiculous Qsort. One option is to have a container of pointers instead of objects, and write a comparison functor to handle the comparison correctly. Another option would be to use a container that maintains the list as sorted.

The correct choice depends on the data and how it is used.

Jeff

---

Note how everyone here has run std::sort with no problems whatsoever. I would say about 7 or 8 of us here, on different compilers and OSes has run std:sort, and not a single problem.

However, it seems that QSort (and even qsort on the Pacific Group compiler if I read Phillip correctly) is having problems. Core dumps, segmentation faults, access violation errors, etc.

An illustration of what you're talking about, right before our eyes.

Regards,

Paul McKenzie

Before even looking at the times posted, has anyone taken the time to see if the data is actually sorted correctly using QSort?

I made a few changes, and sorted pointers on 100,000 elements. A few observations:

a) std::sort beat qsort() when sorting 100,000 pointers, given the criteria of sorting on fld1.

b) Since we're now sorting pointers, qsort will work since pointers are POD types.

c) An interesting thing when outputting the results of the vector after the supposed sorts took place:
- std::sort correctly sorted the first 200 elements.

- qsort correctly sorted the first 200 elements.

- Qsort not only was slower than std::sort, but what good is a sort that doesn't sort correctly? That's right, QSort() totally mangled the data, even for a POD type.

It is not a matter of "tweaking it here and there to reduce the time", the thing just doesn't work. The QSort() code is taken directly from another thread about "QSort beating std::sort by 1000 times".

Here is the code:

Code:

---

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

#define BUFF_SIZE                4096

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

#define ELEMENT_COUNT        100000

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 *)
    );

void dump_contents(const intvec& v, int num)
{
    for (int i = 0; i < num; i++ )
        cout << v[i]->fld1 << endl;
    cout << endl;
    char c;
    cin >> c;
}


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

    intvec::iterator it1 = v.begin();
    intvec::iterator it2 = v.end();

    while (it1 != it2)
    {
        *it1 = new SomeClass;
        ++it1;
    }

    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;

    dump_contents(v, 200);

    randomise_vector(v);

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

    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;
    dump_contents(v, 200);

    char c;
    cin >> c;

    it1 = v.begin();
    while (it1 != it2)
    {
        delete (*it1);
        ++it1;
    }
    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;
}

---

I added a "dump_contents" to this whole charade. Adjust the second argument to suit your tastes. (Make sure you hit a key and hit enter after every dump_contents call to continue processing).

Here are some more observations:

a) The code to std::sort comparison is much simpler to maintain. Look at the hoops you have to jump through to get the comparison function to work for q(Q)sort. It breaks practically every rule of C++ maintenance.

b) If you comment out qsort() and replace with QSort(), dump_contents will reveal for one and all that QSort() has a bug, how major, I don't know and I don't care. Replace the QSort with qsort, and qsort does the job, but slower than std::sort.

c) The timing that I am getting are as follows:

using functor : 361 ticks
using function: 582 ticks
using qsort: 828 ticks
using QSort: (data mangled)

Regards,

Paul McKenzie

Just thought I'd point out a direct quote by Anthony, made earlier in this thread:

Quote:

---

Funny that There's never been an maintainability issue with my code. I just write once, get it work frawlessly, and my code are usually left un-touched for months or years. Because it just works and there is no need for any bug fix, nor there is any for for performance improvement.

---

Yes, it is pretty funny at that. It looks like your ridiculous Qsort does not work "frawlessly".

Jeff

I just took the code that was posted in the other thread. It now sorts correctly, but here are the times I'm getting:

std::sort using functor 391 ticks
std::sort using function 563 ticks
QSort 581 ticks
qsort 875 ticks

Regards,

Paul McKenzie

Paul:
Can you at least tell people the real number, OK?
Forget about how fast or slow Q(q)sort is, Your figure for std::sort simply does not look right:

Quote:

---

Paul's figure:
std::sort using functor 391 ticks
std::sort using function 563 ticks
QSort 581 ticks
qsort 875 ticks

---

I am consistently getting these numbers:
std::sort using functor: 8594 ticks
std::sort using functor: 8703 ticks
Qsort: 438 ticks.

I have a PIII 1700MHz machine, with 512 MB memory. I believe Paul may have a faster machine than mine. But there is no Paul's machine is 20 times faster than mine, in regard to std::sort. If you indeed has a 20 times faster machine, you will see Qsort do it in just 20-30 ticks.

I don't trust Paul's numbers at all. Sorry.

As stated in his previous post, Paul made an intelligent choice about what data structure to use, the result being that he is sorting pointers.

Jeff

Quote:

---

Originally posted by AnthonyMai
Paul:
Can you at least tell people the real number, OK?
Forget about how fast or slow Q(q)sort is, Your figure for std::sort simply does not look right:


I am consistently getting these numbers:
std::sort using functor: 8594 ticks
std::sort using functor: 8703 ticks
Qsort: 438 ticks.

I have a PIII 1700MHz machine, with 512 MB memory. I believe Paul may have a faster machine than mine. But there is no Paul's machine is 20 times faster than mine, in regard to std::sort. If you indeed has a 20 times faster machine, you will see Qsort do it in just 20-30 ticks.

I don't trust Paul's numbers at all. Sorry.

---

I have a Pentium 4 (1.7 Gigahertz)
512 Meg Ram,
768 Meg Virtual memory

Those are the numbers with a freshly rebooted machine. Note, that I am running in Release Mode. You could be running a debug version.

Regards,

Paul McKenzie