To be human is to fear what's unknow or uncertain. It's not surprising that there is wide-spread fear about memcpy() on a class object, or its effect on v-table on different implementations. Because most people simply do not know what's going on underneath.
There is nothing misterious about v-table. They are merely class data member(s), in the form of function pointers, of the base class where the virtual function(s) is(are) declared. They are part of the base class, just like the rest of class data members, although they are not quite as visible. So, yes, the v-table do gets copied over when you are copying or moving objects.
In doing object sorting, no object creation or destruction should be involved. We are just moving objects around from one memory location to another location.
It is highly likely that by merely shifting an object in the memory would not change the property of the object. The object should look just the same before and after the shift. In such case it is perfectly OK to just memcpy to swap objects or move them to a different location.
If in the rare case, the object's property DO depend on its memory location. Then such objects can not be copied, and no proper copy constructor can be written. Because you would have to copy the object into exactly the same memory location to make it look and behave exactly the same!!!
In such rare cases, qsort() would not work properly, but neither std::sort() would work. Since std::sort() requires an appropriate copy constructor, but I already said no proper copy constructor can be written since once the object is copied to a different location, it no longer behave the same even every thing else is the same!!!
Paul McKenzie
July 24th, 2002, 05:14 AM
There is nothing misterious about v-table. They are merely class data member(s), in the form of function pointers, of the base class where the virtual function(s) is(are) declared. They are part of the base class, just like the rest of class data members, although they are not quite as visible. So, yes, the v-table do gets copied over when you are copying or moving objects.There is nothing in the ANSI ISO Standard that says virtual functions are implemented this way. Given just that, the rest of what you say is moot.
Since myself and others have tried to relay to you that looking at underlying code is not how to determine the rules of ANSI C++, I will post your above claim about memcpy() and qsort() to comp.lang.c++ and comp.lang.c++.moderated newsgroup and post the responses to it here. If not for your knowledge, then for others to read.
For those who have access to these newsgroups, the thread is titled:
"memcpy() on objects is safe??"
Regards,
Paul McKenzie
Paul McKenzie
July 24th, 2002, 05:22 AM
Well. here is one response already.
----------------------------------------------
> I have someone on another forum who has made the following claim about
> objects and usage of memcpy(), more importantly, usage of qsort() on
> objects.
> Here is the claim:
> ------------ CUT HERE -------------------------
> In doing object sorting, no object creation or destruction should be
> involved. We are just moving objects around from one memory location to
> another location.
>
> It is highly likely that by merely shifting an object in the memory
> would not change the property of the object. The object should look just
> the same before and after the shift. In such case it is perfectly OK to
> just memcpy to swap objects or move them to a different location.
>
Wrong.
Standard says:
"For any object (other than a base-class subobject) of POD
type T, whether or not the object holds a valid value of type T,
the underlying bytes (1.7) making up the object can be copied
into an array of char or unsigned char.
If the content of the array of char or unsigned char is copied
back into the object, the object shall subsequently hold its
original value." (3.9/2)
There are defect reports on this wording, particulary regarding
PODs with non-static "const" members (proposed resolution is to
remove the above guarantee from such PODs), but the intent
remains the same:
Standard does not give such guarantees for non-POD types.
Furthermore, Standard says:
"An object of POD type shall occupy contiguous bytes
of storage" (1.8/5)
There is no such guarantee for non-POD types.
And the last (but not the least): Standard says:
"A pointer to a POD-struct objects, suitably converted using
a reinterpret_cast, points to its initial member (or if that member is
a bit-field, then to the unit in which it resides) and vice versa.
[Note: there might therefore be unnamed padding within a POD-struct
object, but not at its beginning, as necessary to achieve appropriate
allignment.]" (9.2/17)
There is no such requirement for non-PODs.
> If in the rare case, the object's property DO depend on its memory
> location. Then such objects can not be copied, and no proper copy
> constructor can be written.
Wrong.
Consider so-called "base-pointers", like this one
(everything is snipped, but I hope that idea is clear):
Such "pointers" are helpful when doing some low-level tricks,
and they can be easily made "Assignable", "Comparable" etc.
Note that they _do_ have proper and correct copy constructor's
and assignment operator's semantics.
If you implement based pointers (or any other such classes)
properly, you can use them in containers, perform
std::sort or any other algorithms etc etc
(Indeed, offset_to_pointer<T> and pointer_to_offset cannot
be written portably, they are implementation/platform-specific
operations, and there might be platforms where these operations
is impossible to implement. But this is other issue.)
> Because you would have to copy the object
> into exactly the same memory location to make it look and behave exactly
> the same!!!
>
Nonsense.
> In such rare cases, qsort() would not work properly, but neither
> std::sort() would work.
Wrong.
std::sort() will work correctly with containers of the above pointers,
while qsort() will indeed corrupt everything.
> Since std::sort() requires an appropriate copy
> constructor, but I already said no proper copy constructor can be
> written since once the object is copied to a different location, it no
> longer behave the same even every thing else is the same!!!
Wrong.
> --------------- CUT HERE --------------------------------------
>
> Excusing the typos, can anyone here comment on the above? This all
> started with an argument over whether qsort() is safe to use on all
> objects, as opposed to always using std::sort().
>
qsort() is unsafe, it knows nothing of C++ objects, and it can be used
only with PODs without non-static const members.
memcpy() is unsafe, it knows nothing of C++ objects, and it can be used
only with PODs without non-static const members.
std::sort() is safe to use, as long as all C++ standard library requirements
are met.
Hope it make things clearer,
Sincerely,
Ruslan Abdikeev
Brainbench MVP for Visual C++
http://www.brainbench.com
------------------------------------------------------------------------
Regards,
Paul McKenzie
Elrond
July 24th, 2002, 05:36 AM
What does "POD" stand for?
Paul McKenzie
July 24th, 2002, 05:41 AM
POD --> Plain Old Data.
Examples are char, int, long, double, float.
Regards,
Paul McKenzie
Elrond
July 24th, 2002, 05:48 AM
Thanks, I'd never seen that before (but as non english,...)
AnthonyMai
July 24th, 2002, 10:12 AM
Let's first clarify the POD (Plain Old Data) and none-POD myth.
First there is no distinction between "POD" and "none-POD". For any complicated class you can think about, they can be boiled down to base classes, "none-POD" data object members and POD data members. And each of the base class or "none-POD" member can be further taken apart into smaller components. Continue this process down, eventually every thing is composed of just POD data members.
All classes can be boiled down to just POD data members and nothing else
We have already seen that qsort() works on array of classes with std::string or std::vector and other class members. Is such class POD or none-POD?
I made the assertion that if an object's state or property depends on its own memory location, then such object can not be properly copied. Some one cited the base_pointer example. Unfortunately this example exactly shows why such object can not be copied. You think your copy constructor works. But it doesn't!
Let's say your class contains a direct pointer pointing to the n'th char of a char array within the class. And there is a function call to get that pointer. The caller can use that pointer to do some low level data manipulation efficiently. And when you copy objects of this class around, you adjust that pointer so it still points to the correct char in the char array of the new object. Does it seem to be OK?
It's NOT OK. Let's say a piece of code calls to get that pointer, and decides to store the pointer for later usage. And let's say the class object is the first object stored in a vector. And now you push one more object into the vector, and it finds it needs to do a memory reallocation to be able to contain more objects, and so all objects are "properly" copied to their new location. Every thing works so far. But when the code who stored the previous pointer comes back to manipulate the data of the first object. Bom! Access violation! The first object of the vector was copied from the original first object of the vector. But unfortunately the location is changed so the old pointer no longer works.
What does that tell you? It tells you what I already told you. If an object's property or behavior depends on its own location in any way at all, such object simply can not be copied over. No copy constructor can be written for such animal.
Back to v-table, granted the standard doesn't say any thing how it should be implemented. But v-table is part of the property of a class object, right? Each instance of the class object will have its OWN copy of the v-table. And I do not see any practical and sensible way of implementing it, other than put the v-table together with the rest of class members to form a chunk of continuous memory block which is the class object. Try to do a sizeof() of the class, you will see that it counts in the size of the v-table, in addition to all other none-static and none-cost data members.
Now when it comes to none-static const class members. Its implementation is not specified. It could be implemented in one of three ways. 1.No storage is allocated for it and it is used directly where ever it is referenced. 2.Implemented like a const static member. 3.Implement just like a regular data member but modification of this value is prohibited.
When copying object using memcpy(), in the above case 1 or 2, it will not be copied, nor will it needs to, so it is not an issue.
In the above case 3.We are some how violating the definition of const by writting a value over a const variable. In principle we could be doomed if the const value is allocated in a write-protected memory location. In practice, the only sensible way of implementation would be allocate regular memory for the variable, together with the rest of class members. There simply is no feasible way to put this variable away in a different memory location. Remember we are talking about case 3, where each instance of the class has a separate copy of the const data member.
In summary, the widespread fear of applying qsort() on none-POD object arrays is un-warranted. I am not saying it always works. As I pointed out already, for objects which depends on its own location, qsort() would not work, But neither std::sort in such case.
Paul McKenzie
July 24th, 2002, 10:51 AM
Again, standard says nothing about what you stated. The ANSI standard talks about language rules, not low-level details. If it were the case then why doesn't it include all the cases of implementation that you mentioned? There isn't even a suggestion of how something is implemented low-level. POD and non-POD type is a myth? Now the ANSI standard is wrong?
The ANSI ISO standard is over 700 pages, you would think they would have room for your speculative ideas on how something is implemented, but they didn't.
It's amazing how to you every single C++ expert that can be named is wrong, every one from the inventor of the language (Stroustrup) to the chair of the ANSI C++ standardization committee, to even the ANSI standard itself. I'd stick to what the experts in the language have to say (and hopefully others will to).
I posted your follow-up. I would suggest you take at least a peek there.
Regards,
Paul McKenzie
AnthonyMai
July 24th, 2002, 11:05 AM
Paul:
Do you accept the fact that there exists none-copyable classes. Do you agree that such animal exists at all? Do you agree that it is impossible to write copy constructor for such classes and hence std::sort() would not work?
Zeeshan
July 24th, 2002, 11:17 AM
Who said vtable must be implemented in the form of continous memory, it can be implemented in the form of link list. Because Standard doesnt say anything about this. Why not you at least take a look at C++ Standard to clear lots of your problems.
Paul McKenzie
July 24th, 2002, 11:26 AM
Originally posted by Zeeshan
Who said vtable must be implemented in the form of continous memory, it can be implemented in the form of link list. Because Standard doesnt say anything about this. Why not you at least take a look at C++ Standard to clear lots of your problems. Zeeshan, why fork over $18 US for a document that's wrong ;)
Regards,
Paul McKenzie
AnthonyMai
July 24th, 2002, 12:53 PM
For objects that compiler knows at compiler time, a plain function pointer array of N elements (N be the count of virtual functions) as class member will be the simplest implementation of the v-table. Because the compiler just knows for each virtual function call, which (1st, 2nd or 3rd) function pointer out of the v-table it should use. It's all resolved at compiler time.
For objects that is unknown to application at compiler time, for example COM objects, the implementation v-table is more complicated. However in this case we are talking about objects that the application simply doesn't know. All it knows is the interface. The underneath object is hidden from application. Hence it is impossible for the application to copy, move, store or sort such objects. Such objects are simply inaccessible to application except for its interface(s), So it is out of the topic of this discussion.
Zeeshan
July 24th, 2002, 01:06 PM
Hmm, now plan to start discussion on COM.
for example COM objects, the implementation v-table is more complicated
I think i have little bit knowleldge of this and wrote couple of articals on codeguru and codeproject. In which i discuss the memory layout and virtual function in detail. Take a look at that.
ATL Under the Hood Part 1
http://www.codeguru.com/atl/ATL_UnderTheHood_1.html
ATL Under the Hook Part 2
http://www.codeguru.com/atl/ATL_UndertheHood_2.html
Paul McKenzie
July 24th, 2002, 01:33 PM
I will post two more replies, and that's it. Other CodeGuru participants can check the thread on comp.lang.c++, but I'll give them a taste of what to expect:
> Let's first clarify the POD (Plain Old Data) and none-POD myth.
>
> First there is no distinction between "POD" and "none-POD". For any
> complicated class you can think about, they can be boiled down to base
> classes, "none-POD" data object members and POD data members. And each
> of the base class or "none-POD" member can be further taken apart into
> smaller components. Continue this process down, eventually every thing
> is composed of just POD data members.
>
> All classes can be boiled down to just POD data members and nothing else
>
First, let's speak one language.
Standard clearly specifies what is a POD:
"A POD-struct is an aggregate class that has no non-static data
members of type pointer to member, non-POD-struct, non-POD-union
(or array of such types) or reference, and has no user-defined copy
assignment operator and no user-defined destructor." (9/4)
Standard clearly specifies what is an aggregate:
"An aggregate is an array of a class with no user-declared constructors,
no private or protected non-static data members, no base classes, and
no virtual functions." (8.5.1/1)
There are defect reports on these definitions regarding PODs with
user-defined "address-of" operators, non-static "const" members etc,
but the intent is clear.
Second, _nothing_ is guaranteed about memory layout of non-POD objects.
It is _not_ guaranteed that it is contiguous.
It is _not_ guaranteed that address of object is the address of its initial element.
It is _not_ guaranteed that there are not traps inside.
Third, I want my copy assignment operators and copy constructors
work as intended.
Not blindly copied.
I want members of my class assigned and copied as it were intended
by their authors.
Not blindly copied.
The fourth.
Please take a courage to compile and run the following snippet
(IIRC it was posted by Francis Glassborow or James Kanze):
#include <iostream>
struct A { char ia; };
struct B : virtual A { char ib; };
struct C : virtual A { char ic; };
struct D : B, C { char id; };
complete object B:
sizeof(b) = 9
&ia-&ib = 4
B subobject of D:
sizeof(b) = 9
&ia-&ib = 16
I think it would say you a lot about contiguous objects and sizeof.
And the fifth.
When Standard says "it is an undefined behaviour",
it is an undefined behaviour.
End of the statement.
> We have already seen that qsort() works on array of classes with
> std::string or std::vector and other class members.
>
What you have seen was an undefined behaviour.
An undefined behaviour works exactly in this way:
you _might_ see something you expected to see.
However, undefined behaviour _might_ also cause formatting
of your harddrive (please use Google to find out all the
possible consequences of undefined behaviour posted here
on comp.lang.c++ either by John Harrison or Neil Butterworth, iirc).
> Is such class POD or none-POD?
Such class might be an aggregate, but it is certainly non-POD.
>
> I made the assertion that if an object's state or property depends on
> its own memory location, then such object can not be properly copied.
> Some one cited the base_pointer example. Unfortunately this example
> exactly shows why such object can not be copied. You think your copy
> constructor works. But it doesn't!
Thank you for your inspiration.
Unfortunately, it does work.
Would you be so kind to elaborate?
Indeed, code I posted was not intended to compile.
If you are interested I can post a real code.
Nobody is assured against mistakes, but I don't think this is the case.
The only thing about based_ptr is that it uses non-standard and non-portable
functions offset_to_pointer<> and pointer_to_offset.
But it isn't related to the topic.
>
> Let's say your class contains a direct pointer pointing to the n'th char
> of a char array within the class. And there is a function call to get
> that pointer. The caller can use that pointer to do some low level data
> manipulation efficiently. And when you copy objects of this class
> around, you adjust that pointer so it still points to the correct char
> in the char array of the new object. Does it seem to be OK?
Yes, it is strange design, but it works:
#include <iostream>
#include <vector>
struct foo
{
char c[10];
char* p;
static const int N= 2;
// enum { N= 2 };
// just in case your compiler doesn't accept const int
// Function get_pointer() is intended to allow clients of class
// to perform low-level data manipulations efficiently.
// The pointer returned may be invalidated by the following uses
// of foo object:
// - calling non-const member functions, including copy assignment operator
char* get_pointer() const { return p; }
};
> Let's say a piece of code calls to get that pointer, and
> decides to store the pointer for later usage.
Ok.
> And let's say the class object is the first object stored in a vector.
> And now you push one more
> object into the vector, and it finds it needs to do a memory
> reallocation to be able to contain more objects, and so all objects are
> "properly" copied to their new location.
> Every thing works so far.
Agree.
> But when the code who stored the previous
> pointer comes back to manipulate
> the data of the first object.
> Bom! Access violation!
Nope.
First, it isn't an access violation, it is an undefined behaviour.
Second, if user is stupid and/or never reads documentation,
everything might happen even with std::vector<int>.
Even with std::string.
You can protect stupid user from himself by removing
dangerous get_pointer().
"References, pointers, and iterators referring to the elements
of a basic_string sequence may be invalidated by the following
uses of that basic_string object:
- [...] As an argument to basic_string::swap()." (21.3/5)
So the user _is_ warned about consequences.
Writing such a code the _user_ (not you, and not library vendors)
gets all the responsibility.
This is the first part of the response. To be continued...
Regards,
Paul McKenzie
Paul McKenzie
July 24th, 2002, 01:35 PM
Here is the second part of the response:
> The first object of
> the vector was copied from the original first object of the vector. But
> unfortunately the location is changed so the old pointer no longer works.
>
Ouch.
We do NOT speak about stupid users, do we?
We speak about poor little users of non-POD aggregates.
They call your function (which in turn calls memcpy and qsort)
and see their data corrupted, boomed and access violationed.
> What does that tell you? It tells you what I already told you.
Nope. It tells me that a stupid user is a stupid user.
It tells me that get_pointer function needs to be
carefully documented.
Also it tells me that it is a bad design idea to give such
function to the user.
Note that everything is fine with
std::vector<foo>
from the sample you gave.
> If an
> object's property or behavior depends on its own location in any way at
> all, such object simply can not be copied over. No copy constructor can
> be written for such animal.
Take a look to based_ptr from my previous post, or to the foo definition above.
They both _are_ such animals.
They both _do_ work.
>
> Back to v-table, granted the standard doesn't say any thing how it
> should be implemented. But v-table is part of the property of a class
> object, right?
Neither v-tables nor implementation of virtual function calls
nor implementation of virtual inheritance is described by Standard.
All these things are implementation defined.
> Each instance of the class object will have its OWN copy
> of the v-table.
Wrong.
All implementations using v-tables I've seen so far
placed a _pointer_ to v-table into the instance.
> And I do not see any practical and sensible way of
> implementing it, other than put the v-table together with the rest of
> class members to form a chunk of continuous memory block which is the
> class object.
See above.
> Try to do a sizeof() of the class, you will see that it
> counts in the size of the v-table, in addition to all other none-static
> and none-cost data members.
See above.
>
> Now when it comes to none-static const class members.
> Its implementation is not specified.
> It could be implemented in one of three ways. 1.No
> storage is allocated for it and it is used directly where ever it is
> referenced. 2.Implemented like a const static member. 3.Implement just
> like a regular data member but modification of this value is prohibited.
First of all, I shall admit that you are still speaking about PODs.
>
> When copying object using memcpy(), in the above case 1 or 2, it will
> not be copied, nor will it needs to, so it is not an issue.
>
> In the above case 3.We are some how violating the definition of const by
> writting a value over a const variable. In principle we could be doomed
> if the const value is allocated in a write-protected memory location. In
> practice, the only sensible way of implementation would be allocate
> regular memory for the variable, together with the rest of class
> members. There simply is no feasible way to put this variable away in a
> different memory location. Remember we are talking about case 3, where
> each instance of the class has a separate copy of the const data member.
On a constness, C standard says:
"If an attempt is made to modify an object defined with a const-qualified
type through use of an lvalue with non-const-qualified type,
the behaviour is undefined." (C Standard, 6.7.3/5)
C Standard Rationale (WG14/N897 J11/99-032) says:
"const is specified in such a way that an implementation is at liberty to
put const objects in read-only storage [...]" (p67 line 18)
>
> In summary, the widespread fear of applying qsort() on none-POD object
> arrays is un-warranted. I am not saying it always works. As I pointed
> out already, for objects which depends on its own location, qsort()
> would not work, But neither std::sort in such case.
Please look on based_ptr and the above foo example.
Please read the long thread about C++ objects here
(if URL is split, just merge it)
or search a Google on "virtual inheritance contiguous sizeof".
Hope at least this would make things a little bit clearer,
Sincerely,
Ruslan Abdikeev
Brainbench MVP for Visual C++
http://www.brainbench.com
Regards,
Paul McKenzie
Paul McKenzie
July 24th, 2002, 01:39 PM
This last response (sorry, the last one I'll post -- if you want to see more, go to the newsgroups I've mentioned). This is from someone else called StarDust:
I'd mention a few things: first, I think it's good to write code that works (as
compared to may work). Second, type safety: with qsort you can errorneously supply
any function taking 2 void* and the compiler won't stop you - results are, as they
say, "undefined". That is not the case with the stl sort, here the compiler will pick
the error. A general heuristic: whenever you see conversions to/from void* you know
you better avoid it.
Third, efficiency: stl sort *generates code* - specifically for your data type,
whereas qsort will rely on a run-time equivalent based on user-supplied type
conversions, which means more indirections (in addition to the possibility of
compiler-uncatcheable type errors).
Copying memory as a method of copying objects (non-PODs) is, I'd say, beyond the pale
w/o even worrying of what can possibly go wrong. There's nothing we know about
internal composition of objects, so that's enough to deem this method in general
verboten.
The guy should learn C++, that's my view of it, since what's at issue here is not
that something *may* work *sometimes*, but that this very thing *may not* work, and
therefore such coding habits should be eliminated. The coder's intent should be to
write code that's 100% guaranteed to work. There'll be enough bugs even with that
assumption, but at least you will have a frame of reference and thus narrow the field
of search for the source of your problems.
That's it for the back-and-forth folks. If Anthony wants to respond to Ruslan or StarDust, he knows how to do so.
Regards,
Paul McKenzie
AnthonyMai
July 24th, 2002, 02:20 PM
There's nothing we know about internal composition of objects, so that's enough to deem this method in general verboten.
Hmm? You write your own class and you know nothing about its internal composition?
Copying memory as a method of copying objects (non-PODs) is, I'd say, beyond the pale w/o even worrying of what can possibly go wrong
Haven't I made it clear that I am in no way promoting memory copying as a general method of copying objects. I made it clear that you can use memory copying in the context of moving object in memory or swapping, without creating new ones or deleting existing ones, as in the case of sorting Such usage is safe under the restrictions I listed (i.e., the object's property does not depend on its own location). When the restriction is broken, then the objects are not copyable at all.
The coder's intent should be to
write code that's 100% guaranteed to work.
There is no such thing that an application 100% guarantees to work properly. And from my experience, the only thing that is virtually bug-free, are the code that was written in assembly. The reason is simple: You know ever thing that's going on and there is no place for the bug to hide should you make a mistake.
It is a general rule that low level stuff written in low level programming language tends to be more error free and robust. You pick up a telephone and you can always make a phone call. You turn on a DVD player and it always play the video. You hit the break of your car and it always respond. The piece of assebly code that does the voice compression/decompression in your telephone, the piece of codec that processes the digital video data always works in your DVD player. And the software in the micro-chip that controls your anti-lock break works just frawlessly.
On the other hand the higher level you go up, the more likely there are bugs. You don't know how the compiler will interpret your STL code, and you have no control. The higher level you go, the more unknown and uncertain there will be, and the less control you have, and the more bugs you will produce.
Paul McKenzie
July 24th, 2002, 02:36 PM
StarDust isn't a member of this forum or CodeGuru (AFAIK).
I'll post your response to the comp.lang.c++ newsgroup, since you are not willing to do so. If there is a response, I will not post it here. If you are sure of yourself, you should go there and respond to these fellows.
Again for anyone who is interested, comp.lang.c++, the title of the thread is "memcpy() on objects is safe??".
Regards,
Paul McKenzie
jfaust
July 24th, 2002, 02:40 PM
I can't believe you are still arguing. It was amusing at first, but now it's just getting painful. I almost feel sorry for you. As much as anyone can ever be proven wrong, you've been proven wrong. Yet, you persist.
And the nonsense about less bugs in low-level languages is just that--nonsense. But this has very little to do with the OP.
Jeff
AnthonyMai
July 24th, 2002, 03:49 PM
I am proven wrong what? I have explained my reasoning, provided sample code. I don't see any of them getting reputed.
Can any one cite even just one example where the object can be copied properly, yet applying qsort on the object array will fail?
Talking about writting correct code, it is MORE likely that you will have a bug in using std::sort() than in the case where you use qsort(). The later will fail if the object is impossible to copy, in which case std::sort() will not work either. And this is a rarely occuring situation.
While as in using std::sort(), if you fail to provide a proper copy constructor or assignment operator where a none-default one is needed, you are doomed.
It is a very likely scenary. Why would you need (bother) to write a copy constructor or assignment operator, if in your own code that you write you are NOT doing any object copying or assigning at all?
Some one tried to prove me wrong by sealing my mouth on this board. That doesn't seem to work. You can not get me to the comp.lang.c++ newsgroup any more than you can get me out of this board. When I am tired here I will leave codeguru. When I am interested I will go visit comp.lang.c++. No one can tell me where to go and where not to go. Meanwhile I am still taking pride of the quality of code that I write.
jfaust
July 24th, 2002, 04:10 PM
Your original post was wrong on several accounts--in more ways than I knew. Ruslan Abdikeev pointed these out, described how you were wrong, and then quoted from the standard to back up his claim.
It all boils down to the fact that, according to the standard, you are relying on undefined behavior. I see two choices: 1 -- you think the standard is wrong, or 2 -- it's perfectly OK to rely on undefined behavior. If there's another, please enlighten me.
Jeff
AnthonyMai
July 24th, 2002, 07:35 PM
It all boils down to the fact that, according to the standard, you are relying on undefined behavior. I see two choices: 1 -- you think the standard is wrong, or 2 -- it's perfectly OK to rely on undefined behavior. If there's another, please enlighten me.
I agree with first sentence, I disagree with second sentence.
I am using something undefined behavior as far as C++ standard is concerned. Undefined means that the C++ did NOT say any thing about it. It neither said it is right nor said it is wrong. Blank, nothing, null, no comment, nothing was said, zarda.
So whatever I do, it is on separate path from the C++ standard. It does not cross and there is no conflict. OK?
So your first choice is wrong. I do not think the C++ standard is wrong. Nor do I think a standard is right. There is no right or wrong in a standard. For example the standard US paper size is 8.5 inch x 11 inch. Is 8.5x11 right? Or is it wrong? If I use 8 inch x12 inch paper, am I right or wrong?
Standard is not the whole world. It is just by chance and by a lot of consideration that we come to the standard of 8.5x11 paper size. If C++ development has take a slightly different path or the original author has a slightly different philosophy, the C++ standard may be different from what we see today.
Again there is no right or wrong in a standard. The only thing that can be said is whether a C++ standard is good or bad. Or whether the standard is self consistent or not, or whether a piece of code complies with a standard or not.
You can't say a piece of none-compliant code is right or wrong, any more than you can say the standard is right or wrong. Maybe you can say it is good or bad. But good or bad is opinion oriented. Really the only thing that can say whether a piece of code is right or wrong, is whether it can compile and run to produce the desired result.
No. 2. "2 -- it's perfectly OK to rely on undefined behavior"
Undefined in C++ STL standard does not mean it is undefined and comes out totally from the wild. How v-table is implemented is undefined in C++, but it is defined some where else. And it is totally valid to treat the v-table as part of the class members and do memcpy() on them.
Once again my code works, and Philips et al have helped me to verify that it works at least on a number of different platforms. That says enough whether my code is right or wrong.
Paul McKenzie
July 24th, 2002, 07:54 PM
Once again my code works, and Philips et al have helped me to verify that it works at least on a number of different platforms. That says enough whether my code is right or wrong.Totally irrelevant. If it says in the standard that the behavior is undefined, then it is undefined. Whether you want to say it or not, you are recommending using undefined behavior as per the ANSI/ISO C++ specification.
As far as you stating that "there is no right or wrong in a standard" -- no comment.
Regards,
Paul McKenzie
Zeeshan
July 25th, 2002, 12:23 AM
Hmm? You write your own class and you know nothing about its internal composition?
Yes you dont know, because it is not define in standard. You should not write the portable code which based on memory structur of class. If it works on one compiler (or plateform) then it doesnt mean it ll run on other plateform (or compiler).
e.g. take a look at this program which i took from my artical "ATL Under the Hood Part 1" Program 15.
class Drive : public Base1, public Base2, public Base3 {
virtual void fd() { cout << "Drive::fd" << endl; }
virtual void gd() { cout << "Drive::gd" << endl; }
};
typedef void(*Fun)(void);
int main() {
Drive objDrive;
Fun pFun = NULL;
// calling 1st virtual function of Base1
pFun = (Fun)*((int*)*(int*)((int*)&objDrive+0)+0);
pFun();
// calling 2nd virtual function of Base1
pFun = (Fun)*((int*)*(int*)((int*)&objDrive+0)+1);
pFun();
// calling 1st virtual function of Base2
pFun = (Fun)*((int*)*(int*)((int*)&objDrive+1)+0);
pFun();
// calling 2nd virtual function of Base2
pFun = (Fun)*((int*)*(int*)((int*)&objDrive+1)+1);
pFun();
// calling 1st virtual function of Base3
pFun = (Fun)*((int*)*(int*)((int*)&objDrive+2)+0);
pFun();
// calling 2nd virtual function of Base3
pFun = (Fun)*((int*)*(int*)((int*)&objDrive+2)+1);
pFun();
// calling 1st virtual function of Drive
pFun = (Fun)*((int*)*(int*)((int*)&objDrive+0)+2);
pFun();
// calling 2nd virtual function of Drive
pFun = (Fun)*((int*)*(int*)((int*)&objDrive+0)+3);
pFun();
return 0;
}
This code works fine on VC 6 but crash on Rat Hat Linux 7.0 with gcc 2.96.
Graham
July 25th, 2002, 03:41 AM
Originally posted by AnthonyMai
Why would you need (bother) to write a copy constructor or assignment operator, if in your own code that you write you are NOT doing any object copying or assigning at all?
Because I always consider the copy constructor and copy assignment functions when designing a class:
1) Is copying appropriate? If not, disable copy ctor and copy assign.
2 ) If copying is appropriate, are the compiler-generated functions sufficient? If not, write my own.
3) Is default construction appropriate? Write/disable default ctor as necessary.
4) Is the compiler-generated dtor sufficient? If not, write one.
5) Is the compiler-generated address-of operator sufficient? Almost certainly, but if not, take appropriate action.
AnthonyMai
July 25th, 2002, 08:24 AM
Zeeshan:
If what you quoted is indeed from the article you put on CODEGURU, you need to withdraw it right now. Because it is embarrassing to hang it there to show you do not know what you think you know.
What's the difference between a global function and a none-static class member function?
Can you call a none-static class member function the same way you call global function?
Can you call a none-static class member function WITHOUT a class object?
Why?
Hint: there is a hidden parameter "this" when you call a none-static class member function. You know what it is? How it is passed? What will happen if you don't have it?
You are lucky to have it work on VC6 because in your virtual function you are not touching any class data member.
Now back to portability. There CAN be different ways of v-table implementation. There will be a problem when you assume the v-table is located at the beginning of the memory chunk where class data members are allocated. It could well be any where within the memory chunk.
But I made a reasonable, and sensible assumption that no matter how v-table is implemented, it would have to be put into the same chunk of memory where all other class data members sit, not counting the few bytes gap intentionally un-used to make class data members properly byte aligned.
There is just no reasonable way to put data pertaining to a class's state into two different chunks of memory. And I have not seen any implementation does it in such un-thinkable way.
So, unless you can cite one platform on which my assumption is wrong, it is still correct even not spelled out in the C++ standard.
AT least the C++ standard does not say I am wrong. It simple does not say any thing in this regard.
AnthonyMai
July 25th, 2002, 08:40 AM
Why would you need (bother) to write a copy constructor or assignment operator, if in your own code that you write you are NOT doing any object copying or assigning at all?
Graham said:
Because I always consider the copy constructor and copy assignment functions when designing a class:
1) Is copying appropriate? If not, disable copy ctor and copy assign.
2 ) If copying is appropriate, are the compiler-generated functions sufficient? If not, write my own.
3) Is default construction appropriate? Write/disable default ctor as necessary.
4) Is the compiler-generated dtor sufficient? If not, write one.
5) Is the compiler-generated address-of operator sufficient? Almost certainly, but if not, take appropriate action.
Graham:
The point is not whether you should write your own copy constructor and copy assignment function. Given any scenary, you ask any one, they will tell you the answer correctly.
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?
Philip Nicoletti
July 25th, 2002, 09:48 AM
I don't know much about v-tables, but I took the structs
that was given in response to Paul's post, tried to sort
it using qsort() and std::sort().
On VC++ ... no problems
on Portland Group compiler (pgCC) ... a problem. Not only did
qsort() not sort the data, but it mangled the data in the
structure. std::sort() had no problems.
Maybe I am doing something wrong ? Here is the code and
the output ...
sorted data using qsort
70 70 70 70
75 65 65 65
65 75 75 75
test using std::sort() ...
original data
70 70 70 70
75 75 75 75
65 65 65 65
sorted data using std::sort
65 65 65 65
70 70 70 70
75 75 75 75
<08 [9:30am] /raid >
jfaust
July 25th, 2002, 09:49 AM
"Once again my code works, and Philips et al have helped me to verify that it works at least on a number of different platforms. That says enough whether my code is right or wrong."
I'd hate to be the poor developer 10 years down the road who has to wade through your stinking pile of "code". Because it works now, and addresses an immediate problem now does not make it valid in years to come. There will be new platforms and new compilers.
The product I work on has a good deal of history, and so has had its share of "misguided" developers. We've spent a lot of effort cleaning up the garbage. Thier names are remembered, although no fondly.
The issue is not wether your code works or not. From a maintenance standpoint, your code is simply wrong. Since maintenance is the largest cost of software development, this is a very serious issue.
You would not be allowed to write this garbage at my company, or at any company with a project manager worth anything. There's no chance your Qsort would stand up to any code review. Its garbage. Relying on undefined behavior is wrong. It feels ridiculous that I even have to argue such a simple point.
Jeff
AnthonyMai
July 25th, 2002, 10:25 AM
Phillips:
I can immediately see two problems in your code, which causes the problem you see on pgCC compiler.
First:
inline int qsortCompare(const void *a , const void *b)
{
D d1 = *(D*)a;
D d2 = *(D*)b;
return ( d1.ia - d2.ia);
}
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;
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.
Graham
July 25th, 2002, 10:25 AM
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.
AnthonyMai
July 25th, 2002, 10:39 AM
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:
#define BUFF_SIZE 4096
#define CUTOFF 8 /* testing shows that this is good value */
using namespace std;
class SomeClass
{
public:
SomeClass();
~SomeClass();
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.
Paul McKenzie
July 25th, 2002, 11:23 AM
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
Philip Nicoletti
July 25th, 2002, 11:27 AM
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;
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
jfaust
July 25th, 2002, 11:34 AM
"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
Paul McKenzie
July 25th, 2002, 12:39 PM
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
Graham
July 25th, 2002, 02:35 PM
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.
Paul McKenzie
July 25th, 2002, 02:42 PM
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
Paul McKenzie
July 25th, 2002, 04:57 PM
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".
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
jfaust
July 25th, 2002, 05:07 PM
Just thought I'd point out a direct quote by Anthony, made earlier in this thread:
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
Paul McKenzie
July 25th, 2002, 05:23 PM
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
AnthonyMai
July 25th, 2002, 06:03 PM
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:
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.
jfaust
July 25th, 2002, 06:09 PM
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
Paul McKenzie
July 25th, 2002, 06:12 PM
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
AnthonyMai
July 25th, 2002, 06:23 PM
Jeff:
OK, so Paul pulled a fast one. A couple of weeks ago when I compare index sorting using qsort(), with dicret object sorting using std::sort(), Paul accused me of "pulling a fast one"
Now I am really talking about direct object sorting using Qsort, and Paul is talking about index sorting using std::sort(). Paul is pulling a fast one this time. Fine with me. We are just getting even.
But still comparing index sorting with direct object sorting is comparing apple with orange.
I know Paul is intelligent and can pull an intelligent one, but we are not competing programmer intelligence here. We are letting Qsort() and std::sort() competing here. Let them both sorting objects directly, OK? In such fair competition, std::sort() is clearly defeated by a large margin.
Don't you agree, at least in principle, sorting is an operating that moves objects around so they line up in certain order? Hence in principle, it should not be necessary to create new object or delete old ones, right?
std::sort simply can not move objects without detroying them and re-create them, repeatedly. This is teleportation: Basically you kill some one right on spot, and then replicate the person in a different city, in order to transport him from one city to another. It just sound weird to me.
jfaust
July 25th, 2002, 06:41 PM
Anthony,
Yes, I agree in principal that to sort something, you should not have to recreate items. You should be able to shuffle things around and that's it. Unfortunately, the C++ standard does not guarantee that this will work. This is an important point, and should not be ignored no matter unintuitive it may be.
Both std::sort and Q(q)sort have drawbacks. With std::sort, you have to choose your containers carefully. You need to be aware of what is happening or it will take a long time to sort.
Likewise, with Q(q)sort, you have to choose your containers carefully. If you choose the wrong container, the program will crash. Additionally, this will likely fail with certain compilers, which is of no fault of the compiler, but a fault with the source code.
It is more likely, at least in my experience, that a collection of objects of non-trivial classes will actually be a collection of pointers to those objects. In such cases, std::sort is faster.
In all cases, it is safer.
Jeff
Paul McKenzie
July 25th, 2002, 06:46 PM
There is still the issue of undefined behavior. As of the last message, the Pacific Group compiler did not sort correctly using qsort(), while std::sort does.
You can't in good faith comment on anything until, at the very least, you investigate why it doesn't work for this compiler. So as long as Phillip can't get it to work, what's the point? Everyone has been trying to tell you this, but you didn't want to listen.
As I pointed out std::sort has worked flawlessly on every compiler tried, and it is guaranteed by the ANSI/ISO standard to work the way it's documented to work. If it doesn't, then it is a bug in the implementation and the compiler vendor is required to fix it, if not the implementation is not ANSI/ISO C++ standard.
There is no guarantee that qsort() works with non-POD types by the ANSI/ISO C++ standard. If qsort doesn't work for a non-POD type, the compiler vendor will tell you to "take a hike" if you tried to report a bug concerning trying to sort a non-POD class with qsort().
Regards,
Paul McKenzie
PaulWendt
July 25th, 2002, 06:53 PM
Here's the problem, Anthony: the creators of std::sort had to instill in it the knowledge of objects [ie: copy constructors]. Why? The reason is that you can't directly copy a class's memory contents wholesale or "bad things" will happen. These people weren't idiots; they would have just used a memcpy() if they could have.
What you guys are arguing about isn't even what sort algorithm is fastest; AnthonyMai is merely stating the obvious: copy constructors can cost you performance if they're used superfluously. Hopefully, most people won't HAVE objects that allocate 4k of memory on the heap; if people DO have these types of objects, then hopefully they'll performance into consideration if they do anything like sorting. The problem's not std::sort; it's the fact that we're using copy constructors. Keep in mind that the "default copy constructor" in C++ [and C if you think about is] is the equivalent of a memcpy().
So ... Paul McKenzie's working with what he's got; he knows that copy constructors are costly ... and he uses the tools available to obtain fast sorting. You're right, Mai; std::sort() is slower than qsort() if copy constructors are costly. Unfortunately, qsort() potentially won't sort things properly. Of course you won't believe it until you see it [and even then I'm sure you'll come up with something]. The point is that McKenzie [and any performance-concious C++ programmer] knows that copy constructors can be a bottleneck if they're used too frequently ... and he can use the language to meet his goals. You don't want to use the language to meet your goals; you want to use what you already know in order meet your goals.
Paul McKenzie
July 25th, 2002, 10:22 PM
I think that maybe the tact of seeing this from the compiler vendor's point of view is the best way to sum this all up
Support: "Hello, Pacific Group C++ tech support. How may we help you".
C++ Coder: "I have a problem with your implementation of std::sort. I sent you an email with the code attached. I'm attempting to sort this class, but std::sort is not working".
Support: "Yes, we saw your e-mail, and according to ANSI C++ specs, it should work. We'll report this to the engineers right away."
C++ Coder: "Thank you"
-------------------------------------------------
Phone Call 2:
Support: "Hello, Pacific Group C++ tech support. How may we help you".
C++ Coder: "I have a problem with your implementation of qsort. I sent you an email with the code attached. I'm attempting to sort this class, but qsort is not working".
Support: "Yes, we saw your e-mail, and according to ANSI C++ specs, the standard library qsort() is not guaranteed to sort these types of classes."
C++ Coder: "Yes, but, it works on VC++..."
Support: "Sorry sir, but qsort is not required to sort these types of classes correctly. If you have a problem with qsort sorting integers, doubles, etc. then we will fix it right away."
C++ Coder: "What do you mean? Are you stupid?"
Support: "Sir, if you have a complaint, I can have other engineers explain that qsort is not guaranteed to work correctly for these classes as the ANSI C++ specification makes no guarantees that qsort work for these classes."
C++ Coder: "What do you mean? I can't believe this! You people there know nothing about...Hello...Hello.."
--------------------------------------------------
So the bottom line is whether the compiler vendor is required to fix qsort if it can't sort a non-POD class for the compiler to be compliant. The answer is an emphatic no.
Is the vendor required to fix a problem with std::sort if it doesn't follow ANSI specs, and remain to have a standard's conforming compiler? Yes.
Regards,
Paul McKenzie
Zeeshan
July 26th, 2002, 12:31 AM
Originally posted by AnthonyMai
you do not know what you think you know.
Ok fine, but i havent said any time "i dont need to read this or that or go here or there and no one has responsiblity to tell me what should i do" . If someone advice me then i surely read that book and go to that side, just like Paul advice me to read one good book of STL.
And now only one program related to your questions of static. Hope it shows what i want to say.
#include <iostream>
using namespace std;
class C
{
public:
static void StaticFun(C* pC)
{
pC->NonStaticFun();
}
int main()
{
C objC;
C::StaticFun(&objC);
return 0;
}
I used this type of techniques lots of time when using threading in VC where the thread function need void pointer and i pass the address of the class and then access other data from that pointer. Of course that thread function is static in my that class, because it hase to be.
Originally posted by AnthonyMai
You are lucky to have it work on VC6 because in your virtual function you are not touching any class data member.
Thats what i want to said, this code runs on VC6 because i explore the memory layout of VC6, but it doesnt mean it runs on other compiler. Why? Because it is not standard, and if it is standard then it should be run on every plateform. And that artical disuss ATL not C++ so i discuss those techniques which ATL use internally.
Originally posted by AnthonyMai
There CAN be different ways of v-table implementation.
Finally you accept this, thats what i want to say, v-table is not standard.
Originally posted by AnthonyMai
no matter how v-table is implemented, it would have to be put into the same chunk of memory where all other class data members sit
Excuse me, v-ptr is exists with class data. (In case of VC and most of other compiler, it is not standard too). v-table is not exists with class data. I think again take a look at Part 1 and Part 2 where i show this with small program on VC.
Originally posted by AnthonyMai
There is just no reasonable way to put data pertaining to a class's state into two different chunks of memory. And I have not seen any implementation does it in such un-thinkable way.
OK, but what about output of this program?
#include <iostream>
using namespace std;
class C
{
char ch1;
int i;
char ch2;
};
I still dont know why you compare algorithm with specification. qsort is algorithm and std::sort is an specification. And if you really want to compare algorithm analysis take a look at
The Art of Computer programming vol 3
by Doneld E Knuth
It seem you consider all
Graham
Paul McKenzie
jfaust
Philip Nicoletti
Ruslan Abdikeev
of them wrong although they give so solid logical reasong. Or may be you want to create the longest thread on codeguru. Ok if all of us are wrong then why not directly mail to your code to Bjarne Stroustrup, scott Meyrs, Herb Sutter, Stan Lippman or Andrew Koenig, Douglas Schmidt, Barbra Moo, Andrei Alexandrescu, Rob Murrey etc.
At least write and artical on CUJ on this, and gain fame.
Hope to here yoo on comp.lang.c++, comp.lang.c++.moderated and CUJ soon.
AnthonyMai
July 26th, 2002, 10:48 AM
Zeehan:
With due respects, I know pragma pack and the concept of byte align long time before I started my first job. You don't need to teach me that. Also, you do need to read my previous post carefully, instead of taking it out of context. I quote it here again:
But I made a reasonable, and sensible assumption that no matter how v-table is implemented, it would have to be put into the same chunk of memory where all other class data members sit, not counting the few bytes gap intentionally un-used to make class data members properly byte aligned.
There is just no reasonable way to put data pertaining to a class's state into two different chunks of memory. And I have not seen any implementation does it in such un-thinkable way.
Didn't I meantion the word "byte aligned"? Those few bytes are intentionally left there and they are un-used. Actually on MIPS based systems, trying to access none-byte-aligned data would cause a system fault.
OK, there is this little detail v-ptr and v-table. v-table is a static table and v-ptr is part of the class data members. v-ptr points to v-table. That doesn't change my argument. v-ptr still sticks to the rest of class data members, as long as v-ptr's are copied together with the rest of data member to a new memory location, it will work just fine.
It seems that all these people
Graham
Paul McKenzie
jfaust
Philip Nicoletti
Ruslan Abdikeev
and you
are trying in vain to proving me wrong by pointing out the obvious: i.e., my use of Qsort() does not agree with the C++ standard so it is wrong.
Such logic is frauded. I gladly accept that my method does NOT comply with the C++ standard. But I fully reject that it is wrong.
A standard, any standard, is neither right nor wrong. 8.5"x11" paper size is an American standard. So is 8.5"x11" right or wrong? Other country may be using a different size, are they right or wrong?
You can say a standard is good or bad. though good or bad is opinion oriented. You can not say a standard is right or wrong. AND YOU CAN NOT SAY A PIECE OF CODE IS RIGHT OR WRONG, BASED ON WHETHER IT COMPLY WITH ANSI C++ STANDARD OR NOT.
Technically ANSI C++ standard is not even an international standard. The A in ANSI stands for American. Practically, though we all agree it is an international standard. But again there is no right or wrong in a standard, however wide that standard is applied.
You are entitled to say your opinion whether a piece of code is good or bad. But you really can't say its right or wrong based on standard compliance. If my code works on a specific platform, then my code is right for that specific platform. If my code does not work on a specific platform, then it is wrong for that platform.
A piece of fully ANSI C++ compliant STL based code would not work on an embedded system, and I can say it is wrong for that platform. My plain C code works, and I can say it is right.
I hope that clears things up. If you guys try to prove that my method is none-ANSI C++ compliant. Save it. I never disagree that it is indeed none-compliant.
If you guys are trying to prove me WRONG, by citing clauses from the ANSI C++ standard or citing what Plaugher said. Save it. The logic simply is fauded. None-compliant does not equal to wrong in logical concept.
I explained my method, explained its philosophy, and posted sample code that every one can test. My code works on a number of different platforms, so it is right, at least for the platforms that I tested.
If you try to prove me wrong by citing that on a specific combination of a small potato compiler and an un-common platform, my code does not work. Also save it. You can tell me whether your STL based code would work on my VCR, on my cell phone, on my GPS navigation system, or on the microwave stove in my kitchen.
Does any STL code work for any of the systems I cited? NO! All those are embedded systems. None of them support STL. Most of them support some sort of stripped down C++ but very few embedded system support STL at all.
I can cite much more systems that doesn't care about STL at all, than you guys can cite systems that are ANSI C++ compliant.
If you really want portability, maintainability, platform independent, stay away from STL, used the minimum denominator part of C++. That's my opinion. And that is also the opinion of a large group of people. Ever heard of the Embedded C++ Standard?
Again, stop wasting time trying to prove me wrong by citing clauses from the writting of the ANSI C++ standard. If you are trying to prove I am not standard compliant, you have made your point already. If you are trying to say none-compliance equals wrong, you are wasting you time on a frauded logic.
jfaust
July 26th, 2002, 10:59 AM
So is 8.5"x11" right or wrong
Right or wrong depending on how you look at it. A non-standard sized piece of paper is not guaranteed to work as a standard sized piece of paper. It may or may not work in a printer, fax, shredder, envelope, folder, binder, etc. Similarly your non-standard code is not guaranteed to work with any given compiler.
Wait, I just said I was done arguing this. I just can't resist shoving an argument back at the person.
OK, now I'm really done. No, really...
Jeff
AnthonyMai
July 26th, 2002, 11:18 AM
Jeff:
I can't help laughing when seeing your last comment on standard or none-standar paper. It just amazes me.
Thow away all your C++ books out of your window. Obviously they are wrong and they don't work because they are not printed on standard 8.5"x11" papers. NONE of them. :-)
Look, the world of paper is much bigger than 8.5x11. And the world of computing is MUCH bigger than C++ STL. OK? A group of people come along to express their philosophy of the art of programming, and comes up to a unified opinion, which forms the basis of ANSI C++. Needlessly saying, there is a huge group of people agreeing with that philisophy.
But that doesn't prevent a different group of people who believes something else, practice something differently, and even form their own standard. It's perfect OK if they get their systems work in the way they desire. It's a free world, right?
I feel we are falling into a religious fight now.
Paul McKenzie
July 26th, 2002, 11:20 AM
Graham
Paul McKenzie
jfaust
Philip Nicoletti
Ruslan Abdikeev
and you
are trying in vain to proving me wrong by pointing out the obvious: i.e., my use of Qsort() does not agree with the C++ standard so it is wrong.Not in vain, but very easily proven wrong.
You mention embedded systems. If an embedded system compiler doesn't support STL, then it isn't a conforming ANSI C++ compiler. This forum is an ANSI C++ forum. C++ knows nothing about embedded systems -- it is just a general purpose language defined by the ANSI/ISO C++ standard. Like it or leave it.
And as to you saying that "it works on 'x' platform", unless you can get a guarantee from the compiler vendor that their non-ANSI compliant behavior will not change from version to version, then and only then can you make the claim that "it will work on 'x' platform". A classic example is writing to a const char * for the VC++ series of compilers. You can do it in V5, but V6 bombs out. Same platform, right? Different results. Undefined behavior.
No, myself and every other C++ programmer worth anything will stick with std::sort. There is no need for further comment.
Regards,
Paul McKenzie
Paul McKenzie
July 26th, 2002, 12:04 PM
Originally posted by jfaust
Similarly your non-standard code is not guaranteed to work with any given compiler. It's not even guaranteed to work on these "embedded" compilers he keeps touting, even ones that don't have STL.
There is nothing stopping someone from writing a std::sort equivalent for these embedded C++ compilers (for any compiler for that matter), that is ANSI compliant (doesn't invoke undefined behavior). Heck, Boris Fomitchev at STLPort has done it. His STLPort is specifically aimed at compilers that don't have STL and/or their library is not ANSI compliant.
A responsible C++ expert who has to deal with a compiler that may not have STL, or may not even have templates would have done the following steps:
a) research how the STL sort works for classes. Understand the algorithms used (i.e. pick up a version of STLPort or the SGI implementation)
b) Adapt the code to work for their compiler. If it supports templates, then templatize the code. If it doesn't unroll the code, and make it "skeleton" code, so (as an example) in the future, you just plug in the desired data type into the skeleton. While doing all this, adhering to the ANSI C++ specs.
c) Fine tune any other parts that could be fine-tuned, again adhering to ANSI C++ specs.
The person described above would
a) have a version of sort that works correctly for non-POD types
c) Make it around the lecture circuit and post articles on how to use the code efficiently with various class types.
d) Get acknowledged by Stroustrup, Meyers, et. al. in their latest books and articles.
Regards,
Paul McKenzie
jfaust
July 26th, 2002, 12:56 PM
I can't help laughing when seeing your last comment on standard or none-standar paper. It just amazes me.
Thow away all your C++ books out of your window. Obviously they are wrong and they don't work because they are not printed on standard 8.5"x11" papers. NONE of them. :-)
The examples you gave for paper were made for a specific purpose, and not made for general purpose use. They may not work for general purpose.
Similarly, you've created a method that works for specific compilers, but may not work in general. At the same time, you're trying to pass it off as a general purpose method. Sorry, it's not.
So laugh away and be amazed, C boy, the comparison holds.
Jeff
Paul McKenzie
July 26th, 2002, 06:15 PM
If you really want portability, maintainability, platform independent, stay away from STL, used the minimum denominator part of C++. That's my opinion. And that is also the opinion of a large group of people. Ever heard of the Embedded C++ Standard?Please cite name and document where these "groups of people" have stated this. Everyone else is tired of citing you names, documents and periodicals, now it should be your turn. And this is not the "Embedded C++ Forum". This forum discusses ANSI C++, in its fullest glory, STL, templates, exception handling, and all. If you have a problem with that, go ask the moderator to start an Embedded C++ Forum. And for those who want to know what the inventor of the C++ language thinks about EC++, here it is:
http://www.research.att.com/~bs/bs_faq.html#EC++
Also, your problem has nothing to do with STL. It is that you are copying non-POD objects using behavior that's undefined. This doesn't matter about embedded or non-embedded. Your code could blow to bits an embedded C++ compiler, just as it is now blowing up the Pacific Group compiler.
Regards,
Paul McKenzie
AnthonyMai
July 26th, 2002, 06:42 PM
Paul:
With due respect, The name of this board does not say "ANSI", nor does it say "standard" nor does it say "STL". So this board is for the discussing of all C++ topics, including all flavor and taste of C++, not limiting to ANSI C++ standard and STL.
Also as you pointed out a long time ago, legacy C functions, stuff like memcpy(), strcmp(), etc. are also included as part of the standard C++ library. So it is totally a legitimate topic to discuss usage of legacy C functions in the context of C++.
Paul McKenzie
July 26th, 2002, 08:00 PM
Please read what the subject of this forum is:
Ask or answer C++ questions not related to Visual C++. This includes Console programming, Linux programming, or general ANSI C++
You don't like templates, exception handling, standard library, fine. Whether you like it or not, they are part of ANSI C++. ANSI C++ is defined by the ANSI ISO/IEC 14882 standard document. In that document describes what has been explained to you by others, both on CodeGuru and comp.lang.c++ as to why your code is faulty.
And yes, those functions you mentioned exist in the C++ library. That doesn't mean they can be used any old place you feel like using them.
Regards,
Paul McKenzie
PaulWendt
July 26th, 2002, 09:08 PM
Paul McKenzie said:
>>>>>
Please read what the subject of this forum is:
quote:
--------------------------------------------------------------------------------
Ask or answer C++ questions not related to Visual C++. This includes Console programming, Linux programming, or general ANSI C++
--------------------------------------------------------------------------------
<<<<<
Don't take this the wrong way, Paul, but INCLUDING ANSI C++
does not mean it's LIMITED to ANSI C++. I've been against
Mai's arguments for almost the whole time ... but I feel like you're
stretching here. The only things people shouldn't discuss here
[according to the quote you gave] are questions related to
Visual C++. Again, no offense is intended.
--Paul Wendt
Paul McKenzie
July 26th, 2002, 11:59 PM
Hello Pau;,
Yes, you're right. However, a Linux and Console program should follow the rules of ANSI C++, just like an embedded C++ compiler subset should follow the rules of ANSI C++ (whatever subset is implemented, it follows ANSI rules for that subset).
My interpretation of the subject matter is that a discussion of compiler specific functions (maybe a Unix "curses" function, or the discussion of interrupt handler functions in C or C++) is allowed here, besides general ANSI C++. Plain, flat-out faulty coding as per language specs shouldn't even be considered, regardless if you are talking about a UNIX fork() function or a Borland gotoxy() call.
Regards,
Paul McKenzie
PaulWendt
July 27th, 2002, 10:11 AM
Hey I totally understand where you're coming from; he's had me
practically ripping my hair out with his seeming stubbornness. I
almost feel like he did a good thing, though; he actually
strengthened my appreciation for C++/STL rather than diminished
it [which I think has been his goal all along]. From where I'm
coming from [24-year old wet-behind-the-ears programmer] it's
nice to see these wild ideas, even if they're totally ludicrous and
ultimately shown to be wrong.
I guess, to sum up, I'm not going to be arguing with you about
whether he should have posted it or not.
--Paul
AnthonyMai
July 27th, 2002, 10:21 AM
Paul M.:
Maybe this is for the first time, I want you to quote something from the ANSI C++ standard document to back up your claim. Note, from the the ANSI C++ standard document, not from the words of any individual.
Now tell me, exactly WHICH LINE of sentence within the formal wording of C++ standard says that using qsort() on an object array is prohibited by the standard?
Does the standard explicitly say you can NOT sort integers using qsort()? Does it say you can not sort doubles using qsort(), does it say you can not sort any object using qsort() as long as it contains a std::string()?
For the record, qsort() is a function provided by the ANSI C++ standard library. MSDN said it is ANSI compatible.
And now we are not even talking about qsort(). We are talking about Qsort(), a user written function.
[B]Now tell me exactly which line of code within my Qsort violates ANSI C++ standard?[B] It does not call any function except for the user provided comp() function. The rest is just manipulating and moving chars and integers.
About the only thing I can thing about, is I cast between void and certain data types. You may not like castings like this. But once again, WHICH LINE in the standard document explicitly prohibit casting from/to an object pointer to/from a void pointer?
Technically, my code does NOT violate any of the ANSI C++ standard caluses. You may have an opinion, but opinion is not the standard. Going through the standard word by word, there is nothing that says you can't abanden std::sort and do your own sorting function. Nor does it say you can't use qsort(). Nor does it say you can't cast to void pointer.
OK, now go and find clauses from the standard document before you come back to argue. Don't cite words from opinions of big guys. Opinions are opinions, standard doc is standard doc.
jfaust
July 27th, 2002, 10:48 AM
To compiler writers, the standard describes what a compiler must adhere to. To users of C++ compilers, it describes what can be counted on.
It does not describe what can not be counted on. This would be an infinitely long list of items. Obviously, it would be difficult to fit into a document, even using non-standard sized paper ;)
The standard does not tell you how to program. That's not its purpose. It also does not tell you how not to program. That's also not its purpose. Its purose is to provide compiler writers with a precise and detailed document describing exactly what a compiler must provide in order to be ANSI compliant.
The outcome of this? If it is not in the standard, it cannot be relied on. If it is in the standard, it can be relied on. It is as simple as that. Black and white. True and false. Standard and non-standard. It cannot be any clearer than that.
Jeff
Paul McKenzie
July 27th, 2002, 10:59 AM
Originally posted by AnthonyMai
Paul M.:
Maybe this is for the first time, I want you to quote something from the ANSI C++ standard document to back up your claim. Note, from the [B]the ANSI C++ standard document, not from the words of any individual.Why not? Unlike you, arrogance doesn't disqualify me from using sources from other individuals, especially experts in the field. Showing you where in the ANSI document has been done by others an umpteen times already. You want me to quote them again? Why? To increase this thread by another 50 posts? I don't have the patience, and from the words of others, they no longer have the patience. If someone were to bring in a neutral party to take a look at this thread, they would say, (as they say in the street basketball games), "you got taken to school." Enough said.
BTW, how is your testing doing with the Pacific Group compiler? Still not working? I wonder why...I wonder if it's that pesky undefined behavior. Bad little buggers, aren't they?
Regards,
Paul McKenzie
Paul McKenzie
July 27th, 2002, 12:25 PM
Originally posted by PaulWendt
Hey I totally understand where you're coming from; he's had me
practically ripping my hair out with his seeming stubbornness. I
almost feel like he did a good thing, though; he actually
strengthened my appreciation for C++/STL rather than diminished
it [which I think has been his goal all along]. From where I'm
coming from [24-year old wet-behind-the-ears programmer] it's
nice to see these wild ideas, even if they're totally ludicrous and
ultimately shown to be wrong.
I guess, to sum up, I'm not going to be arguing with you about
whether he should have posted it or not.
--Paul Yes, I believe the same thing -- the opposite effect expected by the OP occurred -- usage of STL has been strengthened by this thread, not diminished.
Regards,
Paul McKenzie
Gabriel Fleseriu
July 28th, 2002, 08:20 AM
Originally posted by Paul McKenzie
Yes, I believe the same thing -- the opposite effect expected by the OP occurred -- usage of STL has been strengthened by this thread, not diminished.
Regards,
Paul McKenzie
You are right, IMHO. Besides of that, I (and many others probably too) tend to have more faith in what Stroustrup, Sutter et. al. say, than in the oppinion of some individual on CodeGuru. By all respect -- no offense intended. :)
AnthonyMai
July 28th, 2002, 09:49 AM
You are right, IMHO. Besides of that, I (and many others probably too) tend to have more faith in what Stroustrup, Sutter et. al. say, than in the oppinion of some individual on CodeGuru.
See what I said before? This is falling into a religious fight. Faith is a word associated with religions. If you believe something or someone by faith, instead of by evidence and reasoning, you are religious. Contrary to what Paul said, I am not going to continue posting on this thread since I have no interest in regilious fight.
I asked Paul to cite the exact clause FROM the standard document to backup his claim that my code "VIOLATES" the standard. He refuses to do so. The fact is he can't. I do things that looks bad in Paul's eyes, I do type unsafe casting from/to a void pointer. I swap objects by direct binary swapping. You may say that's bad, you may say it is unsafe, you may say there may be better solutions. You can say all those because good or bad, safe or unsafe are opinion oriented.
But you can not say that these "bad" things break the standard. No where in the C++ standard prohibits type-unsafe casting. On the contrary, cast operators are specifically INVENTED for the purpose of such type-unsafe casting, i.e., static_cast. Why would static_cast be added to the standard if type-unsafe castings are OUTLAWED?
Does type-unsafe casting break the C++ standard? Paul must think so. Because the only thing bad in my Qsort(), which Paul claims to have broken the standard, is I did type-unsafe casting from/to void*.
Does Paul use void pointer at all? You've got to be doing type-unsafe casting some where, if you have ever used void* at all. So you are breaking the C++ standard right?
The STL code uses fwrite() and a number of legacy C functions underneath, so it calls functions with void* parameters here and there, and some sort of type-unsafe casting is going on there, So STL itself has broken the C++ standard, right?
There is no dispute that The more complicated and time consuming a copy constructor an object has, the more performance advantage you have by using (Q)qsort(), versus std::sort(). The later forces to construct new objects and destroy un-necessarily.
It's ironic that some one cite that std::sort() beats qsort() by some margin when it compares POD data, like integer or double. std::sort() was invented to do "type-safe" sort for NONE-POD data, ironically, that's where std::sort() loses big time to qsort(). I have already shown, in some cases where the object construction involves memory allocation, it loses by being 100+ times slower than qsort().
jfaust
July 28th, 2002, 12:13 PM
Is the Portland compiler wrong, or are you wrong?
I'm sure the Portland compiler follows the standard. I'm even more sure that you don't follow the standard.
cite the exact clause FROM the standard document to backup his claim that my code "VIOLATES" the standard.
The standard is not a comprehensive list of what a programmer cannot do. It does, however, provide exactly and comprehensively what can be relied on.
I'm running out of ways to tell you that you are wrong. Well, here's another.
proof:
"direct binary swapping" for non-POD is not in the standard.
-> compiler writers do not have to support it.
-> it may not be supported by a given compiler
-> programmers cannot rely on it to work on a given compiler.
QED
Anyway, let's hear your take on why Qsort does not work on the Portland compiler. Where is the problem? Is it the compiler or your code? Or was your code only intended to work on the compiler you used to create it?
Jeff
Paul McKenzie
July 28th, 2002, 01:29 PM
So far folks, reports of qsort() working for the Portland compiler are as follows:
it doesn't.
Zeeshan asked this question -- If sorting objects were as easy as the OP thinks it is, why haven't any of the experts done it? Are they naive coders, or is there a reason as to why std::sort works the way it does? Has the OP or any one else pondered that question? Do we have an Einstein here on CodeGuru, and everyone else is a novice? Why hasn't Andrei Alexandrescu (who I believe is one of, if not the best C++ programmer in the world) seen this and written an extensive paper on such a core piece of the library such as std::sort? Why does the head of the ANSI C++ standardization committee point out not to use qsort() in the C/C++ Users Journal article?
It was a recent article, the OP still has time to submit these "incredible findings" to CUJ and have an article posted rebutting the first article.
As Ruslan pointed out at the beginning of this thread, movement of non-POD objects safely involves proper object construction or assignment. Blindly moving objects around, without invoking the proper construction / assigment is nothing but a disaster waiting to happen. This is unbelievable to the OP, since the OP background is 'C'. But this is C++, where rules are to be followed. Again, look at the case of at least one compiler. The qsort() doesn't work, even though it looks like it should work if you look at it in terms of 'C' programming. In 'C', you have no objects, no virtual base classes, no virtual functions, no copy ctor or op= to worry about, so coding like what the OP posts looks fine. Problem is, for ANSI C++ it isn't.
Someone writes a custom copy c-tor and op = for a reason. The reason being that if this object is moved or copied, the contract is that the the programmers routines are called correctly. If you were to write a copy c-tor and op= in the SomeClass, you will notice that it's never called when using qsort(), even though the object has moved. The C++ programmers does not want their objects moved like this (As Ruslan in the beginining of this thread put it, "blindly" copying). Here is his direct quote:
Third, I want my copy assignment operators and copy constructors
work as intended.
Not blindly copied.
I want members of my class assigned and copied as it were intended
by their authors.
Not blindly copied.
With std::sort, the contract is met: the proper c-tor and op = are called for the object when it is copied from one location to another. Without calling the proper construction / assignment, what will happen when you move an object? Undefined behavior. Is this the reason why the writer's of std::sort did things the way they did?
Another point -- std::sort may use a quicksort algorithm (not qsort), but there is no guarantee that it does. There are other sorting strategies that can be used. STLPort uses the "introsort" algortihm. Note the emphasis on "algorithm". All std::sort uses is an algorithm -- it could be quicksort, Quickersort, IntroSort, or some other sort. Improve the algorithm, and you improve std::sort. There is another newsgroup comp.std.c++, where things like this are discussed. The link to the thread that Ruslan provided gives an insight of how careful these people think about topics such as these.
If it were as simple as the OP thinks it is, this problem would have been solved a long time ago and would have been submitted to some organization that has influence. Since it hasn't, again, the OP can do this and be a mover and shaker in the C++ community. I mean, 100x increase? Why keep this a secret?
Regards,
Paul McKenzie
Paul McKenzie
July 28th, 2002, 01:39 PM
Originally posted by jfaust
Is the Portland compiler wrong, or are you wrong?
I'm sure the Portland compiler follows the standard. I'm even more sure that you don't follow the standard.
//...
Anyway, let's hear your take on why Qsort does not work on the Portland compiler. Where is the problem? Is it the compiler or your code? Or was your code only intended to work on the compiler you used to create it?
Jeff Don't be surprised if you get the subtlely arrogant response that the "Portland compiler is small potatoes".
Regards,
Paul McKenzie
AnthonyMai
July 29th, 2002, 09:31 AM
About Qsort used on Portland Group compiler.
Philips was the only one reporting the problem on portland compiler. And the description of exactly what happened is not clear. And no one else comfirmed that result. Probably due to the fact that maybe Philips is the only one who has a copy of that ***** ****** compiler.
I am unable to comment since I do not have a copy of that compiler, and Philips has not tell us exactly where and how it screw up.
As a long time, programmer, Paul, you've got to know that most time when a piece of code does not work in one spot, the fault is usually NOT at that spot, But some where else that you may totally not have expected. That is why DEBUGGING is more difficult than writting code for most programmers.
If Qsort does not work, you really can't start pointing finger right away at Qsort. It may well be that the code preceeding your Qsort call screwed something up, or that you are not passing the correct parameter to Qsort. There are lot of possibilities that that I can point my finger towards. But I am not going to make any speculation or comment until I see more detail reported from Philips.
Back to binary copying of objects. How many times have I emphasised that I am NOT talking about the broader meaning of object copying in which a new object is created which behaves identically like its original.
I am talking about binary copying in a VERY NARROW CONTEXT, in which we are NOT creating new instance of the object, we are merely moving object around. And further, we are not moving objects to any random memory address. We are swapping, i.e., we are moving an object to a memory location where another instance of the same type of object has previously occupied.
And I have further restricted the usable domain by requiring that the object's state should not depend on its own memory location, but depend entirely on all of it's data members.
In such narrowly defined context, swapping by direct binary swapping should have no problem. It would be interesting to see why Philips's code doesn't work on Portland compiler. But before any one investigate that problem into the detail. No one can really say any thing for sure exactly what causes the problem.
jfaust
July 29th, 2002, 09:48 AM
If Qsort does not work, you really can't start pointing finger right away at Qsort.
Well, that makes no sense. If A does not work, don't blame A.
Actually, your algorithm is the first suspect. First of all, there's not much else going on in the program. Second, you're not using a known method/library for sorting. Third, it is complex and largely untested. Fourth, you are relying on something not supported by the standard.
Now what happens? What if it's shown that it really is the fault of your code, and not something else. Will you accept this, and admit that you were wrong? Will you own up to it?
Will you admit that it is dangerous to step outside of the standard?
Or, which is what we all expect, will you blame something else or possibly say that it's not an important enough compiler to consider?
Jeff
codeguru.com
Copyright Internet.com Inc., All Rights Reserved.