Tweet

11 people like it.
Like the snippet!

Dictionary safe for concurrent reads

A fixed-size hash table of Maps. Adding and removing key-value pairs replaces one Map in the spine of the hash table. Threads can read from this collection concurrently while a single thread is writing into it. I created this as a response to the recent thread by Ayende Rahien about the performance of purely functional dictionaries. According to my measurements this collection is 3x slower to build and 2x slower to search than a thread-unsafe .NET Dictionary but it provides the thread safety he requires. However, the built-in .NET ConcurrentDictionary is slightly faster than this and provides stronger thread-safety guarantees.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 

open System.Collections.Generic

type HashMap<'K, 'V when 'K: comparison>(cmp: IEqualityComparer<'K>) =
  let spineLength = 524287
  let spine = Array.create spineLength Map.empty

  member this.Count =
    Array.sumBy Seq.length spine

  member this.Index key =
    abs(cmp.GetHashCode key % spineLength)

  member this.Add(key, value) =
    let idx = this.Index key
    spine.[idx] <- Map.add key value spine.[idx]

  member this.Remove key =
    let idx = this.Index key
    spine.[idx] <- Map.remove key spine.[idx]

  member this.TryGetValue(key, value: byref<'V>) =
    let bucket = spine.[this.Index key]
    match Map.tryFind key bucket with
    | None -> false
    | Some v ->
        value <- v
        true

More information