[Haskell-cafe] Optimizing Eq instances with reallyUnsafePtrEquality#

[Sebastiaan Joosten]

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 at 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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20210608/bf078cad/attachment.html>