more sorting

[Philip Nicoletti]

Attached is a zip archive containing a few test
cases for sorting. Included in the archive is
a file : sorting.txt , which contains a brief
description of the test cases and some timing
results.

Comments and criticisms are welcome.

I can provide a ".tar.gz" file if anyone prefers.

[Paul McKenzie]

As for your errors:

Depending on how the implementation of virtual base classes is done, this can lead to failures when these objects are not copied properly (which is what qsort / QSort does). Possibly GNU and PG use the same or similar technology in implementing these types of classes. Regarless of the reason for failure, everyone stated that the behavior of copying non-POD objects without invoking a proper copy constructor is undefined behavior. std::sort stood out without any problems, no matter which compiler it was run on. The emphasis should be why std::sort works and q/QSort doesn't (again the virtual bae classes looks like the deciding factor). If qsort didn't work and the reason was the kernel was messing up the code somehow, then other non-sort related, sound valid ANSI specification code would also fail that does a few memcpys().

I would change the class type to non-virtual base classes and re-run. If you don't get the errors, then this shows that virtual base classes in PG and g++ cannot be moved around without invoking the correct copy constructors.

Regards,

Paul McKenzie

[AnthonyMai]

Philips:

I downloaded your files, and compiled the error.cpp, which is supposed to give an error, on VC++, it works just fine, without a single line of modification.

I am posting the source code, the compiler output and the executable all in one package to show it indeed works on VC++.

If you claim it doesn't work on your compiler, you have to put your compiler output to prove it, not just the soucre file. The source file works just fine on my compilers.

[AnthonyMai]

Oops, forgot the attachment in last post.

[Philip Nicoletti]

Anthony,

If you had read the text in sorting.txt, you
would have noticed I said it did not work
under Red Hat Linux 7.1 (both g++ and
pgCC)

[AnthonyMai]

Philips:

If you read your own code again, you will realize that you did not actually randomize the array (for the double) before sorting. The array is actually already in order, So when doing std::sort it really doesn't do any thing. Meanwhile I identifies there is a bug in the Qsort code that it would swap two elements un-necessarily some times even when it is not necessary.

If you REALLY randomize the array, you will see that even for double, even for this buggy version of Qsort, std::sort really is not much faster than Qsort.

I will study and fix the bug in Qsort, then you are going to see Qsort beats std::sort even for doubles.

[Philip Nicoletti]

Concerning the double - they are not in order.
They increase , then decrease. And as I mentioned
in sorting.txt, for most data sets of double std::sort() is
from 1.2 to 1.9 times faster than Qsort().

[jfaust]

then you are going to see Qsort beats std::sort even for doubles.


When operating under less restrictions, such as relying on compiler-dependent behavior and ignoring the standard, I'd expect to be able to make anything faster.

Performance doesn't mean anything if the answer is not correct, and your solution only works on a subset of compilers. It is simply not guaranteed to work on any compiler, any version of the compiler, or any operating system.

Jeff

[Yves M]

Originally posted by AnthonyMai
I will study and fix the bug in Qsort, then you are going to see Qsort beats std::sort even for doubles.

std::sort is twice as fast as Qsort on a vector of doubles I tried. And about 30 times faster than qsort.

My results in milliseconds for 1 million doubles:

std::sort 237.8917
qsort 17659.1570
Qsort 512.8487


P.S. My iostreams are broken and I use a windows-specific timer (written by alexey). Sorry for that ;)