Uniqueness guarantees broken in case of overflow? Or document why not

[Blaisorblade]

When writing docs (#2), I reverse-engineered from examples (Term) that two entries with the same IDs should be equal. However, what happens if cacheWidth * i below overflows an integer? This seems unlikely, but also next to impossible to track down if it ever actually happens.

However, I suppose you have some good reason to assume it won't overflow. Are there any caveats?

intern :: Interned t => Uninterned t -> t
intern !bt = unsafeDupablePerformIO $ modifyAdvice $ atomicModifyIORef slot go
  where
  slot = getCache cache ! r
  !dt = describe bt
  !hdt = hash dt
  !wid = cacheWidth dt
  r = hdt `mod` wid
  go (CacheState i m) = case HashMap.lookup dt m of
    Nothing -> let t = identify (wid * i + r) bt in (CacheState (i + 1) (HashMap.insert dt t m), t)
    Just t -> (CacheState i m, t)

[Blaisorblade]

I've thought about this: I think with cacheWidth = 1 you'd need to overflow memory itself to be able to get an overflow, but with higher widths you're relying on having a well-distributed hash. The width is bounded (because the table must fit in memory).

Maybe with some requirements on the hash you can prove that the overflow probability is exponentially small under some assumptions, but hashable does not document any of the guarantees I'd expect for this to be true. Instead, it allows opponents to force "quadratic performance" in hashtables — in those cases, I expect enough collisions for IDs to overflow (with 31bit Ints at least).

Can we make the Id type configurable, with or without performance degradation?

This was introduced in 8b8dbd2 to avoid contention on an MVar; but now you switched to IORef, so I guess this isn't thread-safe any more. Is there still a point in using multiple IORef on a single thread?

[Blaisorblade]

so I guess this isn't thread-safe any more. Is there still a point in using multiple IORef on a single thread?

If not, I think I'd be able to revert 8b8dbd2.