[Haskell-cafe] Does GHC compare pointers when eval'ing (==)

[Johan Holmquist]

> As I understood, the question was if GHC would first compare pointers,
and only call the Eq instance if the pointers are not equal.

Yes, spot on!

> 1. An Eq instance that doesn't obey the reflective property (not
recommended):

And this is what I mean with "defined in some funny way". One could
consider this optimization(?) only to kick in when GHC generates the
instance definition by means of the deriving mechanism. That should be
safe(?).

> I think the reason it isn't done is that it's not always an optimization

Could you explain when it's not?


Clarification:

Consider the following:

    let xs = [1..1000] in xs == xs

xs would surely be equal but generally finding out if two lists are equal
amounts to comparing each element. If the compiler was first to check if
the objects referenced where the same, it should safely be able to yield
True without further evaluation. (In this particular example the compiler
may make other optimizations but it gives the general idea.)

Ofcourse `let x = undefined in x == x` might be considered bad to optimize
to True but maybe this could be checked somehow...





2014-08-20 10:35 GMT+02:00 Michael Snoyman <michael at snoyman.com>:

>
>
>
> On Wed, Aug 20, 2014 at 11:28 AM, Johan Tibell <johan.tibell at gmail.com>
> wrote:
>
>> On Wed, Aug 20, 2014 at 10:23 AM, Erik Hesselink <hesselink at gmail.com>
>> wrote:
>>
>>> As I understood, the question was if GHC would first compare pointers,
>>> and only call the Eq instance if the pointers are not equal. I guess
>>> this would be safe, but I don't think GHC does such a thing.
>>
>>
>> I think the reason it isn't done is that it's not always an optimization.
>> We do it manually in e.g. bytestring.
>>
>>
>>
> There are two cases I can think of where it would also change the
> semantics of the code:
>
> 1. An Eq instance that doesn't obey the reflective property (not
> recommended):
>
> data BadEq = BadEq
> instance Eq BadEq where
>     BadEq == BadEq = False
>
> 2. Eq instances intended to avoid timing attacks, by always comparing the
> entire data structure.
>
> newtype SlowEq a = SlowEq [a]
> instance Eq a => Eq (SlowEq a) where
>     SlowEq x == SlowEq y = slowAnd $ length x == length y : zipWith (==) x
> y
>
> slowAnd =
>     loop True
>   where
>     loop !x [] = x
>     loop !x (!y:ys) = loop (x && y) ys
>
> (Note: not actually tested.) It's difficult for me to imagine a case
> though where a timing attack could result on two data structures sharing
> the same pointer; usually we'd be talking about comparing two ByteStrings
> or Texts that come from very different sources.
>
> Michael
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20140820/40ac2877/attachment.html>