www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Struct Comparison

reply 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.
Oct 22 2009
next sibling parent 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
Oct 22 2009
prev sibling next sibling parent reply 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
Oct 22 2009
parent 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.

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?
Oct 22 2009
prev sibling parent reply 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.
Oct 22 2009
parent 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).
Oct 22 2009