11 people like it.

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
namespace System
namespace System.Collections
namespace System.Collections.Generic
Multiple items
type HashMap<'K,'V (requires comparison)> =
  new : cmp:IEqualityComparer<'K> -> HashMap<'K,'V>
  member Add : key:'K * value:'V -> unit
  member Index : key:'K -> int
  member Remove : key:'K -> unit
  member TryGetValue : key:'K * value:byref<'V> -> bool
  member Count : int

Full name: Script.HashMap<_,_>

--------------------
new : cmp:IEqualityComparer<'K> -> HashMap<'K,'V>
val cmp : IEqualityComparer<'K> (requires comparison)
type IEqualityComparer<'T> =
  member Equals : x:'T * y:'T -> bool
  member GetHashCode : obj:'T -> int

Full name: System.Collections.Generic.IEqualityComparer<_>
val spineLength : int
val spine : Map<'K,'V> [] (requires comparison)
module Array

from Microsoft.FSharp.Collections
val create : count:int -> value:'T -> 'T []

Full name: Microsoft.FSharp.Collections.Array.create
Multiple items
module Map

from Microsoft.FSharp.Collections

--------------------
type Map<'Key,'Value (requires comparison)> =
  interface IEnumerable
  interface IComparable
  interface IEnumerable<KeyValuePair<'Key,'Value>>
  interface ICollection<KeyValuePair<'Key,'Value>>
  interface IDictionary<'Key,'Value>
  new : elements:seq<'Key * 'Value> -> Map<'Key,'Value>
  member Add : key:'Key * value:'Value -> Map<'Key,'Value>
  member ContainsKey : key:'Key -> bool
  override Equals : obj -> bool
  member Remove : key:'Key -> Map<'Key,'Value>
  ...

Full name: Microsoft.FSharp.Collections.Map<_,_>

--------------------
new : elements:seq<'Key * 'Value> -> Map<'Key,'Value>
val empty<'Key,'T (requires comparison)> : Map<'Key,'T> (requires comparison)

Full name: Microsoft.FSharp.Collections.Map.empty
val this : HashMap<'K,'V> (requires comparison)
member HashMap.Count : int

Full name: Script.HashMap`2.Count
val sumBy : projection:('T -> 'U) -> array:'T [] -> 'U (requires member ( + ) and member get_Zero)

Full name: Microsoft.FSharp.Collections.Array.sumBy
module Seq

from Microsoft.FSharp.Collections
val length : source:seq<'T> -> int

Full name: Microsoft.FSharp.Collections.Seq.length
member HashMap.Index : key:'K -> int

Full name: Script.HashMap`2.Index
val key : 'K (requires comparison)
val abs : value:'T -> 'T (requires member Abs)

Full name: Microsoft.FSharp.Core.Operators.abs
System.Object.GetHashCode() : int
IEqualityComparer.GetHashCode(obj: 'K) : int
member HashMap.Add : key:'K * value:'V -> unit

Full name: Script.HashMap`2.Add
val value : 'V
val idx : int
member HashMap.Index : key:'K -> int
val add : key:'Key -> value:'T -> table:Map<'Key,'T> -> Map<'Key,'T> (requires comparison)

Full name: Microsoft.FSharp.Collections.Map.add
member HashMap.Remove : key:'K -> unit

Full name: Script.HashMap`2.Remove
val remove : key:'Key -> table:Map<'Key,'T> -> Map<'Key,'T> (requires comparison)

Full name: Microsoft.FSharp.Collections.Map.remove
member HashMap.TryGetValue : key:'K * value:byref<'V> -> bool

Full name: Script.HashMap`2.TryGetValue
val value : byref<'V>
type byref<'T> = (# "<Common IL Type Omitted>" #)

Full name: Microsoft.FSharp.Core.byref<_>
val bucket : Map<'K,'V> (requires comparison)
val tryFind : key:'Key -> table:Map<'Key,'T> -> 'T option (requires comparison)

Full name: Microsoft.FSharp.Collections.Map.tryFind
union case Option.None: Option<'T>
union case Option.Some: Value: 'T -> Option<'T>
val v : 'V
Raw view Test code New version

More information

Link:http://fssnip.net/l8
Posted:10 years ago
Author:Jon Harrop
Tags: collection , hash table