STL Vector problems

"But each class's constructor is called on construction, which to me is closer to the behavior of a virtual method than a regular method call"

By adding the virtual keyword before a function you are telling the compiler that a derived class may have an overiding function that should be called in place of the abstract classes function. In the case of a pure virtual function (= 0 on end) the derived class must have an overiding function or the compiler will throw a linker error. It is possible to have inline virtual functions, but I understand that compile time increases over normal inline functions. As Graham said the constructor is never virtual because the base class must always be created (if you use the watch on an object of a derived class, when debugging, you will see the inherited classes appear as an object of the derived class - as opposed to actually absorbing the functions and variables into the this pointer of the derived object).

I'm not really sure what your trying to say, but to me the constructor is closer to a regular function call since a more abstract function cannot be used instead (correct me if I'm wrong), for the objects construction. To me it is like a regular function, because, like all regular functions, they are detailed wholly within that classes scope and no other.

Anyway, back to you guys, I'm finding this whole topic of conversation very interesting.

Alan.

And another argument against myself: constructors don' t behave polymorphically.

I guess constructors are really different beasts altogether. Calling a constructor calls a string of methods starting with the most-base constructor down to the most derived constructor.

It seams that this calling sequence is known at compile time, and therefor could be inlined somewhat. I don't know--there's probably other issues that get in the way.

Thanks for the clarifications,

Jeff

There was a discussion about ctors on comp.lang.c++.moderated, prompted by the question "why don't ctors have return values?" The general consensus seemed to be that ctors (and dtors) are "special" - they're not functions (in the general sense) since they obey all sorts of special rules. And because they don't have a return type. Their purpose is to construct an object: if the object doesn't need construction (like the functor above), the compiler ought to be at liberty to optimise the ctor away (unless you do anything to try to see how often the ctor is being called, in which case, it's obliged to keep it and call it). A good reason for not defining a ctor if the compiler-generated one is sufficient, I suppose.

I am not going to contact Scott Meyers or Nicolai Josuttis or any of a couple of million guy out of this planet of 6 billion population, to discuss any issue. I don't have time to do so, more than they have time to come to me to discuss them. (They are welcome to do so, though)

But, look, the fact is it is plain wrong to assume that compiler can inline any thing as long as you declare it as inline, especially when it comes to STL. And thank God, virtually NONE of the STL stuff are actually inlined, otherwise we will be seeing simple programs written in STL becomes so big they could easily fill up a whole hard disk, due to the function inlining.

There mere fact that although most STL based applications are bloatware, they are not yet bloated in any ridicurious way, says to the truth that virtually nothing in STL has actually been inlined.

Gosh, how many times have I read on this board of the pro-STL guys complaining this and that compiler could not compile a piece of template code correctly? Templates are so complicated to implement that most compilers can't implement them correctly. How could you expect any compiler do a smart job in inlining template functions?

I am not convinced of Scott Meyers's claim that his test result show std::sort faster than qsort() by 670%. Show me the code. Paul tried to show me once how std::sort() can sort as fast as qsort, but his example failed him miserably by showing a speed many orders of magnitude slower.

If any one can show me a piece of code that shows std::sort() is faster than qsort() in sorting the same thing, I'd like to see it here.

Finally, std::sort() does use recursive function calls. So any inlining is impossible even in theory. Here is the sorce code, re-written in a moreadable fashion:

Code:

---

template<class _RI, class _Ty, class _Pr>
inline void _Sort
(
    _RI _F,
    _RI _L,
    _Pr _P,
    _Ty *
)
{
    for (; _SORT_MAX < _L - _F; )
    {
        _RI _M = _Unguarded_partition(
            _F,
            _L,
            _Median(
                _Ty(*_F),
                            _Ty(*(_F + (_L - _F) / 2)),
                _Ty(*(_L - 1)),
                _P
                ),
            _P
            );

                if (_L - _M <= _M - _F)
        {
                        _Sort(_M, _L, _P, _Val_type(_F));
            _L = _M;
        }
                else
        {
                        _Sort(_F, _M, _P, _Val_type(_F)),
            _F = _M;
        }
    }   
}

---

I don't want to dispute which function is faster, as if I was to sort a million structures, I would certainly write an algorithm myself. Now, I have two questions:

1. Why would one of the functions, sort and qsort be significantly faster than the other. Don't they both implement the QuickSort algorithm?
2. Why does the std::sort use a recursive structure? I have always found that an iterative approach is faster and more efficient.

