Use pointer equality when comparing keys

[tibbe]

We should use pointer equality to shortcut == comparisons on keys, as it's much cheaper in the case of a match.

[sjakobi]

I wonder whether this optimization shouldn't be better left to the Eq instances. It probably makes a lot of sense for, say, string types and records, but not so much for Ints and simple enums. Perhaps it's something that GHC could do when deriving Eq instances?!

[treeowl]

I think I agree, though it might make sense to use rewrite rules to make it happen for, e.g., String.

…

On Sat, May 29, 2021, 10:45 AM Simon Jakobi ***@***.***> wrote: I wonder whether this optimization shouldn't be better left to the Eq instances. It probably makes a lot of sense for, say, string types and records, but not so much for Ints and simple enums. Perhaps it's something that GHC could do when deriving Eq instances?! — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#77 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAOOF7MTDQ3BVDZETBKJIHTTQD4YHANCNFSM4ANW635Q> .

[sjakobi]

I've brought up the idea in https://mail.haskell.org/pipermail/libraries/2021-June/031290.html.

[sjakobi]

I've had a quick look at some common key types:

• ByteArray and its wrappers ShortByteString and ShortText use pointer equality.
• Data.Text uses pointer equality.
• Data.Text.Lazy uses pointer equality on the individual text chunks but not on the outer Chunk structure.
• Data.ByteString uses pointer equality.
• Data.ByteString.Lazy compares the underlying StrictByteStrings using pointer equality, but not the outer Chunk structure. (Optimize Eq and Ord for LazyByteString using pointer equality haskell/bytestring#404)

[sjakobi]

GHC uses eqString to compare Strings:

eqString :: String -> String -> Bool
eqString []       []       = True
eqString (c1:cs1) (c2:cs2) = c1 == c2 && cs1 `eqString` cs2
eqString _        _        = False

{-# RULES "eqString" (==) = eqString #-}
-- eqString also has a BuiltInRule in GHC.Core.Opt.ConstantFold:
--      eqString (unpackCString# (Lit s1)) (unpackCString# (Lit s2)) = s1==s2

Maybe it would be ok to wrap it in a pointer equality check like this:

eqString :: String -> String -> Bool
eqString !x1 !x2 = isTrue# (reallyUnsafePtrEquality x1 x2) || eqString' x1 x2
  where
    eqString' []       []       = True
    eqString' (c1:cs1) (c2:cs2) = c1 == c2 && cs1 `eqString'` cs2
    eqString' _        _        = False

---

I also think that GHC should add pointer equality checks in derived Eq instances for records, when, say there are at least 2 fields of which at least one is pointer.

[treeowl]

That particular eqString rule looks almost (though I guess not completely) useless, since it only fires when comparing a literal to a literal. I don't think that's even slightly useful in our context. We could attempt an asymmetrical version of it to try to optimize for operations involving string literals as keys, but I suspect those are vanishingly rare.

[sjakobi]

@treeowl Yeah, I just included the rule for completeness. How do you feel about the added pointer equality check in eqString though?

[treeowl]

Maybe occasionally helpful.

[sjakobi]

I wonder whether you could use deriving-via to add a pointer-equality check to an Eq instance.

[treeowl]

There's no way to use the stock deriving machinery without actually creating the stock instance. So you can do something like

newtype Fancy a = Fancy a
instance Eq a => Eq (Fancy a) where
  Fancy !a == Fancy !b = ptrEq a b || a == b

newtype MyString = MyString String
  deriving Eq via (Fancy String) 

but that's pretty limited. Your other option would be to use generics. Cribbing from generic-data:

newtype Bleh a = Bleh a
instance (Generic a, Eq (Rep a)) => Eq (Bleh a) where
  Bleh !a == Bleh !b = ptrEq a b || from a == from b

Of course, you could also do some Template Haskell-based deriving that'll work for GADTs and things you don't want to be Generic.

[sjakobi]

@treeowl Nice! I think we should do some testing on how practical and effective this is and then maybe recommend this approach in the performance tips section I want to add to the readme.

Maybe we can even export a helper like your Fancy from this package…