`hashNub` (and `hashNubOn`)

[sjakobi]

I just came across this blogpost comparing different versions of nub: https://oleg.fi/gists/posts/2021-01-07-discrimination-benchmarks.html

(Correspondig benchmarks: https://github.com/ekmett/discrimination/pull/33/files)

Hoogle finds several implementations of hashNub in several packages: https://hoogle.haskell.org/?hoogle=hashNub

So maybe u-c should export the "definitive" version of that function, similar to how containers exports nubOrd[On]?!

(Bikeshed: Would nubHash[On] be better than hashNub[On]?!)

I think we can use unsafeInsert instead of insert (or at least insertNewKey), so this version should be even faster.

In witherable, there's a more general version of hashNub and also a hashNubOn based on alterF. Maybe we can help improve these versions too.

---

(All this makes me curious how a hashNub based on vector-hashtables would fare.)

CC: @phadej, @klapaucius

[treeowl]

I believe u-c traditionally uses names from containers, so nubHash seems more appropriate. Unsafe insertion is extremely subtle, and I'm not sure if it'll work right. I seem to remember that @int-e might be good at poking holes in that sort of thing. The basic question is what happens if multiple threads end up evaluating the thunk corresponding to a particular list cons in the result. We have to be very sure that everything is properly idempotent.

[treeowl]

A caveat: it's possible that we can do it with unsafePerformIO but not unsafeDupablePerformIO. My comments in the implementation of lazy ST are likely relevant.

[sjakobi]

A caveat: it's possible that we can do it with unsafePerformIO but not unsafeDupablePerformIO.

Sorry if I'm being dense, but what does unsafePerformIO have to do with it?

My comments in the implementation of lazy ST are likely relevant.

Which comments? Do you have a link?

[treeowl]

The situation is rather confusing, and I got slightly confused. unsafeInsert does in-place updates, which means that (to a first approximation) its HashMap argument should never be used after the call.

Now consider what nubHash (nubHashable?) produces: a list cons whose head is the first element of the argument list and whose tail is a thunk representing the rest of the result. That thunk will contain a reference to the accumulating HashSet. When that thunk is forced, the HashSet will be modified to insert the next value (unless we've reached the end of the list).

The potential problem is that (due to lazy blackholing) the thunk could potentially be forced by two different threads. Each of them will try to insert the next value, violating the general requirement that the argument to unsafeInsert not be reused after (or, in fact, during) the call.

That doesn't necessarily mean that what you're suggesting won't work perfectly well. But it means we need to be very sure that these concurrent operations won't actually step on each other in a bad way.

The easy way to make this safe is to ensure the thunk will only be forced in one thread. This would use the noDuplicate# primitive, just like unsafePerformIO. That's not free because it has to walk the GHC stack. But it's not usually terribly expensive, so it might be a reasonable option if we can't convince ourselves of idempotency.

[treeowl]

As for the comments, see https://hackage.haskell.org/package/ghc-internal-9.1201.0/docs/src/GHC.Internal.Control.Monad.ST.Lazy.Imp.html

[sjakobi]

Thanks for the explanation, @treeowl! :)

Maybe we can put up a challenge and ask people to break a naive unsafeInsert-based version of hashNub.

The easy way to make this safe is to ensure the thunk will only be forced in one thread. This would use the noDuplicate# primitive, just like unsafePerformIO. That's not free because it has to walk the GHC stack. But it's not usually terribly expensive, so it might be a reasonable option if we can't convince ourselves of idempotency.

Interesting! Something like this I guess:

 unsafeThaw :: Array a -> ST s (MArray s a)
 unsafeThaw ary
     = ST $ \s -> case unsafeThawSmallArray# (unArray ary) s of
-                   (# s', mary #) -> (# s', MArray mary #)
+                   (# s', mary #) -> case Exts.noDuplicate# s' of
+                     s'' -> (# s'', MArray mary #)
 {-# INLINE unsafeThaw #-}

[sjakobi]

Interesting! Something like this I guess:

Nope. More likely this:

 unsafeThaw :: Array a -> ST s (MArray s a)
 unsafeThaw ary
-    = ST $ \s -> case unsafeThawSmallArray# (unArray ary) s of
-                   (# s', mary #) -> (# s', MArray mary #)
+    = ST $ \s -> case Exts.noDuplicate# s of
+                   s' -> case unsafeThawSmallArray# (unArray ary) s' of
+                     (# s'', mary #) -> (# s'', MArray mary #)
 {-# INLINE unsafeThaw #-}

[treeowl]

I believe this will work reliably without needing too much detailed analysis, but it's been a little while since I've worked on this sort of thing seriously.

nubHashable = \xs -> foldr go stop empty 
  where 
    go x r seen@(HashSet seen_)
      | x `member` seen
      = r seen
      | otherwise
      = x : rest
      where
        -- We use NOINLINE to make sure the thunk
        -- doesn't get duplicated at compile time. 
        -- That's unlikely to happen in this recursive 
        -- context, but it's better to be explicit.
        {-# NOINLINE rest #-}
        rest = unsafePerformIO . evaluate $ r (HashSet $ M.unsafeInsert x () seen_)

[treeowl]

Sticking the noDuplicate# in unsafeThaw seems plausible, but you still have to have your ears perked up where the thunk is created to make sure GHC can't duplicate it at compile time.

[int-e]

Edit: I was wrong, see #560 (comment) below.

Yes, unsafePerformIO . evaluate should be fine. It adds an extra seq# though that isn't needed.

A slightly better alternative would be to factor out unsafeInsertM :: forall k v. Hashable k => k -> v -> HashMap k v -> ST s (HashMap k v) from unsafeInsert and then use this:

rest = r . HashSet $ runST (unsafeIOToST noDuplicate >> M.unsafeInsertM x () seen_)

(noDuplicate comes from GHC.IO.Unsafe)

And finally, yes, the obviously safe way to write this function is with lazy ST, but that makes it hard to avoid extraneous noDuplicate# calls. The last time I did this I ended up with way too many conversions between lazy and strict ST. It's probably saner to stick with strict ST and use unsafeInterleaveST to explicitly defer parts of the computation when going this route.

P.S. It may be worth pointing out that starting with empty is fine because it doesn't contain any arrays that could be updated.

[treeowl]

A slightly better alternative would be to factor out unsafeInsertM :: forall k v. Hashable k => k -> v -> HashMap k v -> ST s (HashMap k v) from unsafeInsert and then use this:

rest = r . HashSet $ runST (unsafeIOToST noDuplicate >> M.unsafeInsertM x () seen_)

Ah yes, that does seem better. Could we avoid explicitly using noDuplicate?

rest = r . HashSet $ unsafePerformIO(sTToIO (M.unsafeInsertM x () seen_))

[int-e]

Ah yes, that does seem better. Could we avoid explicitly using noDuplicate?

rest = r . HashSet $ unsafePerformIO(sTToIO (M.unsafeInsertM x () seen_))

Yes, that works too.

[treeowl]

@int-e , it would also be interesting to consider whether the bare unsafeInsert version would actually work safely. I'm not terribly optimistic, but it could turn out to be totally fine, and fast.

[int-e]

Actually I was wrong earlier; none of these versions that interleave pure code and unsafePerfomIO or runSTare safe and I'm not sure whether that's fixable. The problem, I believe, is that noDuplicate doesn't help if the thunk that unsafePerformIO (or similar) evaluates has been created twice. I've managed to actually produce such failures in ghci, though not with compiled code.

So I think you should just do the obviously safe thing, namely

nub xs = runST (go xs M.empty)
  where
    go [] seen = pure []
    go (x:xs) seen
       | Just _ <- M.lookup x seen = go xs seen
       | otherwise = do
            rest <- unsafeInterleaveST $ do
                seen' <- M.unsafeInsertM x () seen
                go xs seen'
            pure (x : rest)

The crucial difference is that the creation of the argument to unsafeInterleaveST can't be duplicated within the same runST; it will be done by the time the x:rest value is returned.