class
Sync::Map(K, V)
- Sync::Map(K, V)
- Reference
- Object
Overview
Safe and fast Hash-like data-structure.
Map stores the key-value pairs in multiple buckets, each bucket being a
smaller map protected by its own rwlock, so only one bucket is locked at a
time, allowing other threads to keep interacting with the other buckets.
With enough buckets per available parallelism of the CPU, thread contention
over a shared map is significantly reduced when compared to a single Hash
protected with a single RWLock, leading to huge performance improvements.
The main drawback is memory usage. By default the number of buckets is 4
times the number of the system CPU count increased to the next power of two,
each with a minimum capacity of 4 entries. For example a 28-cores CPU will
create 128 buckets of 4 entries (initial capacity of 1024 entries). Just the
bucket slice is 3KB and the entries for a Map(String, Float64) will need
at least 12KB of memory, for a total of 15KB for an empty map!
Each bucket will grow automatically when they reach 75% occupancy; they may also shrink when deleted entries reach 25% of the total capacity.
Follows the Hash interface, but isn't a drop-in replacement.
The main difference is that Map is unordered by design, while Hash is
ordered (key insertion is retained). For example iteration will yield
key-value pairs in unexpected order, and the map can't be sorted.
The map is optimized for safe concurrent and parallel accesses of individual
entries. Methods that require to iterate, such as #each, #keys, or
#values will have to lock each bucket one after the other, and might not
fare that well.
NOTE If K overrides either #== or #hash(hasher) then both methods
must be overriden so that if two K are equal, then their hash must also be
equal (the opposite isn't true).
Defined in:
map.crConstructors
-
.new(initial_capacity : Int32 = 8, buckets_count : Int32 = self.class.default_buckets_count)
Creates a new map.
Class Method Summary
Instance Method Summary
- #[](key : K) : V
- #[]=(key : K, value : V) : V
- #[]?(key : K) : V | Nil
-
#clear : Nil
TODO
- #delete(key : K) : V | Nil
- #delete(key : K, & : -> U) : V | U forall U
-
#dup : Map(K, V)
Returns a shallow copy of this object.
- #each(& : K, V -> ) : Nil
- #each_key(& : K -> ) : Nil
- #each_value(& : V -> ) : Nil
- #empty? : Bool
- #fetch(key : K, default : U) : V | U forall U
- #fetch(key : K, & : -> U) : V | U forall U
- #has_key?(key : K) : Bool
- #keys : Array(K)
- #put(key : K, value : V) : V
- #put_if_absent(key : K, value : V) : V
- #put_if_absent(key : K, & : K -> V) : V
- #rehash : Nil
- #size : Int32
- #to_a : Array(Tuple(K, V))
- #to_h : Hash(K, V)
- #update(key : K, & : V -> V) : V
- #values : Array(V)
Constructor Detail
Creates a new map.
The initial_capacity is the number of entries the map should hold across all buckets. It will be clamped to at least as many buckets the map will hold, then elevated to the next power of two in each bucket.
The buckets_count is the number of buckets in the map. What matters is the actual parallelism (number of hardware threads) of the CPU rather than the total number of threads, but if your application only has 5 threads, running on a CPU with 32 cores, you might want to limit the buckets' count to the next power of two of 5 × 4 (32), instead of the default (128).
Class Method Detail
Instance Method Detail
Returns a shallow copy of this object.
This allocates a new object and copies the contents of
self into it.