To summarise, the points raised sofar against this optimisation are, roughly, as follows.


* More expensive to compare two values which aren't equal.

I think the potential gain of the optimisation might outweigh the cost in the general case.

(Also, the optimisation would not have to be triggered for simple values like Char, Int and Double.)


* Dodgy Eq instances may break the optimisation

But may also break other stuff and should be avoided anyway.


* _|_ will not necessarily yield _|_ on comparison

This seems the biggest problem sofar to me, that (5,_|_) == (5,_|_) would be _|_ if both pairs where at different memory locations and True otherwise. But perhaps not a big deal in practice.


* Disrupts other compiler optimisation opportunities

My knowledge about compilers is lacking so I cannot comment this.


Interesting that this was implemented by hbc. Would be nice to know if it led to problems.



2014-08-20 14:32 GMT+02:00 Jan-Willem Maessen <jmaessen@alum.mit.edu>:
On Wed, Aug 20, 2014 at 2:52 AM, Johan Holmquist <holmisen@gmail.com> wrote:

Comparing two structures for equality (structurally) can be expensive. But if their references are the same they would for sure be equal (unless (==) was defined in some funny way). Does GHC perform any such optimization?


The big problem in practice are the Float / Double instances in the presence of NaN, as noted by other folks.

Back in the day, hbc had a flag that would do a pointer equality check in the derived Eq instances it generated before falling back to a traversal.  Interestingly, it does actually change the way you think about programming when you're working with multiple values that are very likely to share sub-structure.  Suddenly it seems OK to do equality checks as you traverse (because most of them will succeed), which would be O(n^2) if you weren't doing the pointer test.

-Jan-Willem Maessen
 

(Likely a question for another list but I make a stab here first. )


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