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
Printable View
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
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.
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?Quote:
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.
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!Quote:
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.
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
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.Quote:
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!
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
Quote:
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
No. Your latest Qsort() also failed on the structure givenQuote:
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!
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.
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.
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.
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 )Quote:
There is NO difference mathematically between Qsort(), qsort() or std::sort(), they all use the same mathematic algorithm underneath.
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