Predef.hash and inlining

On Mon, Nov 9, 2009 at 1:39 PM, Paul Phillips wrote:
> Very pleased to see Predef.hash and equals "like you mean it" in recent
> checkin.  I couldn't sleep last night so I implemented a whole equal
> hash codes for equal values scheme, but my integration approach could
> only be described as "the hard way" compared to this:
>
>  @inline def hash(x: Any): Int =
>    if (x.isInstanceOf[Number]) (x.asInstanceOf[Number]).intValue
>    else x.hashCode
>
Yes, but unfortunately it cuts off some hash bits. So in my last
checkin I did some refinement where hash forwards to numHash in
BoxesRuntime, which does some checks to get a better distribution of
bits. Let me know what you think of it.

> Are we at a point where we can implement methods like this and count on
> the optimizer to the necessary job? That would be great news.  Mailing
> list readers may wish to contrast this example logic:
>
>  if (l eq null) true else l.equals(null)
>
> with this implementation of that logic:
>
>  ctx1.bb.emitOnly(
>    DUP(ANY_REF_CLASS),
>    STORE_LOCAL(eqEqTempLocal) setPos l.pos,
>    CZJUMP(thenCtx.bb, nonNullCtx.bb, EQ, ANY_REF_CLASS)
>  )
>  nonNullCtx.bb.emitOnly(
>    LOAD_LOCAL(eqEqTempLocal) setPos l.pos,
>    CONSTANT(Constant(null)) setPos r.pos,
>    CALL_METHOD(Object_equals, Dynamic),
>    CZJUMP(thenCtx.bb, elseCtx.bb, NE, BOOL)
>  )
>
> to see why I think @inline is a bit more maintainable.
>
I don't know about the details, and also don't know about how seamless
is the plumbiong with inlined methods. Iulian should be able to tell.

Cheers

On Mon, Nov 09, 2009 at 01:48:52PM +0100, martin odersky wrote:
> Yes, but unfortunately it cuts off some hash bits. So in my last
> checkin I did some refinement where hash forwards to numHash in
> BoxesRuntime, which does some checks to get a better distribution of
> bits. Let me know what you think of it.

That looks a lot more like what I had, which is enclosed below. One
thing I found the last time I went down this road is that there was
quite a performance gain to taking full advantage of the static type if
I knew it. That's why I used to have individual methods for every
variation of equals, like equalsFloatDouble(x: Float, y: Double).

public static int hashFromLong(Long a) {
if (a.longValue() == a.intValue()) return Integer.valueOf(a.intValue()).hashCode();
else return a.hashCode();
}
public static int hashFromFloat(Float a) {
if (a.floatValue() == a.intValue()) return Integer.valueOf(a.intValue()).hashCode();
if (a.floatValue() == a.longValue()) return Long.valueOf(a.longValue()).hashCode();
if (a.floatValue() == a.doubleValue()) return Double.valueOf(a.doubleValue()).hashCode();
else return a.hashCode();
}
public static int hashFromDouble(Double a) {
if (a.doubleValue() == a.intValue()) return Integer.valueOf(a.intValue()).hashCode();
if (a.doubleValue() == a.longValue()) return Long.valueOf(a.longValue()).hashCode();
else return a.hashCode();
}
public static int hashFromObject(Object a) {
if (a instanceof Long) return hashFromLong((Long)a);
else if (a instanceof Float) return hashFromFloat((Float)a);
else if (a instanceof Double) return hashFromDouble((Double)a);
else return a.hashCode();
}

