[swift-dev] Dictionary Collision Resolution Guarantees

[Alexis]

I’m currently cleaning up the docs on Dictionary to reflect the new indexing model, and I stumbled across the note that the following code should work assuming no reallocations occur:

//
//   var (i, found) = d.find(k) // i is associated with d's buffer
//   if found {
//      var e = d            // now d is sharing its data with e
//      e[newKey] = newValue // e now has a unique copy of the data
//      return e[i]          // use i to access e
//   }
//

This is effectively assuming that the open-addressing scheme being used is first-come-first-serve (FCFS). That is, any element being inserted can *only* be inserted into vacant buckets, rather than displacing existing elements. This is currently only internal docs, but do we actually want to guarantee this? The popular alternative of robin hood (RH) doesn’t follow this.

Some background: One interesting optimization avenue worth exploring is to tweak Dictionary to store hashes, rather than bits, to identify occupied slots (with some careful masking so that 0 still means “unoccupied”). Then searching for elements can be implemented as follows:

let hash = hashFromKey(key)
var i = indexFromHash(hash)
while true {
  if hashes[i] == 0 {
    // vacant, not contained
  } else if hashes[i] == hash {
    // maybe already exists?
    if keys[i] == key {
      // actually exists
    }
  }
  i = nextIndex(i)
}

The interesting property of this is that it almost all of the search time is spent linearly walking through an array and doing simple comparisons on integers, which is of course really easy to optimize (potentially even SIMD). 99.9999% of the time, if the element isn’t stored in the Dictionary, then you’ll just hit a 0 hash, and never look at the keys. Similarly, 99.9999% of the time, if the element *is* stored in the Dictionary, you’ll only do a single key comparison (on the actually equal element). So this is also really great for cache — pretty much all of your access are just linear scans of the hashes. 

The main downside is you’re now “wasting” more memory to store hashes, but you can potentially compensate for this by truncating the hashes to 8/16 bits for small Dictionaries (which will be better for SIMD anyway).

So what does this have to do with the RH scheme? Compared to FCFS, RH generally leads to lower variance on search distances, and provides a mechanism to short-circuit long runs if you have the hashes handy. If you find hashes which want to live later in the array than where you started, then the current element definitely isn’t contained. This means you can increase the load factor on your dictionary and further improve cache/memory usage (compensating for the memory-usage loss from storing hashes). However it will be prohibitively expensive if you require hashes to be recomputed on-the-fly.