The containers library uses this trick:
https://github.com/haskell/containers/blob/30ccbaa201043109bf1ee905c66ccd0dbe24422f/containers/src/Utils/Containers/Internal/PtrEquality.hs
It mentions the useful hint to evaluate the arguments to WHNF before calling PtrEquality.
The function ptrEq is used here (for instance):
https://github.com/haskell/containers/blob/30ccbaa201043109bf1ee905c66ccd0dbe24422f/containers/src/Data/Set/Internal.hs#L532
The places where ptrEq is used in that file, its purpose seems to be to reduce memory by reusing existing data-structures, which I suppose also helps with performance.
Surprisingly enough (at least to me) ptrEq is not used in the Eq instance there:
https://github.com/haskell/containers/blob/30ccbaa201043109bf1ee905c66ccd0dbe24422f/containers/src/Data/Set/Internal.hs#L1141

Outside of GHC, there are some (pure) languages that extensively make use of this principle and it's too cool not to mention:
The programming language Elm does this in its generated code (at least when generating JavaScript): https://github.com/elm/compiler/
The theorem proving environment ACL2 uses this principle for memoizing functions, fast 'Map's ('dictionaries' in python lingo, 'alist' or association-list in ACL2 lingo), as well as fast equality. As a LISP dialect, all data-structures are pairs (called CONS). In ACL2, the function 'HONS' (hashed CONS) will construct a pair if it does not already exist, and otherwise it returns a pointer to the already existing object. The point of using HONS in ACL2 is to only perform pointer comparison, without needing to do any other equality check.
General background information: https://www.cs.utexas.edu/~ragerdl/acl2-manual/index.html?topic=ACL2____HONS-AND-MEMOIZATION
The equality test: https://www.cs.utexas.edu/users/moore/acl2/manuals/current/manual/index-seo.php/ACL2____HONS-EQUAL
And there is of course a function to create a 'normed object': https://www.cs.utexas.edu/users/moore/acl2/manuals/current/manual/index-seo.php/ACL2____HONS-COPY
Note that the ACL2 approach only works because it is supported by the run time system (the implementation needs to access 'all data in memory') so it won't work in Haskell (assuming you're not writing your own RTS).

Hope this helps.

On Tue, Jun 8, 2021 at 10:47 AM Joachim Durchholz <jo@durchholz.org> wrote:
Am 08.06.21 um 16:25 schrieb Simon Jakobi via Haskell-Cafe:
> Hi everyone!
>
> In https://github.com/haskell-unordered-containers/unordered-containers/issues/77
> we're wondering whether certain Eq instances, for example record types
> or strings, could be optimized by including a pointer equality check
> that detects when an object is compared with itself.

You have to be aware that the pointer comparison itself does not come
for free. Execution prediction means that the "happy path" may be so
rare it's not loaded into the CPU cache and you might end with a slower
system - the case is somewhat pathological but not so rare that you can
just assume that it will not happen to you.
A lot also depends on whether the data to be compared needs to be loaded
anyway. If yes, the pointer comparison won't give you any gains, it will
be just one instruction more to execute, creating more execution unit
contention inside the CPU. If no, then obviously the pointer comparison
will help.

In the end, you need to benchmark to see if it helps you.
And you cannot usefully benchmark unless you have also nailed down all
performance-relevant compiler and runtime options, which you do only if
you have exhausted all other optimization possibilities.

IOW if it complicates your code, don't do it - unless you are already
long past the point where code reusability has taken a back seat to raw
optimization.

Regards,
Jo
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.