The containers library uses this trick: https://github.com/haskell/containers/blob/30ccbaa201043109bf1ee905c66ccd0db... 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/30ccbaa201043109bf1ee905c66ccd0db... 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/30ccbaa201043109bf1ee905c66ccd0db... 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... The equality test: https://www.cs.utexas.edu/users/moore/acl2/manuals/current/manual/index-seo.... 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.... 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 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/... 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.

(CC'ing the libraries list again) Am Fr., 11. Juni 2021 um 16:26 Uhr schrieb 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 :

...

The containers library uses this trick: https://github.com/haskell/containers/blob/30ccbaa201043109bf1ee905c66ccd0db... 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/30ccbaa201043109bf1ee905c66ccd0db... 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/30ccbaa201043109bf1ee905c66ccd0db...

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... The equality test: https://www.cs.utexas.edu/users/moore/acl2/manuals/current/manual/index-seo.... 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.... 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 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/... 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.

Yup! ;) Filter your floats for nans! On Fri, Jun 11, 2021 at 10:38 AM David Feuer 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@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 :

...

The containers library uses this trick:

https://github.com/haskell/containers/blob/30ccbaa201043109bf1ee905c66ccd0db...

...

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/30ccbaa201043109bf1ee905c66ccd0db...

...

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/30ccbaa201043109bf1ee905c66ccd0db...

...

Outside of GHC, there are some (pure) languages that extensively make

...

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

use of this principle and it's too cool not to mention: 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... The equality test: https://www.cs.utexas.edu/users/moore/acl2/manuals/current/manual/index-seo.... 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.... 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 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/...

...

...

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.