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

[Ivan Lazar Miljenovic]

On 20 August 2014 19:05, Johan Holmquist <holmisen 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.
>
> 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 <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
>>
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>



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