<div dir="ltr"><div class="gmail-AppleOriginalContents" style="direction:ltr">The containers library uses this trick:</div><div class="gmail-AppleOriginalContents" style="direction:ltr"><a href="https://github.com/haskell/containers/blob/30ccbaa201043109bf1ee905c66ccd0dbe24422f/containers/src/Utils/Containers/Internal/PtrEquality.hs">https://github.com/haskell/containers/blob/30ccbaa201043109bf1ee905c66ccd0dbe24422f/containers/src/Utils/Containers/Internal/PtrEquality.hs</a></div><div class="gmail-AppleOriginalContents" style="direction:ltr">It mentions the useful hint to evaluate the arguments to WHNF before calling PtrEquality.</div><div class="gmail-AppleOriginalContents" style="direction:ltr">The function ptrEq is used here (for instance):</div><div class="gmail-AppleOriginalContents" style="direction:ltr"><a href="https://github.com/haskell/containers/blob/30ccbaa201043109bf1ee905c66ccd0dbe24422f/containers/src/Data/Set/Internal.hs#L532">https://github.com/haskell/containers/blob/30ccbaa201043109bf1ee905c66ccd0dbe24422f/containers/src/Data/Set/Internal.hs#L532</a></div><div class="gmail-AppleOriginalContents" style="direction:ltr">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.</div><div class="gmail-AppleOriginalContents" style="direction:ltr">Surprisingly enough (at least to me) ptrEq is not used in the Eq instance there:</div><div class="gmail-AppleOriginalContents" style="direction:ltr"><a href="https://github.com/haskell/containers/blob/30ccbaa201043109bf1ee905c66ccd0dbe24422f/containers/src/Data/Set/Internal.hs#L1141">https://github.com/haskell/containers/blob/30ccbaa201043109bf1ee905c66ccd0dbe24422f/containers/src/Data/Set/Internal.hs#L1141</a></div><div class="gmail-AppleOriginalContents" style="direction:ltr"><br></div><div class="gmail-AppleOriginalContents" style="direction:ltr">Outside of GHC, there are some (pure) languages that extensively make use of this principle and it's too cool not to mention:</div><div class="gmail-AppleOriginalContents" style="direction:ltr"><span style="color:rgb(0,0,0);font-family:Helvetica;font-size:12px">The programming language Elm does this in its generated code (at least when generating JavaScript): <a href="https://github.com/elm/compiler/">https://github.com/elm/compiler/</a></span><div class="gmail-AppleOriginalContents" style="color:rgb(0,0,0);font-family:Helvetica;font-size:12px;direction:ltr">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. <span style="font-family:Arial,Helvetica,sans-serif;font-size:small;color:rgb(34,34,34)">The point of using HONS in ACL2 is to </span><i style="font-family:Arial,Helvetica,sans-serif;font-size:small;color:rgb(34,34,34)">only</i><span class="gmail-Apple-converted-space" style="font-family:Arial,Helvetica,sans-serif;font-size:small;color:rgb(34,34,34)"> </span><span style="font-family:Arial,Helvetica,sans-serif;font-size:small;color:rgb(34,34,34)">perform pointer comparison, without needing to do any other equality check.</span></div><div class="gmail-AppleOriginalContents" style="color:rgb(0,0,0);font-family:Helvetica;font-size:12px;direction:ltr">General background information: <a href="https://www.cs.utexas.edu/~ragerdl/acl2-manual/index.html?topic=ACL2____HONS-AND-MEMOIZATION">https://www.cs.utexas.edu/~ragerdl/acl2-manual/index.html?topic=ACL2____HONS-AND-MEMOIZATION</a></div><div class="gmail-AppleOriginalContents" style="color:rgb(0,0,0);font-family:Helvetica;font-size:12px;direction:ltr">The equality test: <a href="https://www.cs.utexas.edu/users/moore/acl2/manuals/current/manual/index-seo.php/ACL2____HONS-EQUAL">https://www.cs.utexas.edu/users/moore/acl2/manuals/current/manual/index-seo.php/ACL2____HONS-EQUAL</a></div><div class="gmail-AppleOriginalContents" style="color:rgb(0,0,0);font-family:Helvetica;font-size:12px;direction:ltr">And there is of course a function to create a 'normed object': <a href="https://www.cs.utexas.edu/users/moore/acl2/manuals/current/manual/index-seo.php/ACL2____HONS-COPY">https://www.cs.utexas.edu/users/moore/acl2/manuals/current/manual/index-seo.php/ACL2____HONS-COPY</a></div><div class="gmail-AppleOriginalContents" style="color:rgb(0,0,0);font-family:Helvetica;font-size:12px;direction:ltr">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).</div></div><br class="gmail-Apple-interchange-newline"><div>Hope this helps.</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, Jun 8, 2021 at 10:47 AM Joachim Durchholz <<a href="mailto:jo@durchholz.org">jo@durchholz.org</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Am 08.06.21 um 16:25 schrieb Simon Jakobi via Haskell-Cafe:<br>
> Hi everyone!<br>
> <br>
> In <a href="https://github.com/haskell-unordered-containers/unordered-containers/issues/77" rel="noreferrer" target="_blank">https://github.com/haskell-unordered-containers/unordered-containers/issues/77</a><br>
> we're wondering whether certain Eq instances, for example record types<br>
> or strings, could be optimized by including a pointer equality check<br>
> that detects when an object is compared with itself.<br>
<br>
You have to be aware that the pointer comparison itself does not come <br>
for free. Execution prediction means that the "happy path" may be so <br>
rare it's not loaded into the CPU cache and you might end with a slower <br>
system - the case is somewhat pathological but not so rare that you can <br>
just assume that it will not happen to you.<br>
A lot also depends on whether the data to be compared needs to be loaded <br>
anyway. If yes, the pointer comparison won't give you any gains, it will <br>
be just one instruction more to execute, creating more execution unit <br>
contention inside the CPU. If no, then obviously the pointer comparison <br>
will help.<br>
<br>
In the end, you need to benchmark to see if it helps you.<br>
And you cannot usefully benchmark unless you have also nailed down all <br>
performance-relevant compiler and runtime options, which you do only if <br>
you have exhausted all other optimization possibilities.<br>
<br>
IOW if it complicates your code, don't do it - unless you are already <br>
long past the point where code reusability has taken a back seat to raw <br>
optimization.<br>
<br>
Regards,<br>
Jo<br>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
To (un)subscribe, modify options or view archives go to:<br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a><br>
Only members subscribed via the mailman list are allowed to post.</blockquote></div>