• dsimcha (36/36) Oct 22 2009 Regarding recent discussions in Bugzilla: I wonder if we could somehow ...
• bearophile (5/8) Oct 22 2009 I have a similar structCmp in my dlibs, it's used by the Record/record (...
• Andrei Alexandrescu (7/48) Oct 22 2009 This can be done if you associate a cost with each operation (e.g.
• dsimcha (3/13) Oct 22 2009 Right, this is what I had in mind. I take it this isn't a common, well-...
• Don (5/13) Oct 22 2009 The compiler should be doing this. It's the way to fix the Bugzilla bug.
• Walter Bright (5/6) Oct 22 2009 It shouldn't do it. If a memberwise compare is done, it should do them

dsimcha <dsimcha yahoo.com> writes:

Regarding recent discussions in Bugzilla:  I wonder if we could somehow define
a super-efficient struct opEquals that performs introspection and only tests
expensive members if it's necessary.  For example, here is a simple case of it:

enum opEqualsMixin = q{
    bool opEquals(typeof(this) rhs) {
        foreach(tupleIndex, elem; this.tupleof) {
            static if(isIntegral!(typeof(elem))) {
                 // Compare integers first.  They're cheap.
                 if(elem != rhs.tupleof[tupleIndex]) {
                     return false;
            }
        }

        foreach(tupleIndex, elem; this.tupleof) {
            static if(isFloatingPoint!(typeof(elem))) {
                 // Compare floats.  They're also cheap.
                 if(elem != rhs.tupleof[tupleIndex]) {
                     return false;
            }
        }

        foreach(tupleIndex, elem; this.tupleof) {
            static if(!isIntegral!(typeof(elem)) &&
                !isFloatingPoint!(typeof(elem))) {

                 // All the cheap elements were equal.
                 // Resort to more expensive comparisons.
                 if(elem != rhs.tupleof[tupleIndex]) {
                     return false;
            }
        }

        return true;
    }
}

Of course, we could get even fancier.  We could recursively introspect struct
types and use various heuristics to calculate the optimal comparison order at
compile time.  Similar stuff could be done for a generic opCmp that gives a
struct an arbitrary total ordering as long as all of its members have a total
ordering.

bearophile <bearophileHUGS lycos.com> writes:

dsimcha:

 Similar stuff could be done for a generic opCmp that gives a
 struct an arbitrary total ordering as long as all of its members have a total
 ordering.

I have a similar structCmp in my dlibs, it's used by the Record/record (similar
to the Tuple/tuple of Phobos2). It works recursively.
I'd like all D structs to have such richer semantics (opCmp, opHash, opEquals,
a good printing), so Tuple can be removed from the std lib.

Bye,
bearophile

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

dsimcha wrote:
 Regarding recent discussions in Bugzilla:  I wonder if we could somehow define
 a super-efficient struct opEquals that performs introspection and only tests
 expensive members if it's necessary.  For example, here is a simple case of it:
 
 enum opEqualsMixin = q{
     bool opEquals(typeof(this) rhs) {
         foreach(tupleIndex, elem; this.tupleof) {
             static if(isIntegral!(typeof(elem))) {
                  // Compare integers first.  They're cheap.
                  if(elem != rhs.tupleof[tupleIndex]) {
                      return false;
             }
         }
 
         foreach(tupleIndex, elem; this.tupleof) {
             static if(isFloatingPoint!(typeof(elem))) {
                  // Compare floats.  They're also cheap.
                  if(elem != rhs.tupleof[tupleIndex]) {
                      return false;
             }
         }
 
         foreach(tupleIndex, elem; this.tupleof) {
             static if(!isIntegral!(typeof(elem)) &&
                 !isFloatingPoint!(typeof(elem))) {
 
                  // All the cheap elements were equal.
                  // Resort to more expensive comparisons.
                  if(elem != rhs.tupleof[tupleIndex]) {
                      return false;
             }
         }
 
         return true;
     }
 }

Looks cool. I think a first shot would be to make it a standalone function.

 Of course, we could get even fancier.  We could recursively introspect struct
 types and use various heuristics to calculate the optimal comparison order at
 compile time.  Similar stuff could be done for a generic opCmp that gives a
 struct an arbitrary total ordering as long as all of its members have a total
 ordering.

This can be done if you associate a cost with each operation (e.g. 
comparing numbers has cost 1, comparing strings has cost 10, comparing 
using a user-defined function has cost 40 etc.) and then optimize for 
smallest average cost.


Andrei

dsimcha <dsimcha yahoo.com> writes:

== Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article
 Of course, we could get even fancier.  We could recursively introspect struct
 types and use various heuristics to calculate the optimal comparison order at
 compile time.  Similar stuff could be done for a generic opCmp that gives a
 struct an arbitrary total ordering as long as all of its members have a total
 ordering.

 This can be done if you associate a cost with each operation (e.g.
 comparing numbers has cost 1, comparing strings has cost 10, comparing
 using a user-defined function has cost 40 etc.) and then optimize for
 smallest average cost.
 Andrei

Right, this is what I had in mind.  I take it this isn't a common, well-known
optimization technique already?  Walter?

Don <nospam nospam.com> writes:

dsimcha wrote:
 Regarding recent discussions in Bugzilla:  I wonder if we could somehow define
 a super-efficient struct opEquals that performs introspection and only tests
 expensive members if it's necessary.

The compiler should be doing this. It's the way to fix the Bugzilla bug.
There should be no need to define opEquals() unless it does something 
different to an element-by-element comparison.

 Of course, we could get even fancier.  We could recursively introspect struct
 types and use various heuristics to calculate the optimal comparison order at
 compile time.  Similar stuff could be done for a generic opCmp that gives a
 struct an arbitrary total ordering as long as all of its members have a total
 ordering.

Yes. This is something the compiler can't (or shouldn't) do.

Walter Bright <newshound1 digitalmars.com> writes:

Don wrote:
 Yes. This is something the compiler can't (or shouldn't) do.

It shouldn't do it. If a memberwise compare is done, it should do them 
in order. This allows the struct designer to lay out the fields 
optimally (similarly to how case statement order affects efficiency in 
switch statements).