c/c++ question: comparing/sorting sctructs

[trojanfoe]

Why don't you trust your compiler?

Just implement an operator== as a memberwise compare. If memcmp is possible, and actually more efficient, don't you think the compiler will recognize that and optimize the code?


Bo Persson

Huh? If you are implementing the operator == then you define how the comparison is performed. The compiler won't have much 'say' in the matter.

[Bo Persson]

Why don't you trust your compiler?

Just implement an operator== as a memberwise compare. If memcmp is possible, and actually more efficient, don't you think the compiler will recognize that and optimize the code?


Bo Persson

Huh? If you are implementing the operator == then you define how the comparison is performed. The compiler won't have much 'say' in the matter.

The compiler has very much to say on the matter!

If you implement a memberwise compare, comparing each member in sequence, the compiler can very much transform that into a call to memcmp (or its inlined equivalent). *If* it sees that it would actually be faster, which is not at all certain.

It was a very long time ago, that programmers could outsmart compilers on low level stuff. Consider that the guys working on the optimizer passes of the compiler are at least as smart as you and me, but they work full time on this. What are the odds that we can find nice a trick that they have missed?

[trojanfoe]

Why don't you trust your compiler?

Just implement an operator== as a memberwise compare. If memcmp is possible, and actually more efficient, don't you think the compiler will recognize that and optimize the code?


Bo Persson

Huh? If you are implementing the operator == then you define how the comparison is performed. The compiler won't have much 'say' in the matter.

The compiler has very much to say on the matter!

If you implement a memberwise compare, comparing each member in sequence, the compiler can very much transform that into a call to memcmp (or its inlined equivalent). *If* it sees that it would actually be faster, which is not at all certain.

It was a very long time ago, that programmers could outsmart compilers on low level stuff. Consider that the guys working on the optimizer passes of the compiler are at least as smart as you and me, but they work full time on this. What are the odds that we can find nice a trick that they have missed?

Oh I see what you mean, however to give the compiler the opportunity you would have to code each memberwise comparison something like this:

Code: Select all

field1 == other.field1;
field2 == other.field2;

But as we have seen in this thread alone, that isn't legal unless each member also has the operator == implemented. That doesn't give the compiler any choice other than to use your implementation.

Also in C++ I would not advocate the use of memset to initialise padding bytes as I have mentioned before. This is because of virtual function pointer tables that are used to implement inhertitance; they would get blatted.

My method is wholly restricted to C and as already mentioned comes with conditions. Performance comes at a price as everyone knows there is no such thing as a free lunch.

[Dann Corbit]

{snip}

Also in C++ I would not advocate the use of memset to initialise padding bytes as I have mentioned before. This is because of virtual function pointer tables that are used to implement inhertitance; they would get blatted.

My method is wholly restricted to C and as already mentioned comes with conditions. Performance comes at a price as everyone knows there is no such thing as a free lunch.

The virtual function pointers are not the only problem with memset/memcpy/memmove for classes. Constructors and destructors do not get fired. In the general case, these functions are naughty-no-nos for classes.

[Cardoso]

Thank you all for your answers.
Now please consider the special case of a struct with no pointers in it and the compiler switch to padding with 1 byte turned on.
BTW does padding with 1 byte mean no padding bytes at all? The sizeof(structname) would be what we see in the code with no hidden bytes?.
Now, would memcmp work with no problems at all?
If that is the case then I would have my opening book struct array problem solved.

Thanks,
Alvaro

[Dann Corbit]

Padding on 1 byte boundaries means no padding.
Compilers do not implement this pragma in the same way, so you will have to do special things if you ever change compilers.
If your struct has lots of members, I guess that memcmp may actually be slower on average, unless your data is extremely similar. Consider:

typedef struct foo {
int a;
int b;
int c;
int d;
int e;
int f;
int g;
int h;
int i;
int j;
int k;
int l;
int m;
int n;
int o;
int p;
int q;
int r;
int s;
int t;
int u;
int v;
}

foo f1, f2;
...
if (f1.a > f1.b) // then we don't even have to check the other 22 things...

In any case, since we are just looking for a book opening and we want an exact match, I do not think that the construction of the comparison method is very important. Just do it however you feel the most comfortable.

[mcostalba]

Thank you all for your answers.
Now please consider the special case of a struct with no pointers in it and the compiler switch to padding with 1 byte turned on.
BTW does padding with 1 byte mean no padding bytes at all? The sizeof(structname) would be what we see in the code with no hidden bytes?.
Now, would memcmp work with no problems at all?
If that is the case then I would have my opening book struct array problem solved.

Thanks,
Alvaro

Alvaro,

please accept this hard learned suggestion: Forget tricks !!!!, you will never learn how to code if you start this way.

memcmp is a dirty trick to say at least, don't use it, is not portable, is compiler dependent, is endian dependent, is probably broken and most impostant is unnecessary for you.

The alghoritm to do proper software engeneering is:

1 - Code your program the way is meant to be coded, in the most natural end logical way.

2- IF (and this is a big if) you are not satisfied with perfrormance then PROFILE the code (80% of cases slow downs are not where you think they are, and if you are a novice this figure goes easily to 99% of cases)

3- Try to speed up ONLY the critical paths, speeding up randomly, monkey style, only increases crap level of your code without added benefit.


In your case I wouldn't be surprised if you find that memcmp does not speed up anything: if you see previous operator>() implementations this boils down to a long list of terms "anded" togheter (a && b && c && ...)

Now, C/C++ rules states that && chains are shortcuted, i.e. comparison stops at the first difference, so if the first terms are more likely to be unique, as can be a board position, comparison will be very fast without using broken tricks.

Regards
Marco

[sje]

3- Try to speed up ONLY the critical paths, speeding up randomly, monkey style, only increases crap level of your code without added benefit.

There is much truth to this statement.

Probably 90 percent of all chess program bugs come from deficient optimization attempts. Maybe more. That's a lot of time spent on trying to speed up things. Is your time worth that much less than the machine's? Wouldn't your time be better spent on improving existing algorithms or inventing new ones?

[trojanfoe]

memcmp is a dirty trick to say at least, don't use it, is not portable, is compiler dependent, is endian dependent, is probably broken and most impostant is unnecessary for you.

rubbish

[mcostalba]

memcmp is a dirty trick to say at least, don't use it, is not portable, is compiler dependent, is endian dependent, is probably broken and most impostant is unnecessary for you.

rubbish

Of course memcmp() is a standard function. But just compares RAM. Is the use of memcmp to compare struct that has that long list of qualities.

I don't know if this was clear. Perhaps is still rubbish for you, hopeful less smelly