Aside: Why Caching?

Goal

Image Caching

Image Video Caching

Image Model Caching

Goal

One Instance to Rule them all

• Sole control of shared resources

One Instance to Rule them all

https://pixabay.com/en/hard-disk-storage-computer-159264/

One Instance to Rule them all

https://pixabay.com/en/internet-wlan-radio-network-1606099/

Cache Protocol

protocol Cache {

  associatedtype Key
  associatedtype Value

  func get(key: Key) -> Future<Value>

  func set(key: Key, value: Value) -> Future<Void>

}

Instance of a cache

class RamCache<K, V>: Cache where K: Hashable {
  typealias Key = K
  typealias Value = V

  func get(key: Key) -> Future<Value> { /* ... */ }

  func set(key: Key, value: Value) -> Future<Void> { /* ... */ }

}

Disk Cache

// md5 string key
class DiskCache<K>: Cache where K: StringConvertible {
  typealias Key = K
  typealias Value = NSData // byte array

  func get(key: Key) -> Future<Value> { /* ... */ }
  func set(key: Key, value: Value) -> Future<Void> { /* ... */ }
}

Cache Layering

https://upload.wikimedia.org/wikipedia/commons/thumb/8/8a/Boxkite.svg/2000px-Boxkite.svg.png

Cache Layering

Cache Layering

Cache Layering

Cache layering

extension Cache {

  func compose<B: Cache>(other: B) ->
          BasicCache<Self.Key, Self.Value>
      where Self.Key == B.Key
            Self.Value == B.Value {

    return BasicCache(
      get: { k in 
          self.get(k).orElse{
            other.get(k)
              .map{ v in self.set(k, v); return v }
          } }
      }

      set: { k, v in
         Future.join(self.set(k, v), other.set(k, v)) }
  }

}

Cache layering

let c = a.compose(b)
// c is a cache!

Cache layering

let c = a.compose(b).compose(x)
// c is a cache!

Network Cache

// always hit the network (no-op set)
class NetworkCache<K>: Cache where K: URLConvertible {
  typealias Key = K
  typealias Value = NSData // byte array
}

Associative -- Cache layering

let c1 = (ram.compose(disk))
    .compose(network)
// vs
let c2 = ram.compose(
    (disk.compose(network))
)

Identity Cache

Identity Layering

Cache layering

Associative binary operator + an identity element = Monoid

Monoidal Caching

let imageCache = fold(
  ramCache,
  diskCache,
  networkCache
)

Monoidal Caching

Layer?

Layer?

Transforming Caches

http://www.publicdomainpictures.net/pictures/170000/velka/wizard-1463307675N9Z.jpg

Transforming caches

Transforming caches

// bytesToImage: NSData -> UIImage
// imageToBytes: UIImage -> NSData
let imageNetCache: Cache<Value=UIImage> = 
    netCache.mapValues(bytesToImage, imageToBytes)

Transforming caches

Note that these transformed caches are virtual.

They provide different projections onto the same underlying cache.

Transforming caches

Transforming caches

extension Cache {
  func mapValues(
      f: Circle -> Triangle,
      _ fInv: Triangle -> Circle
  ) -> BasicCache<Key, Triangle> {

    return BasicCache(
      get: { k in self.get(k).map(f) }

      set: { k, v in self.set(k, fInv(v)) }
    )
  }
}

Transforming caches

extension Cache {
  func mapValues(
      f: NSData -> UIImage,
      _ fInv: UIImage -> NSData
  ) -> BasicCache<Key, UIImage> {

    return BasicCache(
      get: { k in self.get(k).map(f) }
      set: { k, v in self.set(k, fInv(v)) }
    )
  }
}

Transforming caches

extension Cache {
  func mapValues<V2>(
      f: Value -> V2,
      _ fInv: V2 -> Value
  ) -> BasicCache<Key, V2> {

    return BasicCache(
      get: { k in self.get(k).map(f) }
      set: { k, v in self.set(k, fInv(v)) }
    )
  }
}

Key transformations

https://pixabay.com/p-30417/?no_redirect

Key transformations

extension Cache {
  func mapKeys<K2>(
      fInv: K2 -> Key,
  ) -> BasicCache<K2, Value> {

    return BasicCache(
      get: { k in self.get(fInv(k)) }

      set: { k, v in self.set(fInv(k), v) }
    )
  }
}

Map Keys

Key transformations

// diskCache: DiskCache<String>
// urlToString: Url -> String
let urlCache = diskCache.mapKeys(urlToString)

Monoidal Caching

Monoidal Caching

let diskAndNet =
    diskCache.compose(netCache)
let diskAndNetImage =
    diskAndNet.mapValues(bytesToImg, imgToBytes)
return ramCache.compose(diskAndNetImage)

Problem

Optimization: Reusing inflight requests

extension Cache where K: Hashable {
  func reuseInflight(
      dict: [K: Future<V>]) -> BasicCache<K, V> {

    var dict = dict
    return BasicCache(
      get: { k in dict[k] ?? ({
              let f = self.get(k)
              dict[k] = f
              return f
           })() }
      set: self.set
    )
  }
  // logic for freeing the memory elided
}

Optimiziation: Reusing inflight requests

let smartNetworkCache = networkCache.reuseInflight(dict)
// still conforms to Cache<Key=Url,Value=NSData>

let f = smartNetworkCache.get(url)
let f2 = smartNetworkCache.get(url)
// only one real network request!
// same reference f === f2

Reuse across composed caches!

let optimizedCache = diskCache.compose(netCache)
    .reuseInflight(dict)

Optimized Caching

let diskAndNet =
    diskCache.compose(netCache).reuseInflight(dict)
let diskAndNetImage =
    diskAndNet.mapValues(bytesToImg, imgToBytes)
return ramCache.compose(diskAndNetImage)

Complexity in one place

https://pixabay.com/p-724096

Overall win

Carlos Caching

• Carlos is an open source Swift library
• Created by @Vittorio_Monaco and @esad

Purescript Implementation

Purescript implementation created to help formalize these ideas

Appendix

Type Erasure

• We want to define the operators on protocols not the concrete instances
• In Swift you cannot return some type with existentials (like our Cache protocol)
• We need some type without an existential associatedtype.

Type erasure

In Swift, type erasure is converting protocol constraints to a concrete struct full of lambdas. Existential associated types become universally quantified generics.

Type erasure is usually used in Swift to simplify type signatures, but we can also use it to workaround this limitation in the language. You erase the type information that you had about the specific cache and add a small runtime penalty of an extra function call

func simplify() -> BasicCache<K, V> {
  return BasicCache(getFn: self.get, setFn: self.set)
}

Type-erased cache

struct BasicCache<K, V>: Cache {
  typealias Key = K
  typealias Value = V

  let getFn: K -> Future<V>
  let setFn: (K, V) -> Future<Void>

  func get(key: Key) -> Future<Value> {
    return getFn(key)
  }
  func set(key: Key, value: Value) -> Future<Void> {
    return setFn(key, value)
  }
}

Async Transforming caches

// bytesToImageAsync: NSData -> Future<UIImage>
// imageToBytes: UIImage -> Future<NSData>
let imageNetCache: Cache<Value=UIImage> =
    netCache.asyncMapValues(
        bytesToImageAsync,
        imageToBytesAsync
    )

// asyncMapValues implementation similar to mapValues

Transforming caches

• The v appears in covariant output and contravariant input positions
• We need two transformation functions
• Caches are profunctors w.r.t. values

Key transformations

• The k appears in contravariant input positions
• Caches are contravariant functors w.r.t. the keys