On Mon, Nov 9, 2009 at 2:01 PM, Paul Phillips wrote:
> On Mon, Nov 09, 2009 at 01:48:52PM +0100, martin odersky wrote:
>> Yes, but unfortunately it cuts off some hash bits. So in my last
>> checkin I did some refinement where hash forwards to numHash in
>> BoxesRuntime, which does some checks to get a better distribution of
>> bits. Let me know what you think of it.
>
> That looks a lot more like what I had, which is enclosed below.  One
> thing I found the last time I went down this road is that there was
> quite a performance gain to taking full advantage of the static type if
> I knew it.  That's why I used to have individual methods for every
> variation of equals, like equalsFloatDouble(x: Float, y: Double).
>
>    public static int hashFromLong(Long a) {
>      if (a.longValue() == a.intValue()) return Integer.valueOf(a.intValue()).hashCode();
>      else return a.hashCode();
>    }
>    public static int hashFromFloat(Float a) {
>      if (a.floatValue() == a.intValue()) return Integer.valueOf(a.intValue()).hashCode();
>      if (a.floatValue() == a.longValue()) return Long.valueOf(a.longValue()).hashCode();
>      if (a.floatValue() == a.doubleValue()) return Double.valueOf(a.doubleValue()).hashCode();
>      else return a.hashCode();
>    }
>    public static int hashFromDouble(Double a) {
>      if (a.doubleValue() == a.intValue()) return Integer.valueOf(a.intValue()).hashCode();
>      if (a.doubleValue() == a.longValue()) return Long.valueOf(a.longValue()).hashCode();
>      else return a.hashCode();
>    }
>    public static int hashFromObject(Object a) {
>      if (a instanceof Long) return hashFromLong((Long)a);
>      else if (a instanceof Float) return hashFromFloat((Float)a);
>      else if (a instanceof Double) return hashFromDouble((Double)a);
>      else return a.hashCode();
>    }
>
That looks indeed very similar. If you think the split helps
peformance, please fell free to update!

Cheers

On Mon, Nov 9, 2009 at 2:11 PM, Jesper Nordenberg wrote:

On Mon, Nov 09, 2009 at 05:11:33AM -0800, Jesper Nordenberg wrote:
> > variation of equals, like equalsFloatDouble(x: Float, y:
> > Double).
>
> Preferably @specialize optimized code should call a specialized
> hash/equal function directly. Can this be done by overloading the
> functions?

The reason I didn't overload the type specific equals methods is that I
hadn't figured out how to deal with them internally. The problem is
that when you overload like that, the compiler sees the method as having
an OverloadedType, but in normal operation these are eliminated long
before the point at which I needed to call the methods in BoxesRunTime.
I could probably figure out how to make it work now, but at the time it
was easy enough to simply generate unique names, and since only robots
would be calling those methods I wasn't sweating it.

On Mon, Nov 9, 2009 at 1:48 PM, martin odersky <martin.odersky@epfl.ch> wrote:

On Mon, Nov 9, 2009 at 1:39 PM, Paul Phillips <paulp@improving.org> wrote:
> Very pleased to see Predef.hash and equals "like you mean it" in recent
> checkin.  I couldn't sleep last night so I implemented a whole equal
> hash codes for equal values scheme, but my integration approach could
> only be described as "the hard way" compared to this:
>
>  @inline def hash(x: Any): Int =
>    if (x.isInstanceOf[Number]) (x.asInstanceOf[Number]).intValue
>    else x.hashCode
>
Yes, but unfortunately it cuts off some hash bits. So in my last
checkin I did some refinement where hash forwards to numHash in
BoxesRuntime, which does some checks to get a better distribution of
bits. Let me know what you think of it.

> Are we at a point where we can implement methods like this and count on
> the optimizer to the necessary job? That would be great news.  Mailing
> list readers may wish to contrast this example logic:
>
>  if (l eq null) true else l.equals(null)
>
> with this implementation of that logic:
>
>  ctx1.bb.emitOnly(
>    DUP(ANY_REF_CLASS),
>    STORE_LOCAL(eqEqTempLocal) setPos l.pos,
>    CZJUMP(thenCtx.bb, nonNullCtx.bb, EQ, ANY_REF_CLASS)
>  )
>  nonNullCtx.bb.emitOnly(
>    LOAD_LOCAL(eqEqTempLocal) setPos l.pos,
>    CONSTANT(Constant(null)) setPos r.pos,
>    CALL_METHOD(Object_equals, Dynamic),
>    CZJUMP(thenCtx.bb, elseCtx.bb, NE, BOOL)
>  )
>
> to see why I think @inline <scala code here> is a bit more maintainable.
>
I don't know about the details, and also don't know about how seamless
is the plumbiong with inlined methods. Iulian should be able to tell.

A method marked @inline will override the optimizer's heuristic about when it's a good idea to inline, and just go for it. However, it won't inline a method when it's not safe to do so: for instance, when the method is not final, or it uses private members.
 
I agree that relying on the inliner is nicer. That code was written (long) before there was an optimizer. The only argument in its favor is that the 'efficient' bytecode is generated even when -optimize is off. But that's a weak argument, given the recent changes in equality, and that my simple tests didn't reveal a conclusive improvement after inlining 'ScalaRunTime.inlinedEquals'.

iulian

Cheers