[Haskell-cafe] Optimizing Eq instances with reallyUnsafePtrEquality#

Fri Jun 11 14:35:20 UTC 2021

As far as I'm concerned, nonreflexive instances are not supported by
`containers` at all. If your == isn't reflexive, you just need to assume
that anything with an Eq constraint might behave arbitrarily badly.

On Fri, Jun 11, 2021, 10:27 AM Simon Jakobi via Haskell-Cafe <
haskell-cafe at haskell.org> wrote:

> Thanks for the feedback everyone! :)
>
> The gist I get is that using pointer equality is not free, but it can
> make sense when
>
> 1. two objects are particularly likely to be the same;
> 2. establishing equality by other means (e.g. structural equality) is
> particularly expensive
>
> The usecases I now have in mind are:
>
> * Lookups in unordered-containers: Since keys are only ==-d when their
> hashes are equal, it seems that the likelihood that they are in fact
> the same object should be fairly good. I think we can ignore the issue
> of irreflexive instances here, because the lookup logic already
> requires reflexivity.
>
> * The Eq instances of containers' Set and IntSet types and of HashSet
> from unordered-containers. These instances seem particularly
> expensive, and Set and HashSet already require reflexivity. I don't
> think we can apply the same optimizations to the Eq instances of the
> various Map types, because we might run into irreflexive values there.
>
> * Eq for lazy ByteStrings – another expensive instance. The instance
> for strict ByteStrings already makes use of pointer equality.
>
> Cheers,
> Simon
>
>
>
>
>
>
>
>
> Am Di., 8. Juni 2021 um 18:51 Uhr schrieb Sebastiaan Joosten
> <sjcjoosten+haskell at gmail.com>:
> >
> > 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.
> >
> > _______________________________________________
> > 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.
> _______________________________________________
> 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/20210611/6127f31a/attachment.html>