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

On 20 August 2014 19:05, Johan Holmquist 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.

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(?).

Unless deep down a value is used that _does_ have a dodgy custom derived Eq instance.

...

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 :

...

On Wed, Aug 20, 2014 at 11:28 AM, Johan Tibell wrote:

...

On Wed, Aug 20, 2014 at 10:23 AM, Erik Hesselink 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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Ivan Lazar Miljenovic Ivan.Miljenovic@gmail.com http://IvanMiljenovic.wordpress.com