Repository: JuliaCollections/DataStructures.jl
Pull request #634 (2020-06-14 17:47:10)

SwissDict
### SwissDict
Part of GSoC'20 work.
Initial code and tests.
Tests run and works.
As of now, the benchmarks aren't favorable.
I'll post the benchmarks once I finish the work on #517 

**Tasks remaining**

- [x] Refactor code, and improve benchmarks.
- [x] Add docstrings and deploy doc
- [x] Add file to README


Patch:
diff --git a/README.md b/README.md
index 03429ea..9e99bcc 100644
--- a/README.md
+++ b/README.md
@@ -23,6 +23,7 @@ This package implements a variety of data structures, including
 -   Mutable Binary Heap
 -   Ordered Dicts and Sets
 -   RobinDict (implemented with [Robin Hood Hashing](https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf))
+-   SwissDict (inspired from [SwissTables](https://abseil.io/blog/20180927-swisstables))
 -   Dictionaries with Defaults
 -   Trie
 -   Linked List and Mutable Linked List
diff --git a/docs/make.jl b/docs/make.jl
index 56e9c88..c75f845 100644
--- a/docs/make.jl
+++ b/docs/make.jl
@@ -19,6 +19,7 @@ makedocs(
         "ordered_containers.md",
         "default_dict.md",
         "robin_dict.md",
+        "swiss_dict.md",
         "trie.md",
         "linked_list.md",
         "mutable_linked_list.md",
diff --git a/docs/src/index.md b/docs/src/index.md
index 1818935..174bb74 100644
--- a/docs/src/index.md
+++ b/docs/src/index.md
@@ -15,6 +15,7 @@ This package implements a variety of data structures, including
 -   Mutable Binary Heap
 -   Ordered Dicts and Sets
 -   RobinDict and OrderedRobinDict (implemented with [Robin Hood Hashing](https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf))
+-   SwissDict (inspired from [SwissTables](https://abseil.io/blog/20180927-swisstables))
 -   Dictionaries with Defaults
 -   Trie
 -   Linked List and Mutable Linked List
diff --git a/docs/src/swiss_dict.md b/docs/src/swiss_dict.md
new file mode 100644
index 0000000..eda4ef0
--- /dev/null
+++ b/docs/src/swiss_dict.md
@@ -0,0 +1,43 @@
+```@meta
+DocTestSetup = :(using DataStructures)
+```
+
+# SwissDict
+
+`SwissDict` provides a standard dictionary, conforming to the AbstractDict protocol, which is inspired from SwissTable developed by Google. This provides improved performance over Dict at extremely high Load Factor.
+
+The interface of `SwissDict` replicates that of `Dict`.
+
+Examples:
+
+```jldoctest
+julia> d = RobinDict{Int, Char}(1 => 'a', 2 => 'b')
+SwissDict{Int64,Char} with 2 entries:
+  1 => 'a'
+  2 => 'b'
+
+julia> d[3] = 'c';
+
+julia> collect(d)
+3-element Array{Pair{Int64,Char},1}:
+ 1 => 'a'
+ 2 => 'b'
+ 3 => 'c'
+
+julia> delete!(d, 2);
+
+julia> d[1]
+'a': ASCII/Unicode U+0061 (category Ll: Letter, lowercase)
+
+julia> d
+SwissDict{Int64,Char} with 2 entries:
+  1 => 'a'
+  3 => 'c'
+
+julia> pop!(d)
+1 => 'a'
+```
+
+```@meta
+DocTestSetup = nothing
+```
diff --git a/src/DataStructures.jl b/src/DataStructures.jl
index 675c625..93b8825 100644
--- a/src/DataStructures.jl
+++ b/src/DataStructures.jl
@@ -56,6 +56,7 @@ module DataStructures
     export MultiDict, enumerateall
     export RobinDict
     export OrderedRobinDict, isordered
+    export SwissDict
 
     export DiBitVector
 
@@ -97,6 +98,7 @@ module DataStructures
     include("container_loops.jl")
     include("robin_dict.jl")
     include("ordered_robin_dict.jl")
+    include("swiss_dict.jl")
     export
         CircularBuffer,
         capacity,
diff --git a/src/ordered_robin_dict.jl b/src/ordered_robin_dict.jl
index 98e6b68..15d938f 100644
--- a/src/ordered_robin_dict.jl
+++ b/src/ordered_robin_dict.jl
@@ -230,6 +230,7 @@ end
 function get!(default::Base.Callable, h::OrderedRobinDict{K,V}, key0) where {K,V}
     index = get(h.dict, key0, -2)
     index > 0 && return @inbounds h.vals[index]
+    
     v = convert(V, default())
     setindex!(h, v, key0)
     return v
diff --git a/src/swiss_dict.jl b/src/swiss_dict.jl
new file mode 100644
index 0000000..3fcc719
--- /dev/null
+++ b/src/swiss_dict.jl
@@ -0,0 +1,651 @@
+const SWISS_DICT_LOAD_FACTOR = 0.97
+const _u8x16 = NTuple{16, VecElement{UInt8}}
+
+"""
+    SwissDict([itr])
+
+`SwissDict{K,V}()` constructs a hash table with keys of type `K` and values of type `V`.
+Keys are compared with [`isequal`](@ref) and hashed with [`hash`](@ref).
+Given a single iterable argument, constructs a [`SwissDict`](@ref) whose key-value pairs
+are taken from 2-tuples `(key,value)` generated by the argument.
+
+# Examples
+```jldoctest
+julia> SwissDict([("A", 1), ("B", 2)])
+SwissDict{String,Int64} with 2 entries:
+  "B" => 2
+  "A" => 1
+```
+
+Alternatively, a sequence of pair arguments may be passed.
+
+```jldoctest
+julia> SwissDict("A"=>1, "B"=>2)
+SwissDict{String,Int64} with 2 entries:
+  "B" => 2
+  "A" => 1
+```
+"""
+mutable struct SwissDict{K,V} <: AbstractDict{K,V}
+    slots::Vector{_u8x16}
+    keys::Vector{K}
+    vals::Vector{V}
+    nbfull::Int
+    count::Int
+    age::UInt
+    idxfloor::Int  # an index <= the indices of all used slots
+
+    function SwissDict{K,V}() where {K, V}
+        new(fill(_expand16(0x00),1), Vector{K}(undef, 16), Vector{V}(undef, 16), 0, 0, 0, 1)
+    end
+    function SwissDict{K,V}(d::SwissDict{K,V}) where {K, V}
+        new(copy(d.slots), copy(d.keys), copy(d.vals), d.nbfull, d.count, d.age,
+            d.idxfloor)
+    end
+    function SwissDict{K, V}(slots, keys, vals, nbfull, count, age, idxfloor) where {K, V}
+        new(slots, keys, vals, nbfull, count, age, idxfloor)
+    end
+end
+function SwissDict{K,V}(kv) where {K, V}
+    h = SwissDict{K,V}()
+    for (k,v) in kv
+        h[k] = v
+    end
+    return h
+end
+SwissDict{K,V}(p::Pair) where {K,V} = setindex!(SwissDict{K,V}(), p.second, p.first)
+function SwissDict{K,V}(ps::Pair...) where {K, V}
+    h = SwissDict{K,V}()
+    sizehint!(h, length(ps))
+    for p in ps
+        h[p.first] = p.second
+    end
+    return h
+end
+SwissDict() = SwissDict{Any,Any}()
+SwissDict(kv::Tuple{}) = SwissDict()
+Base.copy(d::SwissDict) = SwissDict(d)
+Base.empty(d::SwissDict, ::Type{K}, ::Type{V}) where {K, V} = SwissDict{K, V}()
+
+SwissDict(ps::Pair{K,V}...) where {K,V} = SwissDict{K,V}(ps)
+SwissDict(ps::Pair...)                  = SwissDict(ps)
+
+function SwissDict(kv)
+    try
+        dict_with_eltype((K, V) -> SwissDict{K, V}, kv, eltype(kv))
+    catch e
+        if !isiterable(typeof(kv)) || !all(x->isa(x,Union{Tuple,Pair}),kv)
+            throw(ArgumentError("SwissDict(kv): kv needs to be an iterator of tuples or pairs"))
+        else
+            rethrow(e)
+        end
+    end
+end
+
+# SIMD utilities
+@inline _expand16(u::UInt8) = ntuple(i->VecElement(u), Val(16))
+_blsr(i::UInt32)= i & (i-Int32(1))
+
+@inline _vcmp_eq(u::_u8x16, v::_u8x16) = Core.Intrinsics.llvmcall(("""
+%cmp = icmp eq <16 x i8> %0, %1
+%cmp16 = bitcast <16 x i1> %cmp to i16
+%res = zext i16 %cmp16 to i32
+ret i32 %res
+"""), UInt32, Tuple{_u8x16,_u8x16}, u, v)
+
+@inline _vcmp_le(u::_u8x16, v::_u8x16) = Core.Intrinsics.llvmcall(("""
+%cmp = icmp ule <16 x i8> %0, %1
+%cmp16 = bitcast <16 x i1> %cmp to i16
+%res = zext i16 %cmp16 to i32
+ret i32 %res
+"""), UInt32, Tuple{_u8x16,_u8x16}, u, v)
+
+@inline function _prefetchr(p::Ptr)
+    ccall("llvm.prefetch", llvmcall, Cvoid, (Ref{Int8}, Int32, Int32, Int32), Ptr{Int8}(p), 0, 3, 1)
+end
+
+@inline function _prefetchw(p::Ptr)
+    ccall("llvm.prefetch", llvmcall, Cvoid, (Ref{Int8}, Int32, Int32, Int32), Ptr{Int8}(p), 1, 3, 1)
+end
+
+@inline function _hashtag(u::Unsigned)
+    #extracts tag between 0x02 and 0xff from lower bits, rotates tag bits to front
+    u = u % UInt
+    tag = u % UInt8
+    if UInt === UInt64
+        hi = ((u>>8) | (u<<56)) % Int
+    else
+        hi = ((u>>8) | (u<<24)) % Int
+    end
+    tag = tag > 1 ? tag : tag+0x02
+    return (hi, tag)
+end
+
+Base.@propagate_inbounds function _slotget(slots::Vector{_u8x16}, i::Int)
+    @boundscheck 0 < i <= length(slots)*16 || throw(BoundsError(slots, 1 + (i-1)>>4))
+    GC.@preserve slots begin
+        return unsafe_load(convert(Ptr{UInt8}, pointer(slots)), i)
+    end
+end
+
+Base.@propagate_inbounds function _slotset!(slots::Vector{_u8x16},  v::UInt8, i::Int)
+   @boundscheck 0 < i <= length(slots)*16 || throw(BoundsError(slots, 1 + (i-1)>>4))
+    GC.@preserve slots begin
+        return unsafe_store!(convert(Ptr{UInt8}, pointer(slots)), v, i)
+    end
+end
+
+@inline function _find_candidates(v::_u8x16, tag::UInt8)
+    match = _vcmp_eq(v, _expand16(tag))
+    return (match, v[16].value === 0x00)
+end
+
+@inline _find_free(v::_u8x16) = _vcmp_le(v, _expand16(UInt8(1)))
+
+# Basic operations
+
+# get the index where a key is stored, or -1 if not present
+ht_keyindex(h::SwissDict, key) = ht_keyindex(h::SwissDict, key, _hashtag(hash(key))...)
+function ht_keyindex(h::SwissDict, key, i0, tag)
+    slots = h.slots
+    keys = h.keys
+    sz = length(slots)
+    i = i0 & (sz-1)
+    _prefetchr(pointer(h.keys, i*16+1))
+    _prefetchr(pointer(h.vals, i*16+1))
+    #Todo/discuss: _prefetchr(pointer(h.keys, i*16+9))?
+    @inbounds while true
+        msk = slots[i+1]
+        cands, done = _find_candidates(msk, tag)
+        while cands != 0
+            off = trailing_zeros(cands)
+            idx = i*16 + off + 1
+            isequal(keys[idx], key) && return idx
+            cands = _blsr(cands)
+        end
+        done && break
+        i = (i+1) & (sz-1)
+    end
+    return -1
+end
+
+# get the index where a key is stored, or -pos if not present
+# and the key would be inserted at pos
+# This version is for use by setindex! and get!. It never rehashes.
+ht_keyindex2!(h::SwissDict, key) = ht_keyindex2!(h, key, _hashtag(hash(key))...)
+@inline function ht_keyindex2!(h::SwissDict, key, i0, tag)
+    slots = h.slots
+    keys = h.keys
+    sz = length(slots)
+    i = i0 & (sz-1)
+    _prefetchw(pointer(h.keys, i*16+1))
+    _prefetchw(pointer(h.vals, i*16+1))
+    #Todo/discuss: _prefetchr(pointer(h.keys, i*16+9))?
+    @inbounds while true
+        msk = slots[i+1]
+        cands, done = _find_candidates(msk, tag)
+        while cands != 0
+            off = trailing_zeros(cands)
+            idx = i*16 + off + 1
+            isequal(keys[idx], key) && return idx, tag
+            cands = _blsr(cands)
+        end
+        done && break
+        i = (i+1) & (sz-1)
+    end
+    i = i0 & (sz-1)
+    @inbounds while true
+        msk = slots[i+1]
+        cands = _find_free(msk)
+        if cands != 0
+            off = trailing_zeros(cands)
+            idx = i*16 + off + 1
+            return -idx, tag
+        end
+        i = (i+1) & (sz-1)
+    end
+end
+
+function _setindex!(h::SwissDict, v, key, index, tag)
+    @inbounds h.keys[index] = key
+    @inbounds h.vals[index] = v
+    h.count += 1
+    h.age += 1
+    so =  _slotget(h.slots, index)
+    h.nbfull += (iszero(index & 0x0f) & (so==0x00))
+    _slotset!(h.slots, tag, index)
+    if index < h.idxfloor
+        h.idxfloor = index
+    end
+    maybe_rehash_grow!(h)
+end
+
+function _delete!(h::SwissDict{K,V}, index) where {K,V}
+    # Caller is responsible for maybe shrinking the SwissDict after the deletion.
+    isbitstype(K) || isbitsunion(K) || ccall(:jl_arrayunset, Cvoid, (Any, UInt), h.keys, index-1)
+    isbitstype(V) || isbitsunion(V) || ccall(:jl_arrayunset, Cvoid, (Any, UInt), h.vals, index-1)
+    isboundary = iszero(index & 0x0f) #boundaries: 16, 32, ...
+    @inbounds _slotset!(h.slots, ifelse(isboundary, 0x01, 0x00), index)
+    h.count -= 1
+    h.age += 1
+    maybe_rehash_shrink!(h)
+end
+
+
+# fast iteration over active slots.
+function _iterslots(h::SwissDict, start::Int)
+    i0 = ((start-1) & (length(h.keys)-1))>>4 + 1
+    off = (start-1) & 0x0f
+    @inbounds sl = _find_free(h.slots[i0>>4 + 1])
+    sl = ((~sl & 0xffff)>>off) << off
+    return _iterslots(h, (i0, sl))
+end
+
+function _iterslots(h::SwissDict, state)
+    i, sl = state
+    while iszero(sl)
+        i += 1
+        i <= length(h.slots) || return nothing
+        @inbounds msk = h.slots[i]
+        sl = _find_free(msk)
+        sl = (~sl & 0xffff)
+    end
+    return ((i-1)*16 + trailing_zeros(sl) + 1, (i, _blsr(sl)))
+end
+
+# Dictionary resize logic:
+# Guarantee 40% of buckets and 15% of entries free, and at least 25% of entries filled
+# growth when > 85% entries full or > 60% buckets full, shrink when <25% entries full.
+# >60% bucket full should be super rare outside of very bad hash collisions or
+# super long-lived Dictionaries (expected 0.85^16 = 7% buckets full at 85% entries full).
+# worst-case hysteresis: shrink at 25% vs grow at 30% if all hashes collide.
+# expected hysteresis is 25% to 42.5%.
+function maybe_rehash_grow!(h::SwissDict)
+        sz = length(h.keys)
+        if h.count > sz * SWISS_DICT_LOAD_FACTOR || (h.nbfull-1) * 10 > sz * 6
+            rehash!(h, sz<<2)
+        end
+    end
+
+function maybe_rehash_shrink!(h::SwissDict)
+   sz = length(h.keys)
+   if h.count*4 < sz && sz > 16
+       rehash!(h, sz>>1)
+   end
+end
+
+function Base.sizehint!(d::SwissDict, newsz)
+    newsz = _tablesz(newsz*2)  # *2 for keys and values in same array
+    oldsz = length(d.keys)
+    # grow at least 25%
+    if newsz < (oldsz*5)>>2
+        return d
+    end
+    rehash!(d, newsz)
+end
+
+function rehash!(h::SwissDict{K,V}, newsz = length(h.keys)) where {K, V}
+    olds = h.slots
+    oldk = h.keys
+    oldv = h.vals
+    sz = length(oldk)
+    newsz = _tablesz(newsz)
+    (newsz*SWISS_DICT_LOAD_FACTOR) > h.count || (newsz <<= 1)
+    h.age += 1
+    h.idxfloor = 1
+    if h.count == 0
+        resize!(h.slots, newsz>>4)
+        fill!(h.slots, _expand16(0x00))
+        resize!(h.keys, newsz)
+        resize!(h.vals, newsz)
+        h.nbfull = 0
+        return h
+    end
+    nssz = newsz>>4
+    slots = fill(_expand16(0x00), nssz)
+    keys = Vector{K}(undef, newsz)
+    vals = Vector{V}(undef, newsz)
+    age0 = h.age
+    nbfull = 0
+    is = _iterslots(h, 1)
+    count = 0
+    @inbounds while is !== nothing
+        i, s = is
+        k = oldk[i]
+        v = oldv[i]
+        i0, t = _hashtag(hash(k))
+        i = i0 & (nssz-1)
+        idx = 0
+        while true
+            msk = slots[i + 1]
+            cands = _find_free(msk)
+            if cands != 0
+                off = trailing_zeros(cands)
+                idx = i*16 + off + 1
+                break
+            end
+            i = (i+1) & (nssz-1)
+        end
+        _slotset!(slots, t, idx)
+        keys[idx] = k
+        vals[idx] = v
+        nbfull += iszero(idx & 0x0f)
+        count += 1
+        if h.age != age0
+            return rehash!(h, newsz)
+        end
+        is = _iterslots(h, s)
+    end
+    h.slots = slots
+    h.keys = keys
+    h.vals = vals
+    h.nbfull = nbfull
+    @assert h.age == age0
+    @assert h.count == count
+    return h
+end
+
+Base.isempty(t::SwissDict) = (t.count == 0)
+Base.length(t::SwissDict) = t.count
+
+"""
+    empty!(collection) -> collection
+
+Remove all elements from a `collection`.
+
+# Examples
+```jldoctest
+julia> A = SwissDict("a" => 1, "b" => 2)
+SwissDict{String,Int64} with 2 entries:
+  "b" => 2
+  "a" => 1
+
+julia> empty!(A);
+
+julia> A
+SwissDict{String,Int64} with 0 entries
+```
+"""
+function Base.empty!(h::SwissDict{K,V}) where {K, V}
+    fill!(h.slots, _expand16(0x00))
+    sz = length(h.keys)
+    empty!(h.keys)
+    empty!(h.vals)
+    resize!(h.keys, sz)
+    resize!(h.vals, sz)
+    h.nbfull = 0
+    h.count = 0
+    h.age += 1
+    h.idxfloor = 1
+    return h
+end
+
+function Base.setindex!(h::SwissDict{K,V}, v0, key0) where {K, V}
+    key = convert(K, key0)
+    _setindex!(h, v0, key)
+end
+
+function _setindex!(h::SwissDict{K,V}, v0, key::K) where {K, V}
+    v = convert(V, v0)
+    index, tag = ht_keyindex2!(h, key)
+
+    if index > 0
+        h.age += 1
+        @inbounds h.keys[index] = key
+        @inbounds h.vals[index] = v
+    else
+        _setindex!(h, v, key, -index, tag)
+    end
+
+    return h
+end
+
+"""
+    get!(collection, key, default)
+
+Return the value stored for the given key, or if no mapping for the key is present, store
+`key => default`, and return `default`.
+
+# Examples
+```jldoctest
+julia> d = SwissDict("a"=>1, "b"=>2, "c"=>3);
+
+julia> get!(d, "a", 5)
+1
+
+julia> get!(d, "d", 4)
+4
+
+julia> d
+SwissDict{String,Int64} with 4 entries:
+  "c" => 3
+  "b" => 2
+  "a" => 1
+  "d" => 4
+```
+"""
+Base.get!(h::SwissDict{K,V}, key0, default) where {K,V} = get!(()->default, h, key0)
+
+"""
+    get!(f::Function, collection, key)
+
+Return the value stored for the given key, or if no mapping for the key is present, store
+`key => f()`, and return `f()`.
+
+This is intended to be called using `do` block syntax:
+```julia
+get!(dict, key) do
+    # default value calculated here
+    time()
+end
+```
+"""
+function Base.get!(default::Callable, h::SwissDict{K,V}, key0) where {K, V}
+    key = convert(K, key0)
+    return _get!(default, h, key)
+end
+
+function _get!(default::Callable, h::SwissDict{K,V}, key::K) where {K, V}
+    index, tag = ht_keyindex2!(h, key)
+
+    index > 0 && return @inbounds h.vals[index]
+
+    age0 = h.age
+    v = convert(V, default())
+    if h.age != age0
+        index, tag = ht_keyindex2!(h, key)
+    end
+    if index > 0
+        h.age += 1
+        @inbounds h.keys[index] = key
+        @inbounds h.vals[index] = v
+    else
+        _setindex!(h, v, key, -index, tag)
+    end
+    return v
+end
+
+function Base.getindex(h::SwissDict{K,V}, key) where {K, V}
+    index = ht_keyindex(h, key)
+    @inbounds return (index < 0) ? throw(KeyError(key)) : h.vals[index]::V
+end
+
+"""
+    get(collection, key, default)
+
+Return the value stored for the given key, or the given default value if no mapping for the
+key is present.
+
+# Examples
+```jldoctest
+julia> d = SwissDict("a"=>1, "b"=>2);
+
+julia> get(d, "a", 3)
+1
+
+julia> get(d, "c", 3)
+3
+```
+"""
+function Base.get(h::SwissDict{K,V}, key, default) where {K, V}
+    index = ht_keyindex(h, key)
+    @inbounds return (index < 0) ? default : h.vals[index]::V
+end
+
+"""
+    get(f::Function, collection, key)
+
+Return the value stored for the given key, or if no mapping for the key is present, return
+`f()`.  Use [`get!`](@ref) to also store the default value in the dictionary.
+
+This is intended to be called using `do` block syntax
+
+```julia
+get(dict, key) do
+    # default value calculated here
+    time()
+end
+```
+"""
+function Base.get(default::Callable, h::SwissDict{K,V}, key) where {K, V}
+    index = ht_keyindex(h, key)
+    @inbounds return (index < 0) ? default() : h.vals[index]::V
+end
+
+"""
+    haskey(collection, key) -> Bool
+
+Determine whether a collection has a mapping for a given `key`.
+
+# Examples
+```jldoctest
+julia> D = SwissDict('a'=>2, 'b'=>3)
+SwissDict{Char,Int64} with 2 entries:
+  'a' => 2
+  'b' => 3
+
+julia> haskey(D, 'a')
+true
+
+julia> haskey(D, 'c')
+false
+```
+"""
+Base.haskey(h::SwissDict, key) = (ht_keyindex(h, key) > 0)
+Base.in(key, v::KeySet{<:Any, <:SwissDict}) = (ht_keyindex(v.dict, key) > 0)
+
+"""
+    getkey(collection, key, default)
+
+Return the key matching argument `key` if one exists in `collection`, otherwise return `default`.
+
+# Examples
+```jldoctest
+julia> D = SwissDict('a'=>2, 'b'=>3)
+SwissDict{Char,Int64} with 2 entries:
+  'a' => 2
+  'b' => 3
+
+julia> getkey(D, 'a', 1)
+'a': ASCII/Unicode U+0061 (category Ll: Letter, lowercase)
+
+julia> getkey(D, 'd', 'a')
+'a': ASCII/Unicode U+0061 (category Ll: Letter, lowercase)
+```
+"""
+function Base.getkey(h::SwissDict{K,V}, key, default) where {K, V}
+    index = ht_keyindex(h, key)
+    @inbounds return (index<0) ? default : h.keys[index]::K
+end
+
+function _pop!(h::SwissDict, index)
+    @inbounds val = h.vals[index]
+    _delete!(h, index)
+    maybe_rehash_shrink!(h)
+    return val
+end
+
+"""
+    pop!(collection, key[, default])
+
+Delete and return the mapping for `key` if it exists in `collection`, otherwise return
+`default`, or throw an error if `default` is not specified.
+
+# Examples
+```jldoctest
+julia> d = SwissDict("a"=>1, "b"=>2, "c"=>3);
+
+julia> pop!(d, "a")
+1
+
+julia> pop!(d, "d")
+ERROR: KeyError: key "d" not found
+Stacktrace:
+[...]
+
+julia> pop!(d, "e", 4)
+4
+```
+"""
+function Base.pop!(h::SwissDict, key)
+    index = ht_keyindex(h, key)
+    return index > 0 ? _pop!(h, index) : throw(KeyError(key))
+end
+
+function Base.pop!(h::SwissDict, key, default)
+    index = ht_keyindex(h, key)
+    return index > 0 ? _pop!(h, index) : default
+end
+
+function Base.pop!(h::SwissDict)
+    isempty(h) && throw(ArgumentError("SwissDict must be non-empty"))
+    is = _iterslots(h, h.idxfloor)
+    @assert is !== nothing
+    idx, s = is
+    @inbounds key = h.keys[idx]
+    @inbounds val = h.vals[idx]
+    _delete!(h, idx)
+    h.idxfloor = idx
+    return key => val
+end
+
+"""
+    delete!(collection, key)
+
+Delete the mapping for the given key in a collection, and return the collection.
+
+# Examples
+```jldoctest
+julia> d = SwissDict("a"=>1, "b"=>2)
+SwissDict{String,Int64} with 2 entries:
+  "b" => 2
+  "a" => 1
+
+julia> delete!(d, "b")
+SwissDict{String,Int64} with 1 entry:
+  "a" => 1
+```
+"""
+function Base.delete!(h::SwissDict, key)
+    index = ht_keyindex(h, key)
+    if index > 0
+        _delete!(h, index)
+    end
+    maybe_rehash_shrink!(h)
+    return h
+end
+
+Base.@propagate_inbounds function Base.iterate(h::SwissDict, state = h.idxfloor)
+    is = _iterslots(h, state)
+    is === nothing && return nothing
+    i, s = is
+    @inbounds p = h.keys[i] => h.vals[i]
+    return (p, s)
+end
+
+Base.@propagate_inbounds function Base.iterate(v::Union{KeySet{<:Any, <:SwissDict}, Base.ValueIterator{<:SwissDict}}, state=v.dict.idxfloor)
+    is = _iterslots(v.dict, state)
+    is === nothing && return nothing
+    i, s = is
+    return (v isa KeySet ? v.dict.keys[i] : v.dict.vals[i], s)
+end


Test patch:
diff --git a/test/bench_robin_dict.jl b/test/bench_dict.jl
similarity index 98%
rename from test/bench_robin_dict.jl
rename to test/bench_dict.jl
index 9584ed7..d0ba7a3 100644
--- a/test/bench_robin_dict.jl
+++ b/test/bench_dict.jl
@@ -5,7 +5,7 @@ using Random
 
 suite = BenchmarkGroup()
 
-dicttypes = [Dict, RobinDict]
+dicttypes = [Dict, RobinDict, SwissDict]
 KVtypes = [Int, Float64]
 aexps = [4]
 for dt in dicttypes
diff --git a/test/runtests.jl b/test/runtests.jl
index f81b35a..0daa7df 100644
--- a/test/runtests.jl
+++ b/test/runtests.jl
@@ -33,6 +33,7 @@ tests = ["deprecations",
          "ordered_robin_dict",
          "dibit_vector",
          "red_black_tree",
+         "swiss_dict",
          "avl_tree"
         ]
 
diff --git a/test/test_swiss_dict.jl b/test/test_swiss_dict.jl
new file mode 100644
index 0000000..561807e
--- /dev/null
+++ b/test/test_swiss_dict.jl
@@ -0,0 +1,348 @@
+@testset "Constructors" begin
+    h1 = SwissDict()
+    @test length(h1) == 0
+    @test isempty(h1) == true
+    @test h1.idxfloor == 1
+    @test length(h1.keys) == 16
+    @test length(h1.vals) == 16
+    @test length(h1.slots) == 1
+    @test eltype(h1) == Pair{Any, Any}
+    @test keytype(h1) == Any
+    @test valtype(h1) == Any
+end
+
+@testset "SwissDict" begin
+    h = SwissDict()
+    for i=1:10000
+        h[i] = i+1
+    end
+    for i=1:10000
+        @test (h[i] == i+1)
+    end
+    for i=1:2:10000
+        delete!(h, i)
+    end
+    for i=1:2:10000
+        h[i] = i+1
+    end
+    for i=1:10000
+        @test (h[i] == i+1)
+    end
+    for i=1:10000
+        delete!(h, i)
+    end
+    @test isempty(h)
+    h[77] = 100
+    @test h[77] == 100
+    for i=1:10000
+        h[i] = i+1
+    end
+    for i=1:2:10000
+        delete!(h, i)
+    end
+    for i=10001:20000
+        h[i] = i+1
+    end
+    for i=2:2:10000
+        @test h[i] == i+1
+    end
+    for i=10000:20000
+        @test h[i] == i+1
+    end
+    h = SwissDict{Any,Any}("a" => 3)
+    @test h["a"] == 3
+    h["a","b"] = 4
+    @test h["a","b"] == h[("a","b")] == 4
+    h["a","b","c"] = 4
+    @test h["a","b","c"] == h[("a","b","c")] == 4
+
+    @testset "eltype, keytype and valtype" begin
+        @test eltype(h) == Pair{Any,Any}
+        @test keytype(h) == Any
+        @test valtype(h) == Any
+
+        td = SwissDict{AbstractString,Float64}()
+        @test eltype(td) == Pair{AbstractString,Float64}
+        @test keytype(td) == AbstractString
+        @test valtype(td) == Float64
+        @test keytype(Dict{AbstractString,Float64}) === AbstractString
+        @test valtype(Dict{AbstractString,Float64}) === Float64
+    end
+    # test rethrow of error in ctor
+    @test_throws DomainError SwissDict((sqrt(p[1]), sqrt(p[2])) for p in zip(-1:2, -1:2))
+end
+
+@testset "SwissDict on pairs" begin
+	let x = SwissDict(3=>3, 5=>5, 8=>8, 6=>6)
+	    pop!(x, 5)
+	    for k in keys(x)
+	        SwissDict{Int,Int}(x)
+	        @test k in [3, 8, 6]
+	    end
+	end
+    
+    let y = SwissDict{Any, Int}(3=>3, 5=>5, "8"=>8, 6=>6)
+        pop!(y, "8")
+        for k in keys(y)
+            SwissDict{Int,Int}(y)
+            @test k in [3, 5, 6]
+        end
+    end
+
+    d = @inferred SwissDict(Pair(1,1), Pair(2,2), Pair(3,3))
+    @test isa(d, SwissDict)
+    @test d == SwissDict(1=>1, 2=>2, 3=>3)
+    @test eltype(d) == Pair{Int,Int}
+end
+
+@testset "KeyError" begin
+    let z = SwissDict()
+        get_KeyError = false
+        try
+            z["a"]
+        catch _e123_
+            get_KeyError = isa(_e123_,KeyError)
+        end
+        @test get_KeyError
+    end
+end
+
+@testset "Filter function" begin
+    _d = SwissDict("a"=>0)
+    @test isa([k for k in filter(x->length(x)==1, collect(keys(_d)))], Vector{String})
+    
+    h = SwissDict{Int, Int}()
+    for i in 1:100
+        h[i] = i
+    end
+    filter!(x->isodd(x.first), h)
+    for i in 1:2:100
+        @test h[i] == i
+    end
+end
+
+@testset "typeof" begin
+    d = SwissDict(((1, 2), (3, 4)))
+    @test d[1] === 2
+    @test d[3] === 4
+    d2 = SwissDict(1 => 2, 3 => 4)
+    d3 = SwissDict((1 => 2, 3 => 4))
+    @test d == d2 == d3
+    @test typeof(d) == typeof(d2) == typeof(d3) == SwissDict{Int,Int}
+
+    d = SwissDict(((1, 2), (3, "b")))
+    @test d[1] === 2
+    @test d[3] == "b"
+    d2 = SwissDict(1 => 2, 3 => "b")
+    d3 = SwissDict((1 => 2, 3 => "b"))
+    @test d == d2 == d3
+    @test typeof(d) == typeof(d2) == typeof(d3) == SwissDict{Int,Any}
+
+    d = SwissDict(((1, 2), ("a", 4)))
+    @test d[1] === 2
+    @test d["a"] === 4
+    d2 = SwissDict(1 => 2, "a" => 4)
+    d3 = SwissDict((1 => 2, "a" => 4))
+    @test d == d2 == d3
+    @test typeof(d) == typeof(d2) == typeof(d3) == SwissDict{Any,Int}
+
+    d = SwissDict(((1, 2), ("a", "b")))
+    @test d[1] === 2
+    @test d["a"] == "b"
+    d2 = SwissDict(1 => 2, "a" => "b")
+    d3 = SwissDict((1 => 2, "a" => "b"))
+    @test d == d2 == d3
+    @test typeof(d) == typeof(d2) == typeof(d3) == SwissDict{Any,Any}
+end
+
+@testset "type of SwissDict constructed from varargs of Pairs" begin
+    @test SwissDict(1=>1, 2=>2.0) isa SwissDict{Int,Real}
+    @test SwissDict(1=>1, 2.0=>2) isa SwissDict{Real,Int}
+    @test SwissDict(1=>1.0, 2.0=>2) isa SwissDict{Real,Real}
+
+    for T in (Nothing, Missing)
+        @test SwissDict(1=>1, 2=>T()) isa SwissDict{Int,Union{Int,T}}
+        @test SwissDict(1=>T(), 2=>2) isa SwissDict{Int,Union{Int,T}}
+        @test SwissDict(1=>1, T()=>2) isa SwissDict{Union{Int,T},Int}
+        @test SwissDict(T()=>1, 2=>2) isa SwissDict{Union{Int,T},Int}
+    end
+end
+
+@testset "equality" for eq in (isequal, ==)
+    @test  eq(SwissDict(), SwissDict())
+    @test  eq(SwissDict(1 => 1), SwissDict(1 => 1))
+    @test !eq(SwissDict(1 => 1), SwissDict())
+    @test !eq(SwissDict(1 => 1), SwissDict(1 => 2))
+    @test !eq(SwissDict(1 => 1), SwissDict(2 => 1))
+
+    # Generate some data to populate dicts to be compared
+    data_in = [ (rand(1:1000), randstring(2)) for _ in 1:1001 ]
+
+    # Populate the first dict
+    d1 = SwissDict{Int, AbstractString}()
+    for (k, v) in data_in
+        d1[k] = v
+    end
+    data_in = collect(d1)
+    # shuffle the data
+    for i in 1:length(data_in)
+        j = rand(1:length(data_in))
+        data_in[i], data_in[j] = data_in[j], data_in[i]
+    end
+    # Inserting data in different (shuffled) order should result in
+    # equivalent dict.
+    d2 = SwissDict{Int, AbstractString}()
+    for (k, v) in data_in
+        d2[k] = v
+    end
+
+    @test eq(d1, d2)
+    d3 = copy(d2)
+    d4 = copy(d2)
+    # Removing an item gives different dict
+    delete!(d1, data_in[rand(1:length(data_in))][1])
+    @test !eq(d1, d2)
+    # Changing a value gives different dict
+    d3[data_in[rand(1:length(data_in))][1]] = randstring(3)
+    !eq(d1, d3)
+    # Adding a pair gives different dict
+    d4[1001] = randstring(3)
+    @test !eq(d1, d4)
+
+    @test eq(SwissDict(), sizehint!(SwissDict(),96))
+
+    # Dictionaries of different types
+    @test !eq(SwissDict(1 => 2), SwissDict("dog" => "bone"))
+    @test eq(SwissDict{Int,Int}(), SwissDict{AbstractString,AbstractString}())
+end
+
+@testset "equality special cases" begin
+    @test SwissDict(1=>0.0) == SwissDict(1=>-0.0)
+    @test !isequal(SwissDict(1=>0.0), SwissDict(1=>-0.0))
+
+    @test SwissDict(0.0=>1) != SwissDict(-0.0=>1)
+    @test !isequal(SwissDict(0.0=>1), SwissDict(-0.0=>1))
+
+    @test SwissDict(1=>NaN) != SwissDict(1=>NaN)
+    @test isequal(SwissDict(1=>NaN), SwissDict(1=>NaN))
+
+    @test SwissDict(NaN=>1) == SwissDict(NaN=>1)
+    @test isequal(SwissDict(NaN=>1), SwissDict(NaN=>1))
+
+    @test ismissing(SwissDict(1=>missing) == SwissDict(1=>missing))
+    @test isequal(SwissDict(1=>missing), SwissDict(1=>missing))
+
+    @test SwissDict(missing=>1) == SwissDict(missing=>1)
+    @test isequal(SwissDict(missing=>1), SwissDict(missing=>1))
+end
+
+@testset "get!" begin 
+    f(x) = x^2
+    d = SwissDict(8=>19)
+    @test get!(d, 8, 5) == 19
+    @test get!(d, 19, 2) == 2
+
+    @test get!(d, 42) do  # d is updated with f(2)
+        f(2)
+    end == 4
+
+    @test get!(d, 42) do  # d is not updated
+        f(200)
+    end == 4
+
+    @test get(d, 13) do   # d is not updated
+        f(4)
+    end == 16
+
+    @test d == SwissDict(8=>19, 19=>2, 42=>4)
+
+    d1 = SwissDict{Int8, Char}()
+    d1[1%Int8] = 'a'
+    @test get!(d1, 1, 'b') == 'a'
+    @test get!(d1, 2, 'c') == 'c'
+end
+
+@testset "push!" begin
+    d = SwissDict()
+    @test push!(d, 'a' => 1) === d
+    @test d['a'] == 1
+    @test push!(d, 'b' => 2, 'c' => 3) === d
+    @test d['b'] == 2
+    @test d['c'] == 3
+    @test push!(d, 'd' => 4, 'e' => 5, 'f' => 6) === d
+    @test d['d'] == 4
+    @test d['e'] == 5
+    @test d['f'] == 6
+    @test length(d) == 6
+end
+
+@testset "pop!" begin
+    d = SwissDict(1=>2, 3=>4)
+    @test pop!(d, 1) == 2
+    @test_throws KeyError pop!(d, 1)
+    @test pop!(d, 1, 0) == 0
+    @test pop!(d) == (3=>4)
+    @test_throws ArgumentError pop!(d)
+end
+
+@testset "keys as a set" begin
+    d = SwissDict(1=>2, 3=>4)
+    @test keys(d) isa AbstractSet
+    @test empty(keys(d)) isa AbstractSet
+    let i = keys(d) ∩ Set([1,2])
+        @test i isa AbstractSet
+        @test i == Set([1])
+    end
+    @test Set(string(k) for k in keys(d)) == Set(["1","3"])
+end
+
+@testset "find" begin
+    @test findall(isequal(1), SwissDict(:a=>1, :b=>2)) == [:a]
+    @test sort(findall(isequal(1), SwissDict(:a=>1, :b=>1))) == [:a, :b]
+    @test isempty(findall(isequal(1), SwissDict()))
+    @test isempty(findall(isequal(1), SwissDict(:a=>2, :b=>3)))
+
+    @test findfirst(isequal(1), SwissDict(:a=>1, :b=>2)) == :a
+    @test findfirst(isequal(1), SwissDict(:a=>1, :b=>1, :c=>3)) in (:a, :b)
+    @test findfirst(isequal(1), SwissDict()) === nothing
+    @test findfirst(isequal(1), SwissDict(:a=>2, :b=>3)) === nothing
+end
+
+@testset "haskey" begin
+    h = SwissDict(1=>2, 2=>3)
+    @test haskey(h, 1) == true
+    @test haskey(h, 2) == true
+    @test haskey(h, 3) == false
+    @test !haskey(h, "1")
+end
+
+@testset "getkey" begin
+    h = SwissDict(1=>2, 3 => 6, 5=>10)
+    @test getkey(h, 1, 7) == 1
+    @test getkey(h, 4, 6) == 6
+    @test getkey(h, "1", 8) == 8
+end
+
+
+@testset "ArgumentError" begin
+    @test_throws ArgumentError SwissDict(0)
+    @test_throws ArgumentError SwissDict([1])
+    @test_throws ArgumentError SwissDict([(1,2),0])
+end
+
+@testset "empty tuple" begin
+    h = SwissDict(())
+    @test length(h) == 0
+end
+
+@testset "empty" begin
+    h = SwissDict()
+    for i=1:10000
+        h[i] = i+1
+    end
+    prev_sz = length(h.keys)
+    @test length(h) != 0
+    empty!(h)
+    @test length(h) == 0
+    @test length(h.keys) == length(h.vals) == prev_sz
+end