- About Scala
- Documentation
- Code Examples
- Software
- Scala Developers
more on national security.
Fri, 2009-11-06, 17:32
Hi Paul,
Your example made me think some more. Let's weigh the issues again,
between what's currently in spec and what's currently implemented:
For the spec:
- It's simpler to spec.
- It's faster.
- It does not violate the equals hashcode contract.
For the current implementation:
- It is insensitive to type widening.
For me the equals/hashcode problem was the most serious issue. But on
second thought that problem only affects floats and doubles, right? I
mean, the hashCodes of equal Byte/Short/Char/Int/Long numbers are
always equal, right? In that case I believe
we do not have that serious a problem in the end. Anybody putting
doubles or floats in a hashtable deserves to be burnt. So maybe we can
just spec that the equals/hashCode contract is broken for floats and
doubles when compared with numbers of different types, and that these
things should in any case never be stored in hashtables.
If that's the case, (please correct me if I'm wrong), it seems the
tips of the scale lower to the current implementation. Insensitivity
to type widening is an important property. It warrants some
complications in the spec. It would also warrant some minor slow-down,
but the slowdown must be really small (say, less than 1% on typical
codes). The fastest way I know to express BoxesRuntime.equals is like
this:
def equals(x: AnyRef, y: AnyRef) = {
if (x eq null) return y eq null
if (x.isInstanceOf[Number] || x.isInstanceOf[Character]) return
numEquals(x, y)
x.equals(y)
}
(Note that numEquals can be slow, as it would only be called for
numbers of static type Any or AnyVal)
Unfortunately, this is 40 bytes, which makes it not that likely to be
inlined by the JVM. On the other hand, the optimizer might inline it.
Can we try this with -optimize? If this method gets inlined it would
be only two instanceofs in addition to the spec scheme, which should
be no big deal.
Paul, can you comment on this? Are there points I have overlooked?
If not, would you be happy to put this scheme into place? I intended
to ask you to please remove all the various choices of equality that
you have added, because that makes it easier for me to fiddle with the
previous status quo. But it might be that you like this proposition
well enough to implement it yourself :-) ?
Cheers
Fri, 2009-11-06, 19:07
#2
Re: more on national security.
On Fri, Nov 6, 2009 at 6:18 PM, Paul Phillips wrote:
> On Fri, Nov 06, 2009 at 05:31:45PM +0100, martin odersky wrote:
>> For me the equals/hashcode problem was the most serious issue. But on
>> second thought that problem only affects floats and doubles, right?
>
> Unfortunately that's only true up to Int. Long hashCodes are equal for
> nonnegative values, but not negative. I have to think about things to
> say any more than that.
>
Yuck! That's the most brain dead thing I have seen in a long time. Why
oh why did they do that?
Fri, 2009-11-06, 19:17
#3
Re: Re: more on national security.
On Fri, 2009-11-06 at 18:59 +0100, martin odersky wrote:
> Yuck! That's the most brain dead thing I have seen in a long time. Why oh why did they do that?
Since new Long(50).equals(new Integer(50)) == false anyway, I am
guessing that they just went with something cheap to compute and didn't
think much of it:
(int)(value ^ (value >>> 32));
The main mistake is the equality part, the hashCode part just follows
from that.
Best,
Ismael
Sat, 2009-11-07, 18:27
#4
Re: Re: more on national security.
OK, so how about biting the bullet and also special-ascing hashCode,
i.e. inlined:
if (x.isInstanceOf[Long]) longHashCode(x.asInstanceOf[Long])
else x.hashCode
where
def longHashCode(l: Long) = {
if (l.longValue == l.intValue) l.intValue
else super.hashCode
}
It's ugly, but so are the alternatives.
Cheers
Sat, 2009-11-07, 18:37
#5
Re: Re: more on national security.
On Sat, Nov 07, 2009 at 06:17:42PM +0100, martin odersky wrote:
> OK, so how about biting the bullet and also special-ascing hashCode,
> i.e. inlined:
>
> if (x.isInstanceOf[Long]) longHashCode(x.asInstanceOf[Long])
> else x.hashCode
Now we're talking! All options on the table! If we are willing to invade
HashCodeLandia then the combat space takes on a whole new shape. I
think the boxed types could be made to behave just like the primitives,
not just with Long but across the board, and guarantee equal hashcodes
for equal values. Unfortunately I have to go right now but if you're
open on this front I would love to take another bite at the enchilada.
Sat, 2009-11-07, 23:27
#6
Re: Re: more on national security.
Sat, 2009-11-07, 23:37
#7
Re: Re: more on national security.
On Sat, Nov 7, 2009 at 11:17 PM, Jesper Nordenberg <megagurka@yahoo.com> wrote:
--- On Sat, 11/7/09, martin odersky <martin.odersky@epfl.ch> wrote:
> OK, so how about biting the bullet
> and also special-ascing hashCode,
> i.e. inlined:
>
> if (x.isInstanceOf[Long])
> longHashCode(x.asInstanceOf[Long])
> else x.hashCode
>
> where
>
> def longHashCode(l: Long) = {
> if (l.longValue == l.intValue)
> l.intValue
> else super.hashCode
> }
>
> It's ugly, but so are the alternatives.
This looks very similar to what I suggested a couple of weeks ago (and Martin dismissed). You put this stuff in a hash code function in Predef and all Scala code that uses == should use this function instead of x.hashCode. Somehow magically transforming x.hashCode to something else at compile time sounds like a bad idea.
Java collections will still use equals() and hashCode(), but there's nothing we can do about that.
You mean besides hooking into the system classloader and rewrite them on load? ;)
/Jesper Nordenberg
--
Viktor Klang
| "A complex system that works is invariably
| found to have evolved from a simple system
| that worked." - John Gall
Blog: klangism.blogspot.com
Twttr: twitter.com/viktorklang
Code: github.com/viktorklang
Sun, 2009-11-08, 00:07
#8
Re: Re: more on national security.
Sun, 2009-11-08, 00:57
#9
Re: Re: more on national security.
On Saturday November 7 2009, Jesper Nordenberg wrote:
Sun, 2009-11-08, 09:47
#10
Re: Re: more on national security.
Mon, 2009-11-09, 00:57
#11
Re: Re: more on national security.
as an aside, what would F# do?http://blogs.msdn.com/dsyme/archive/2009/11/08/equality-and-comparison-constraints-in-f-1-9-7.aspx
adriaan
On Sun, Nov 8, 2009 at 9:40 AM, Jesper Nordenberg <megagurka@yahoo.com> wrote:
adriaan
On Sun, Nov 8, 2009 at 9:40 AM, Jesper Nordenberg <megagurka@yahoo.com> wrote:
--- On Sun, 11/8/09, Randall R Schulz <rschulz@sonic.net> wrote:
> If I get the point of this, shouldn't Hasher encapsulate
> both hashing
> and equality testing? They are expected to obey a
> congruency contract,
> right?
Yes, that might be a good idea, although for each equality function there is a huge number of valid hash functions and the same hash function can be consistent with multiple equality functions.
/Jesper Nordenberg
Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm
On Fri, Nov 06, 2009 at 05:31:45PM +0100, martin odersky wrote:
> For me the equals/hashcode problem was the most serious issue. But on
> second thought that problem only affects floats and doubles, right?
Unfortunately that's only true up to Int. Long hashCodes are equal for
nonnegative values, but not negative. I have to think about things to
say any more than that.