www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - == operator

reply "Jonathan Marler" <johnnymarler gmail.com> writes:
I've recently looked at how the '==' operator works with classes. 
  I was disappointed to find that 'a == b' always gets rewritten 
to:

.object.opEquals(a, b);

The reason for my disappointment is that this results in 
unnecessary overhead. I would think that the compiler would first 
try to rewrite the '==' operator using a type-specific opEquals 
method, then fall back on the generic version if one did not 
exist.  Is there a reason for this?
Jan 03 2015
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 1/3/15 5:30 PM, Jonathan Marler wrote:

 I've recently looked at how the '==' operator works with classes.  I was
 disappointed to find that 'a == b' always gets rewritten to:

 .object.opEquals(a, b);

 The reason for my disappointment is that this results in unnecessary
 overhead. I would think that the compiler would first try to rewrite the
 '==' operator using a type-specific opEquals method, then fall back on
 the generic version if one did not exist.  Is there a reason for this?


TDPL has a detailed explanation of that, including a reference to Java's 
approach. There's less overhead in calling the free function in object 
(it's inlinable and if e.g. the references are equal there's no virtual 
call overhead).

Andrei
Jan 03 2015
parent reply "Jonathan Marler" <johnnymarler gmail.com> writes:
On Sunday, 4 January 2015 at 03:14:31 UTC, Andrei Alexandrescu 
wrote:

 On 1/3/15 5:30 PM, Jonathan Marler wrote:

 I've recently looked at how the '==' operator works with 
 classes.  I was
 disappointed to find that 'a == b' always gets rewritten to:

 .object.opEquals(a, b);

 The reason for my disappointment is that this results in 
 unnecessary
 overhead. I would think that the compiler would first try to 
 rewrite the
 '==' operator using a type-specific opEquals method, then fall 
 back on
 the generic version if one did not exist.  Is there a reason 
 for this?


 TDPL has a detailed explanation of that, including a reference 
 to Java's approach. There's less overhead in calling the free 
 function in object (it's inlinable and if e.g. the references 
 are equal there's no virtual call overhead).

 Andrei


Can you point me to that detailed explanation?

The problem I see is that in almost all cases the 
opEquals(Object) method will have to perform a cast back to the 
original type at runtime.  The problem is this isn't doing any 
useful work.  The current '==' operator passes the class as an 
Object to a generic opEquals method which eventually gets passed 
to a method that must cast it back to the original type.  Why not 
just have the == operator rewrite the code to call a "typed" 
opEquals method?  Then no casting is necessary.

I wrote a quick performance test to demonstrate the issue.

import std.stdio;
import std.datetime;
class IntWrapper
{
   int x;
   this(int x)
   {
     this.x = x;
   }
   override bool opEquals(Object o)
   {
     IntWrapper other = cast(IntWrapper)o;
     return other && this.x == other.x;
   }
   bool opEquals()(auto ref const IntWrapper other) const
   {
     return this.x == other.x;
   }
}
void main(string[] args)
{
   size_t runCount = 2;
   size_t loopCount = 10000000;
   StopWatch sw;

   IntWrapper x = new IntWrapper(1);
   IntWrapper y = new IntWrapper(1);

   bool result;

   for(auto runIndex = 0; runIndex < runCount; runIndex++) {

     writefln("run %s (loopcount %s)", runIndex + 1, loopCount);

     sw.reset();
     sw.start();
     for(auto i = 0; i < loopCount; i++) {
       result = x.x == y.x;
     }
     sw.stop();
     writefln("  x.x == y.x               : %s microseconds", 
sw.peek.usecs);

     sw.reset();
     sw.start();
     for(auto i = 0; i < loopCount; i++) {
       result = x.opEquals(y);
     }
     sw.stop();
     writefln("  x.opEquals(y)            : %s microseconds", 
sw.peek.usecs);

     sw.reset();
     sw.start();
     for(auto i = 0; i < loopCount; i++) {
       result = x.opEquals(cast(Object)y);
     }
     sw.stop();
     writefln("  x.opEquals(cast(Object)y): %s microseconds", 
sw.peek.usecs);

     sw.reset();
     sw.start();
     for(auto i = 0; i < loopCount; i++) {
       result = x == y;
     }
     sw.stop();
     writefln("  x == y                   : %s microseconds", 
sw.peek.usecs);

   }
}

Compiled with dmd on Windows(x64):
dmd test.d -O -boundscheck=off -inline -release


run 1 (loopcount 10000000)
   x.x == y.x               : 6629 microseconds
   x.opEquals(y)            : 6680 microseconds
   x.opEquals(cast(Object)y): 89290 microseconds
   x == y                   : 138572 microseconds
run 2 (loopcount 10000000)
   x.x == y.x               : 6124 microseconds
   x.opEquals(y)            : 6263 microseconds
   x.opEquals(cast(Object)y): 90918 microseconds
   x == y                   : 132807 microseconds
Jan 03 2015
next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 1/3/15 8:43 PM, Jonathan Marler wrote:

 On Sunday, 4 January 2015 at 03:14:31 UTC, Andrei Alexandrescu wrote:

 On 1/3/15 5:30 PM, Jonathan Marler wrote:

 I've recently looked at how the '==' operator works with classes.  I was
 disappointed to find that 'a == b' always gets rewritten to:

 .object.opEquals(a, b);

 The reason for my disappointment is that this results in unnecessary
 overhead. I would think that the compiler would first try to rewrite the
 '==' operator using a type-specific opEquals method, then fall back on
 the generic version if one did not exist.  Is there a reason for this?


 TDPL has a detailed explanation of that, including a reference to
 Java's approach. There's less overhead in calling the free function in
 object (it's inlinable and if e.g. the references are equal there's no
 virtual call overhead).

 Andrei


 Can you point me to that detailed explanation?


You'd need to buy TDPL. In turn, TDPL refers this article: 
http://www.drdobbs.com/jvm/java-qa-how-do-i-correctly-implement-th/184405053 
-- Andrei
Jan 03 2015
prev sibling parent reply "anonymous" <anonymous example.com> writes:
On Sunday, 4 January 2015 at 04:43:17 UTC, Jonathan Marler wrote:

 The problem I see is that in almost all cases the 
 opEquals(Object) method will have to perform a cast back to the 
 original type at runtime.  The problem is this isn't doing any 
 useful work.  The current '==' operator passes the class as an 
 Object to a generic opEquals method which eventually gets 
 passed to a method that must cast it back to the original type.
  Why not just have the == operator rewrite the code to call a 
 "typed" opEquals method?  Then no casting is necessary.


[...]

 run 1 (loopcount 10000000)
   x.x == y.x               : 6629 microseconds
   x.opEquals(y)            : 6680 microseconds
   x.opEquals(cast(Object)y): 89290 microseconds
   x == y                   : 138572 microseconds
 run 2 (loopcount 10000000)
   x.x == y.x               : 6124 microseconds
   x.opEquals(y)            : 6263 microseconds
   x.opEquals(cast(Object)y): 90918 microseconds
   x == y                   : 132807 microseconds


I made made opEquals(Object) final and tried with ldc. Gives me 
these times:

run 1 (loopcount 10000000)
   x.x == y.x               : 0 microseconds
   x.opEquals(y)            : 0 microseconds
   x.opEquals(cast(Object)y): 0 microseconds
   x == y                   : 108927 microseconds
run 2 (loopcount 10000000)
   x.x == y.x               : 0 microseconds
   x.opEquals(y)            : 0 microseconds
   x.opEquals(cast(Object)y): 0 microseconds
   x == y                   : 106700 microseconds

Threw some `asm {}`s in there to make it less hyper-optimized:

run 1 (loopcount 10000000)
   x.x == y.x               : 4996 microseconds
   x.opEquals(y)            : 3932 microseconds
   x.opEquals(cast(Object)y): 3924 microseconds
   x == y                   : 109300 microseconds
run 2 (loopcount 10000000)
   x.x == y.x               : 3068 microseconds
   x.opEquals(y)            : 2931 microseconds
   x.opEquals(cast(Object)y): 2963 microseconds
   x == y                   : 108093 microseconds

I think (final) opEquals(Object) itself is ok.

A final opEquals(Object) is faster with dmd, too. But it's 
nowhere near the others. So apparently dmd misses some 
optimization there, presumably inlining.
Jan 04 2015
parent "Jonathan Marler" <johnnymarler gmail.com> writes:
I've create a PR for a templated opEquals here 
(https://github.com/D-Programming-Language/druntime/pull/1087).  
Currently it will not build without some changes in phobos, PR 
here 
(https://github.com/D-Programming-Language/phobos/pull/2848).  
Using the new templated opEquals it fixed the 
overhead/performance issues as seen here:

compiled on windows(x64): dmd opEqualsTest.d -inline -O -release

run 1 (loopcount 10000000)
   x.x == y.x               : 11609 microseconds
   x.opEquals(y)            : 22303 microseconds
   x.opEquals(cast(Object)y): 146859 microseconds
   x == y                   : 37685 microseconds
run 2 (loopcount 10000000)
   x.x == y.x               : 7525 microseconds
   x.opEquals(y)            : 7528 microseconds
   x.opEquals(cast(Object)y): 106771 microseconds
   x == y                   : 37251 microseconds

As you can see the '==' operator is now much close to the direct 
call to opEquals.  There is still some minimal overhead (I think 
caused by an extra function call and some null checks) but it is 
much closer.  I'm still working on the PRs but this may be a good 
solution.
Jan 06 2015
prev sibling parent reply "anonymous" <anonymous example.com> writes:
On Sunday, 4 January 2015 at 01:30:11 UTC, Jonathan Marler wrote:

 I've recently looked at how the '==' operator works with 
 classes.
  I was disappointed to find that 'a == b' always gets rewritten 
 to:

 .object.opEquals(a, b);

 The reason for my disappointment is that this results in 
 unnecessary overhead. I would think that the compiler would 
 first try to rewrite the '==' operator using a type-specific 
 opEquals method, then fall back on the generic version if one 
 did not exist.  Is there a reason for this?


For reference, here is .object.opEquals (according to 
documentation[1]):

bool opEquals(Object a, Object b)
{
     if (a is b) return true;
     if (a is null || b is null) return false;
     if (typeid(a) == typeid(b)) return a.opEquals(b);
     return a.opEquals(b) && b.opEquals(a);
}

I see one fundamental source of overhead: The types degenerate to 
Object, resulting in virtual calls that could be avoided. Maybe 
it'd be worthwhile to templatize object.opEquals: `bool 
opEquals(A, B)(A a, B b)`.

Also, the typeid thing could be counter-productive with trivial 
equalities. But it helps with complex ones.

By the way, I think `typeid(a) == typeid(b)` is silly. It calls 
object.opEquals on the `typeid`s. And if they're not identical, 
that in turn calls object.opEquals on the `typeid`s of the 
`typeid`s. That fortunately hits the `is` case, or we'd go on 
forever. All that only to realize that 
`typeid(a).opEquals(typeid(b))` suffices.

[1] http://dlang.org/operatoroverloading.html
Jan 03 2015
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 1/3/15 7:23 PM, anonymous wrote:

 For reference, here is .object.opEquals (according to documentation[1]):

 bool opEquals(Object a, Object b)
 {
      if (a is b) return true;
      if (a is null || b is null) return false;
      if (typeid(a) == typeid(b)) return a.opEquals(b);
      return a.opEquals(b) && b.opEquals(a);
 }

 I see one fundamental source of overhead: The types degenerate to
 Object, resulting in virtual calls that could be avoided. Maybe it'd be
 worthwhile to templatize object.opEquals: `bool opEquals(A, B)(A a, B b)`.


Good point. It's been discussed but rejected because druntime generally 
shuns templates. I think that resistance is mostly vestigial by now.


 Also, the typeid thing could be counter-productive with trivial
 equalities. But it helps with complex ones.

 By the way, I think `typeid(a) == typeid(b)` is silly. It calls
 object.opEquals on the `typeid`s. And if they're not identical, that in
 turn calls object.opEquals on the `typeid`s of the `typeid`s. That
 fortunately hits the `is` case, or we'd go on forever. All that only to
 realize that `typeid(a).opEquals(typeid(b))` suffices.

 [1] http://dlang.org/operatoroverloading.html


Interesting. Is a pull request in your future? :o) -- Andrei
Jan 03 2015
next sibling parent "anonymous" <anonymous example.com> writes:
On Sunday, 4 January 2015 at 03:37:05 UTC, Andrei Alexandrescu 
wrote:

 By the way, I think `typeid(a) == typeid(b)` is silly. It calls
 object.opEquals on the `typeid`s. And if they're not 
 identical, that in
 turn calls object.opEquals on the `typeid`s of the `typeid`s. 
 That
 fortunately hits the `is` case, or we'd go on forever. All 
 that only to
 realize that `typeid(a).opEquals(typeid(b))` suffices.

 [1] http://dlang.org/operatoroverloading.html


 Interesting. Is a pull request in your future? :o) -- Andrei


No need. The actual code has it right: 
https://github.com/D-Programming-Language/druntime/blob/b3a8032e3960480a1588b3d1a4491808b4502d67/src/object_.d#L171
Jan 04 2015
prev sibling parent Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Saturday, January 03, 2015 19:37:16 Andrei Alexandrescu via Digitalmars-d
wrote:

 On 1/3/15 7:23 PM, anonymous wrote:

 For reference, here is .object.opEquals (according to documentation[1]):

 bool opEquals(Object a, Object b)
 {
      if (a is b) return true;
      if (a is null || b is null) return false;
      if (typeid(a) == typeid(b)) return a.opEquals(b);
      return a.opEquals(b) && b.opEquals(a);
 }

 I see one fundamental source of overhead: The types degenerate to
 Object, resulting in virtual calls that could be avoided. Maybe it'd be
 worthwhile to templatize object.opEquals: `bool opEquals(A, B)(A a, B b)`.


 Good point. It's been discussed but rejected because druntime generally
 shuns templates. I think that resistance is mostly vestigial by now.


It needs to happen as part of getting opEquals and friends off of Object,
but a Win32 compiler bug is currently preventing it from happening:

https://github.com/D-Programming-Language/druntime/pull/459
https://issues.dlang.org/show_bug.cgi?id=12537

Unfortunately, none of the compiler devs seem to have taken any notice of
it, and I haven't had the time or expertise to figure it out myself.
Otherwise, it probably would have been templatize before the last dconf.

- Jonathan M Davis
Jan 04 2015
prev sibling parent reply Martin Nowak <code+news.digitalmars dawg.eu> writes:
On 01/04/2015 04:23 AM, anonymous wrote:

 I see one fundamental source of overhead: The types degenerate to
 Object, resulting in virtual calls that could be avoided. Maybe it'd be
 worthwhile to templatize object.opEquals: `bool opEquals(A, B)(A a, B b)`.


+1 definitely makes sense, can you file an enhancement request

https://issues.dlang.org
Jan 03 2015
next sibling parent reply Martin Nowak <code+news.digitalmars dawg.eu> writes:
On 01/04/2015 06:16 AM, Martin Nowak wrote:

 +1 definitely makes sense, can you file an enhancement request


It requires a `final bool opEquals(SameClass other)` method to avoid the 
virtual call.
Jan 03 2015
parent reply "anonymous" <anonymous example.com> writes:
On Sunday, 4 January 2015 at 05:24:09 UTC, Martin Nowak wrote:

 It requires a `final bool opEquals(SameClass other)` method to 
 avoid the virtual call.


`final bool opEquals(Object)` is enough, no?
Jan 04 2015
parent reply "Martin Nowak" <code dawg.eu> writes:
On Sunday, 4 January 2015 at 15:02:39 UTC, anonymous wrote:

 On Sunday, 4 January 2015 at 05:24:09 UTC, Martin Nowak wrote:

 It requires a `final bool opEquals(SameClass other)` method to 
 avoid the virtual call.


 `final bool opEquals(Object)` is enough, no?


No, then you'd still need a dynamic cast for the argument.
Jan 04 2015
parent "anonymous" <anonymous example.com> writes:
On Sunday, 4 January 2015 at 15:15:09 UTC, Martin Nowak wrote:

 On Sunday, 4 January 2015 at 15:02:39 UTC, anonymous wrote:

 On Sunday, 4 January 2015 at 05:24:09 UTC, Martin Nowak wrote:

 It requires a `final bool opEquals(SameClass other)` method 
 to avoid the virtual call.


 `final bool opEquals(Object)` is enough, no?


 No, then you'd still need a dynamic cast for the argument.


Sure, but the method call doesn't need to be virtual. As far as I 
understand, they're independent issues.

bool opEquals(Object)           virtual call, dynamic cast
final bool opEquals(Object)     possibly non-virtual call, 
dynamic cast
bool opEquals(SameClass)        virtual call, no cast
final bool opEquals(SameClass)  possibly non-virtual call, no cast
Jan 04 2015
prev sibling next sibling parent "Daniel Murphy" <yebbliesnospam gmail.com> writes:
"Martin Nowak"  wrote in message news:m8aicl$jkt$1 digitalmars.com...


 On 01/04/2015 04:23 AM, anonymous wrote:

 I see one fundamental source of overhead: The types degenerate to
 Object, resulting in virtual calls that could be avoided. Maybe it'd be
 worthwhile to templatize object.opEquals: `bool opEquals(A, B)(A a, B 
 b)`.


 +1 definitely makes sense, can you file an enhancement request


It would be nice if the inliner+optimizer could do this for us.
Jan 03 2015
prev sibling parent "anonymous" <anonymous example.com> writes:
On Sunday, 4 January 2015 at 05:17:10 UTC, Martin Nowak wrote:

 +1 definitely makes sense, can you file an enhancement request

 https://issues.dlang.org


https://issues.dlang.org/show_bug.cgi?id=13933
Jan 04 2015