[Haskell-cafe] Optimizing Eq instances with reallyUnsafePtrEquality#

Fri Jun 11 22:04:32 UTC 2021

Yup!

;)
Filter your floats for nans!

On Fri, Jun 11, 2021 at 10:38 AM David Feuer <david.feuer at gmail.com> wrote:

> 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.
>
> _______________________________________________
> 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/62ec44ee/attachment.html>