Quote:

---

Originally posted by Anthony Mai
Show me the code. Paul tried to show me once how std::sort() can sort as fast as qsort, but his example failed him miserably by showing a speed many orders of magnitude slower.

---

I showed you no such thing. What I did show you is that std::sort works on indices, and it was pointed out to you as such. Please stop spreading this propaganda here and on other threads.

As far as not wanting to talk to Meyers , all it takes is to post your claims at comp.lang.c++.moderated and you will get responses since he and others are there. That's all, and it only takes a few clicks using IE or Netscape to ask a question in a newsgroup. I post there, NMTop40 posts there, James Curran posts there, and even newbies to C++ who post to CodeGuru post there also. What's wrong with just clicking on the link that I gave to Josuttis's e-mail? It just takes a move of a mouse and a push of a button, not exactly yeoman's work.

Regards,

Paul McKenzie

Code:

---

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

using namespace std;

typedef vector<int> intvec;

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

inline bool stllessfunc(int lhs, int rhs)
{
    return lhs < rhs;
}

inline int qscompare(const void* lhs, const void* rhs)
{
    return *(static_cast<const int*>(lhs)) < *(static_cast<const int*>(rhs)) ? -1 :
        (*(static_cast<const int*>(rhs)) < *(static_cast<const int*>(lhs)) ? 1 : 0);
}

int main()
{
    intvec v(1000000, 0);

    randomise_vector(v);

    cout << "std::sort using functor: ";
    clock_t start = clock();
    sort(v.begin(), v.end(), less<int>());
    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]), 1000000, sizeof(int), qscompare);
    stop = clock();
    cout << stop - start << " ticks" << endl;

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

---

Output from program:

std::sort using functor: 830 ticks
std::sort using function: 1530 ticks
qsort: 3400 ticks

Woohoo!

Similar results:

std::sort using functor: 380 ticks
std::sort using function: 591 ticks
qsort: 1212 ticks

smiles,

Jeff

Here are the results from Borland Builder C++ 6.0:

std::sort using functor: 265 ticks
std::sort using function: 422 ticks
qsort: 531 ticks

Regards,

Paul McKenzie

Here is Sun Solaris (very slow):

std::sort using functor: 4950 ticks
std::sort using function: 5380 ticks
qsort: 7250 ticks

Regards,

Paul McKenzie

Hold on to the excitement yet!

In Graham's code, the two comparison function use are not equivalent in code complexity. So it is not quote a fair comparison.

Granted when taking that difference away, qsort() is still slower than std::sort(). I accept that. And I looked into qsort source code, and see why:

Code:

---

static void __cdecl swap (
    char *a,
    char *b,
    unsigned width
    )
{
    char tmp;

    if ( a != b )
        /* Do the swap one character at a time to avoid potential alignment
          problems. */
        while ( width-- ) {
            tmp = *a;
            *a++ = *b;
            *b++ = tmp;
        }
}

---

The swap function used by qsort swaps object one byte at a time, while as std::sort has the benefit of compiler optimization and swaps things at least 4 times faster (a 4 bytes integer at a time). So indeed qsort is bad in this aspect.


But the fact still remains that Scott Meyers is WRONG in asserting that inlining makes std::sort faster. I dumped both the release version and debug version compiled code to assembly. Guess what:
Not a single inline function is being actually inlined.


std::sort() wins this battle over qsort purely by the fault of qsort author not being able to write something that copies more than a byte at a time. It also thanks to the fact that the object less<int> Graham used is an empty object, and hence passing it is never a huzzle. Next time when the object is more than a trivial int, and you are passing a none-empty comparator object in, you will be in trouble using std::sort. Paul's code has already demonstrated that.

Assuming you only looked at VC++ source code, what is your explanation for Borland Builder 6.0 and Solaris std::sort beating qsort()?

And of course, Meyers is wrong (/sarcasm off).

Regards,

Paul McKenzie

Quote:

---

Originally posted by Anthony Mai
Next time when the object is more than a trivial int, and you are passing a none-empty comparator object in, you will be in trouble using std::sort. Paul's code has already demonstrated that.

---

And so qsort() will beat std::sort() if there is, say a string as opposed to an int. OK, whatever you say.

VC 6.0:

Code:

---

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

using namespace std;

class SomeClass
{
  public:
    std::string fld1;
};

struct SortFld
{
    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", rand());
        (*i).fld1 = 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());
}

int main()
{
    intvec v(1000000);

    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]), 1000000, sizeof(SomeClass), qscompare);
    stop = clock();
    cout << stop - start << " ticks" << endl;

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

Output:
std::sort using functor: 6339 ticks
std::sort using function: 8672 ticks
qsort: 8762 ticks

---

Regards,

Paul McKenzie

Quote:

---

I am not convinced of Scott Meyers's claim that his test result show std::sort faster than qsort() by 670%. Show me the code. Paul tried to show me once how std::sort() can sort as fast as qsort, but his example failed him miserably by showing a speed many orders of magnitude slower.

---

OK, not 670% - I concede defeat on that, since my system is obviously not the same a Scott Meyers'. But 410% is still pretty impressive.

Quote:

---

The swap function used by qsort swaps object one byte at a time, while as std::sort has the benefit of compiler optimization and swaps things at least 4 times faster (a 4 bytes integer at a time). So indeed qsort is bad in this aspect.

---

So how do you propose to improve qsort's swapping? One of the arguments we've used against qsort is its lack of type-safety. It's that lack that is directly responsible for its inefficiency in swapping. I would hope that any half-decent std::sort implementation would use std::swap to swap objects, because then I can specialise swap for my class and make it efficient. You can swap two vectors (of any size) in the time it takes to swap two pointers: you can tell std::sort that, but you can't tell qsort.

These factors are not annoying little details that help to explain away an inconvenient result - they are fundamental reasons why std::sort is preferable to qsort.

Quote:

---

But the fact still remains that Scott Meyers is WRONG in asserting that inlining makes std::sort faster. I dumped both the release version and debug version compiled code to assembly. Guess what:
Not a single inline function is being actually inlined.

---

And just think, if the compiler did inline those functions, just how embarrasing the comparison would be then.

Quote:

---

In Graham's code, the two comparison function use are not equivalent in code complexity. So it is not quote a fair comparison.

---

Don't talk tosh. I tried to make the two functions of equivalent complexity. That I couldn't is entirely down to qsort's requirements on the function (the need for void* arguments and a three-valued result). Don't tell me it's not fair, both functions were as efficient as the constraints allowed - it's another fundamental factor in the comparison: std::sort allows you to to use less complex comparison functions.

Quote:

---

std::sort() wins this battle over qsort purely by the fault of qsort author not being able to write something that copies more than a byte at a time.

---

Cobblers. It's not the author's fault - he's hamstrung by the nature of qsort.

Quote:

---

It also thanks to the fact that the object less<int> Graham used is an empty object, and hence passing it is never a huzzle.

---

And the original functor I proposed (and that you objected so strongly to) is also an empty object. That's another factor: any predicate should be an empty object.

I checked the compiled output of Visual C++ 6.0 to see if the calls to operator() were being inlined. As far as I could tell, as long as the operator() was not too big, Visual C++ 6.0 would inline the call. This was compiled using the default release mode optimizer option to Maximize speed.

In order to verify that the inlining of the calls was making a difference, I modified the test program which sorted a vector of ints to test using a version with an external operator() (which can't be inlined) against a version which can be inlined.

When I ran this test on my machine, I got the following output:

std::sort using functor: 470 ticks
std::sort using functor without inline: 1042 ticks
std::sort using function: 1011 ticks

I think that this shows that Scott Meyers' claims about inlining improving the performance of the sort to be true.

This is the test program that I used:

extern.h
class SomeClass
{
public:
int fld1;
};

struct SortFldExtern
{
bool operator() (const SomeClass& first, const SomeClass& second);
};



extern.cpp
#include "extern.h"

bool SortFldExtern ::operator() (const SomeClass& first, const SomeClass& second)
{
return first.fld1 < second.fld1;
}


main.cpp
#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <string>
#include "extern.h"

using namespace std;


typedef vector<SomeClass> intvec;


void randomize_vector(intvec& v)
{
srand(time(0));
for (intvec::iterator i = v.begin(); i != v.end(); ++i)
(*i).fld1 = rand();
}


struct SortFld
{
bool operator() (const SomeClass& first, const SomeClass& second)
{
return first.fld1 < second.fld1;
}
};


inline bool stllessfunc(const SomeClass& lhs, const SomeClass& rhs)
{
return lhs.fld1 < rhs.fld1;
}


int main()
{
intvec v(1000000);

randomize_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;

randomize_vector(v);

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

randomize_vector(v);

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

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