[Haskell-cafe] Optimizing Eq instances with reallyUnsafePtrEquality#
david.feuer at gmail.com
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.
> Am Di., 8. Juni 2021 um 18:51 Uhr schrieb Sebastiaan Joosten
> <sjcjoosten+haskell at gmail.com>:
> > The containers library uses this trick:
> > It mentions the useful hint to evaluate the arguments to WHNF before
> calling PtrEquality.
> > The function ptrEq is used here (for instance):
> > 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:
> > 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
> > 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:
> > The equality test:
> > And there is of course a function to create a 'normed object':
> > 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>
> >> Am 08.06.21 um 16:25 schrieb Simon Jakobi via Haskell-Cafe:
> >> > Hi everyone!
> >> >
> >> > In
> >> > 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:
> Only members subscribed via the mailman list are allowed to post.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe