Hash collisions with FetchKey.ID in episode 0312-sqlite-sharing-pt4?

[seanwoodward]

Am I wrong? It looks like FetchKey.ID will allow for hash collisions. Key evaluation on Shared storage will default to Equatable tests on similar FetchKeys independent of Value.Type.

[mbrandonw]

Hi @seanwoodward, can you more concretely describe the problem you think you are seeing?

The ID type is technically generic over Value since it is nested inside FetchKey:

let _: FetchKey<Int>.ID
let _: FetchKey<String>.ID

So the Value type is definitely incorporated into the hashability of the ID. Further, it also incorporates the hash of the some FetchKeyRequest<Value>.

So I'm not sure how a collision can occur.

[mbrandonw]

Can confirm Type has no contribution to the hashValue which is probably obvious when we think about it.

Yeah, I thought when erased to AnyHashable the underlying type was taken into account, but that does not seem to be the case. We could of course mix in the type if we want, either at the level of FetchKey.ID or deep in the Sharing library itself.

It seems there is no benefit from Hashable conformance in those instances. For more than a few cases, ID might just as well conform to Equatable only.

Hashable is required because we store these keys in a dictionary using their ID:

https://github.com/pointfreeco/swift-sharing/blob/e75764374ef5ff58c62c23759240550bf0507d1a/Sources/Sharing/Internal/PersistentReferences.swift#L14

And while the ID's hashValue will not differentiate between two SharedKeys holding onto the exact same data, it will differentiate between two keys holding onto different data. So hash collisions still may not be that common in practice.

[seanwoodward]

Hashable is required because we store these keys in a dictionary using their ID:

Of course, but no benefit based on underlying types from the Hashable conformance.

Yeah, I thought when erased to AnyHashable the underlying type was taken into account, but that does not seem to be the case. We could of course mix in the type if we want, either at the level of FetchKey.ID or deep in the Sharing library itself.

But, like I think you have said on other related topics. Mixing the type in could get expensive and end up being counterproductive.

It just seems, FetchKeys and types like those are areas where caution is warranted. One can easily obscure away distinguishing characteristics in the fetch function. I can't think of a concrete case at the moment, but I was considering the possibility of overwriting one value with another unexpectedly because the id's couldn't be distinguished. Possibly if a key was fashioned with a closure.

[stephencelis]

Just to add to what Brandon said, the lookup is only done a single time when a new @SharedReader property wrapper is created, and there will only be as many entries as there are live keys, so even with collisions the performance isn't likely an issue here.

That said, we should probably improve the uniqueness of the hash values in any shipping example/code, so thanks for bringing this up!

[mbrandonw]

Of course, but no benefit based on underlying types from the Hashable conformance.

Yes there is a benefit if you have multiple FetchKey's that hold onto different data. For example:

struct User: FetchKeyRequest {
  let id: User.ID
  func fetch(…)
}
struct Tag: FetchKeyRequest {
  let id: Tag.ID
  func fetch(…)
}

These two requests will correspond to distinct SharedReaderKeys with distinct hash values, and so lookups via @SharedReader(.fetchOne(User(…)) and @SharedReader(.fetchOne(Tag(…)) will be fast since each key gets its own hash bucket.

And so the collision problem is really only if you have a whole bunch of FetchKeyRequests that hold onto the exact same data (such as no data at all). Further, this problem goes away once you have a query builder that plays nicely with hashability, because then you don't even need FetchKeyRequest most of the time. In that world, the only time you need FetchKeyRequest is if you want to bundle multiple queries into a single transaction.

But, like I think you have said on other related topics. Mixing the type in could get expensive and end up being counterproductive.

I don't remember discussing this. Mixing in the type is not expensive. It can be done like so:

struct ID: Hashable {
  let rawValue: AnyHashableSendable
  let typeID: ObjectIdentifier

  init(rawValue: some FetchKeyRequest) {
    rawValue = AnyHashableSendable(rawValue)
    typeID = ObjectIdentifier(type(of: rawValue))
  }
}

I would also mention that the times the storage is accessed via the ID is quite rare. You can put a print in the hash(into:) of a FetchKeyRequest conformance to see this. And so there probably isn't any concern for performance with hash collisions.

I can't think of a concrete case at the moment, but I was considering the possibility of overwriting one value with another unexpectedly because the id's couldn't be distinguished. Possibly if a key was fashioned with a closure.

That isn't possible because at the end of the day Equatable still distinguishes between the SharedKeys. The hashValue is only used for fast paths in Dictionary and is not ever used as an equality check. The worse that can happen is that our storage dictionary secretly has one single hash bucket with a large collection of values that need to be linearly checked for equality. In general that can worse the performance of the dictionary, but in this particular example it does not seem to be a problem.

[seanwoodward]

The worse that can happen is that our storage dictionary secretly has one single hash bucket with a large collection of values that need to be linearly checked for equality.

That's what got me on this path. Also hanging on the mention somewhere that type got considered as part of the hashablity. I did not think it did, and it does not. Consequently the only thing distinguishing the ID's hashValues would be the stored properties on the FetchKeyRequests.

Also, AnyHashableSendable does not appear to incorporate type either. The _HasCustomAnyHashableRepresentation simply forwards the base.

This seems like a naive approach, but I am interested in your thoughts.

struct TypeSensativeHashableWrapper<T: Hashable>: Hashable {
  let type: AnyHashable
  let base: T
  init(_ base: T) {
    self.type = ObjectIdentifier(T.self)
    self.base = base
  }
}

extension FetchKeyRequest {
  func _toCustomAnyHashable() -> AnyHashable? {
    .init(TypeSensativeHashableWrapper(self))
  }
}