Lazy recalculation strategy

Hi there, I’m currently thinking about an approach on how I can optimize a few specific use-cases in our application and I had an idea similar to how .distinctUntilChanged operator in RxSwift works but for collections. Basically I have a cache in our application which stores models that are not yet converted to view models. At some point the application will do the conversion let’s say to get some kind of a list related to the UI. However this view model is not cached anywhere and the conversion process occurs quite often. Now I’d like to build a small wrapper type that will cache the converted value lazely and don’t recompute the value until the original model changes, hence the comparison with the distinctUntilChanged operator from before.

One strategy that I had in my mind was to cache the hashValue of the original collection (it’s an Array so the order remains the same) and recalculate only when the hashValue is different from the cached hashValue. To clarify this is only a runtime approach and do not want to store the hashValue anywhere since it’s not considered to be stable between different runs.

  • Can I assume that strategy to be safe?
  • Do you have other suggestions how to build a cache that will recompute the values lazely?

Here is a small type that I just wrote quickly in Playgrounds:

struct LazyMapCache<T, R> where T : Hashable {
  ///
  private let map: (T) -> R

  ///
  private var _hashValue: Int

  ///
  private lazy var _mappedValue: R = map(value)

  ///
  var value: T

  ///
  var mappedValue: R {
    mutating get {
      if _hashValue != value.hashValue {
        _hashValue = value.hashValue
        _mappedValue = map(value)
      }
      return _mappedValue
    }
  }

  ///
  init(value: T, map: @escaping (T) -> R) {
    self.value = value
    self._hashValue = value.hashValue
    self.map = map
  }
}

But different values can have the same hashValue.

Yes, it’s technically unsafe, because a.hashValue == b.hashValue doesn’t imply either a == b (or f(a) == f(b) for presumably pure function f). It will work with high probably if your hash function is “good enough”, but why not just test a == b directly? Or, if equality testing is too expensive, invalidate the stored hash value when the item is changed (using didSet or similar).