[Haskell-cafe] Optimizing Eq instances with reallyUnsafePtrEquality#

[Simon Jakobi]

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.