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?

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

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

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

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

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

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.

"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. 

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

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.