dictionary maintenance

dict_del.jl

using Random


println("start...", Base.VERSION)

function gentape(Nsz, Ntape, rf)
    init = [rf() for i=1:Nsz]
    unique!(init)
    Nsz = length(init)
    state = copy(init)
    tape = Vector{eltype(init)}(undef, 3*Ntape)
    for i=1:3:3*Ntape
        replace=rand(1:Nsz)
        tape[i] = state[replace]
        nv = rf()
        state[replace] = nv
        tape[i+1] = nv
        tape[i+2] = rand(Bool) ? state[rand(1:Nsz)] : rf()
    end
    return init, tape
end;

@noinline function benchloop(init, tape)
    d = Set(init)
    nc = 0
    d.dict.age = 23
    ns = 0; mean_del = 0.0; mean_fill = 0.0; mean_mp = 0;
    for i=1:3:length(tape)
        if ((i-2)%UInt & 0xffff) < 3
                ns += 1
                mean_del += d.dict.ndel/length(d.dict.slots)
                mean_fill += d.dict.count/length(d.dict.slots)
                mean_mp += d.dict.maxprobe 
        end
        o = tape[i]
        n = tape[i+1]
        pop!(d, tape[i])
        push!(d, tape[i+1])
        nc += (tape[i+2] in d)
        push!(d, n)
    end
    return d, mean_del/ns, mean_fill/ns, mean_mp/ns, nc
end;

instances = []; 
for rf in [()->rand(Int), ()->randstring(16), ()->rand(Int8, 16)]
for nsz in [1<<11, 1<<12, 1<<13, 1<<14, 1<<15, 1<<16] 
        push!(instances, (nsz, 1<<21, rf)); 
end; 
end;


@noinline function run_bench(nsz, ntape, rf::rfT) where rfT
    GC.gc(true);
    rollovers = ntape/nsz
    rehashes = Int[]
    times = Float64[]
    meanfills = Float64[]
    meandels = Float64[]
    meanmps = Float64[]
    for i=1:3
        Random.seed!(hash(i))
        GC.gc(true);
        init, tape = gentape(nsz, ntape, rf)
        GC.gc(true);
        GC.enable(false) 
        t = @elapsed begin s, meandel, meanfill, meanmp,_ = benchloop(init, tape) end;
        push!(times, t)
        push!(rehashes, Int(s.dict.age>>32));
        push!(meanfills, meanfill);
        push!(meandels, meandel);
        push!(meanmps, meanmp);
        GC.enable(true)
        GC.gc(true)
    end
    
    cycles_per_op = round.((2e9 / 3) .* times ./ ntape)
    rollovers_until_rehash = rollovers ./ rehashes
    println("Run: nsz=$(nsz) with $(ntape) x 3 operations on $(typeof(rf()))")
    println("\tElapsed: $(times) seconds = $(cycles_per_op) cycles per operation")
    println("\tRehashes: $(rehashes) in $(rollovers) rollovers, i.e. every $(rollovers_until_rehash)")
    println("\tMean fill: $(meanfills)  // Mean del: $(meandels)  // Mean maxprobe: $(meanmps)")
    println()
    GC.gc(true);
end
#=
println("\n=== Super-vanilla ===\n")

for instance in instances
    run_bench(instance...)
end
=#

@eval Base @noinline function rehash!(h::Dict{K,V}, newsz = length(h.keys)) where V where K
    olds = h.slots
    oldk = h.keys
    oldv = h.vals
    sz = length(olds)
    newsz = _tablesz(newsz)
    h.age += (1<<32) + 1
    h.idxfloor = 1
    if h.count == 0
        resize!(h.slots, newsz)
        fill!(h.slots, 0)
        resize!(h.keys, newsz)
        resize!(h.vals, newsz)
        h.ndel = 0
        return h
    end

    slots = zeros(UInt8,newsz)
    keys = Vector{K}(undef, newsz)
    vals = Vector{V}(undef, newsz)
    age0 = h.age
    count = 0
    maxprobe = h.maxprobe

    for i = 1:sz
        @inbounds if olds[i] == 0x1
            k = oldk[i]
            v = oldv[i]
            index0 = index = hashindex(k, newsz)
            while slots[index] != 0
                index = (index & (newsz-1)) + 1
            end
            probe = (index - index0) & (newsz-1)
            probe > maxprobe && (maxprobe = probe)
            slots[index] = 0x1
            keys[index] = k
            vals[index] = v
            count += 1

            if h.age != age0
                # if `h` is changed by a finalizer, retry
                return rehash!(h, newsz)
            end
        end
    end

    h.slots = slots
    h.keys = keys
    h.vals = vals
    h.count = count
    h.ndel = 0
    h.maxprobe = maxprobe
    @assert h.age == age0

    return h
end

@eval Base @inline function _delete!(h::Dict{K,V}, index) where {K,V}
    @inbounds h.slots[index] = 0x2
    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)
    h.ndel += 1
    h.count -= 1
    h.age += 1
    return h
end

@eval Base @propagate_inbounds function _setindex!(h::Dict, v, key, index)
    h.slots[index] = 0x1
    h.keys[index] = key
    h.vals[index] = v
    h.count += 1
    h.age += 1
    if index < h.idxfloor
        h.idxfloor = index
    end

    sz = length(h.keys)
    # Rehash now if necessary
    if h.ndel >= ((3*sz)>>2) || h.count*3 > sz*2
        # > 3/4 deleted or > 2/3 full
        rehash!(h, h.count > 64000 ? h.count*2 : h.count*4)
    end
end



println("\n=== Vanilla ===\n")

for instance in instances
    run_bench(instance...)
end

println("\n=== Clean post del ===\n")

@eval Base @inline function _delete!(h::Dict{K,V}, index) where {K,V}
    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)
    off = 3 
    if (index-off -1)%UInt <= length(h.slots)-8
        p = convert(Ptr{UInt64}, pointer(h.slots, index-off))
        c = xor(ltoh(unsafe_load(p)), 0x0000000000000003<<(off*8))
        del =  c & 0x0202020202020202
        nonempty = del | ( (c & 0x0101010101010101)<<1 )
        remdel = del & ( (~nonempty) >>8 )
        remdel |= del & (remdel>>8)
        remdel |= del & (remdel>>8)
        remdel |= del & (remdel>>8)
        unsafe_store!(p, htol(xor(c, remdel)))
        h.count -= 1
        h.age += 1
        h.ndel += 1 #- count_ones(remdel)
    else
        @inbounds h.slots[index] = 0x2
        h.ndel += 1
        h.count -= 1
        h.age += 1
    end
    return h
end

for instance in instances
    run_bench(instance...)
end

println("\n=== Clean post del, maintain correct delcount ===\n")

@eval Base @inline function _delete!(h::Dict{K,V}, index) where {K,V}
    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)
    off = 3 
    if (index-off -1)%UInt <= length(h.slots)-8
        p = convert(Ptr{UInt64}, pointer(h.slots, index-off))
        c = xor(ltoh(unsafe_load(p)), 0x0000000000000003<<(off*8))
        del =  c & 0x0202020202020202
        nonempty = del | ( (c & 0x0101010101010101)<<1 )
        remdel = del & ( (~nonempty) >>8 )
        remdel |= del & (remdel>>8)
        remdel |= del & (remdel>>8)
        remdel |= del & (remdel>>8)
        unsafe_store!(p, htol(xor(c, remdel)))
        h.count -= 1
        h.age += 1
        h.ndel += 1 - count_ones(remdel)
    else
        @inbounds h.slots[index] = 0x2
        h.ndel += 1
        h.count -= 1
        h.age += 1
    end
    return h
end

@eval Base @propagate_inbounds function _setindex!(h::Dict, v, key, index)
    @inbounds h.ndel -= ifelse(h.slots[index] == 0x02, 1, 0)
    h.slots[index] = 0x01
    h.keys[index] = key
    h.vals[index] = v
    h.count += 1
    h.age += 1
    if index < h.idxfloor
        h.idxfloor = index
    end

    sz = length(h.keys)
    # Rehash now if necessary
    if (h.ndel + h.count) >= ((3*sz)>>2) || h.count*3 > sz*2
        # > 2/3 full or < 3/4 free
        rehash!(h, h.count > 64000 ? h.count*2 : h.count*4)
    end
end

for instance in instances
    run_bench(instance...)
end

println("...end")

results

$ ./julia ./dict_del.jl 
start...1.2.0-DEV.357

=== Vanilla ===

Run: nsz=2048 with 2097152 x 3 operations on Int64
	Elapsed: [0.244645259, 0.242470297, 0.242256811] seconds = [78.0, 77.0, 77.0] cycles per operation
	Rehashes: [341, 341, 341] in 1024.0 rollovers, i.e. every [3.002932551319648, 3.002932551319648, 3.002932551319648]
	Mean fill: [0.25, 0.25, 0.25]  // Mean del: [0.330810546875, 0.330810546875, 0.330810546875]  // Mean maxprobe: [26.0, 21.0, 30.0]

Run: nsz=4096 with 2097152 x 3 operations on Int64
	Elapsed: [0.236748098, 0.233313993, 0.235331316] seconds = [75.0, 74.0, 75.0] cycles per operation
	Rehashes: [170, 170, 170] in 512.0 rollovers, i.e. every [3.011764705882353, 3.011764705882353, 3.011764705882353]
	Mean fill: [0.25, 0.25, 0.25]  // Mean del: [0.3333740234375, 0.3333740234375, 0.3333740234375]  // Mean maxprobe: [40.0, 29.0, 47.0]

Run: nsz=8192 with 2097152 x 3 operations on Int64
	Elapsed: [0.243490105, 0.243375606, 0.246732829] seconds = [77.0, 77.0, 78.0] cycles per operation
	Rehashes: [85, 85, 85] in 256.0 rollovers, i.e. every [3.011764705882353, 3.011764705882353, 3.011764705882353]
	Mean fill: [0.25, 0.25, 0.25]  // Mean del: [0.33856201171875, 0.33856201171875, 0.33856201171875]  // Mean maxprobe: [37.0, 38.0, 33.0]

Run: nsz=16384 with 2097152 x 3 operations on Int64
	Elapsed: [0.258064497, 0.256909348, 0.257829223] seconds = [82.0, 82.0, 82.0] cycles per operation
	Rehashes: [42, 42, 42] in 128.0 rollovers, i.e. every [3.0476190476190474, 3.0476190476190474, 3.0476190476190474]
	Mean fill: [0.25, 0.25, 0.25]  // Mean del: [0.333343505859375, 0.333343505859375, 0.333343505859375]  // Mean maxprobe: [45.0, 43.0, 62.0]

Run: nsz=32768 with 2097152 x 3 operations on Int64
	Elapsed: [0.275115335, 0.28050324, 0.275732432] seconds = [87.0, 89.0, 88.0] cycles per operation
	Rehashes: [21, 21, 21] in 64.0 rollovers, i.e. every [3.0476190476190474, 3.0476190476190474, 3.0476190476190474]
	Mean fill: [0.25, 0.25, 0.25]  // Mean del: [0.3307342529296875, 0.3307342529296875, 0.3307342529296875]  // Mean maxprobe: [53.0, 54.0, 49.0]

Run: nsz=65536 with 2097152 x 3 operations on Int64
	Elapsed: [0.404229679, 0.409030475, 0.408865516] seconds = [129.0, 130.0, 130.0] cycles per operation
	Rehashes: [20, 20, 20] in 32.0 rollovers, i.e. every [1.6, 1.6, 1.6]
	Mean fill: [0.4765625, 0.4765625, 0.4765625]  // Mean del: [0.3307340145111084, 0.3307340145111084, 0.3307340145111084]  // Mean maxprobe: [49.364583333333336, 54.0, 65.0]

Run: nsz=2048 with 2097152 x 3 operations on String
	Elapsed: [0.569544235, 0.561555841, 0.570819405] seconds = [181.0, 179.0, 181.0] cycles per operation
	Rehashes: [341, 341, 341] in 1024.0 rollovers, i.e. every [3.002932551319648, 3.002932551319648, 3.002932551319648]
	Mean fill: [0.25, 0.25, 0.25]  // Mean del: [0.330810546875, 0.330810546875, 0.330810546875]  // Mean maxprobe: [27.0, 30.0, 28.0]

Run: nsz=4096 with 2097152 x 3 operations on String
	Elapsed: [0.606367623, 0.601522081, 0.613714138] seconds = [193.0, 191.0, 195.0] cycles per operation
	Rehashes: [170, 170, 170] in 512.0 rollovers, i.e. every [3.011764705882353, 3.011764705882353, 3.011764705882353]
	Mean fill: [0.25, 0.25, 0.25]  // Mean del: [0.3333740234375, 0.3333740234375, 0.3333740234375]  // Mean maxprobe: [32.0, 35.0, 28.0]

Run: nsz=8192 with 2097152 x 3 operations on String
	Elapsed: [0.667988412, 0.662645417, 0.669715024] seconds = [212.0, 211.0, 213.0] cycles per operation
	Rehashes: [85, 85, 85] in 256.0 rollovers, i.e. every [3.011764705882353, 3.011764705882353, 3.011764705882353]
	Mean fill: [0.25, 0.25, 0.25]  // Mean del: [0.33856201171875, 0.33856201171875, 0.33856201171875]  // Mean maxprobe: [33.0, 38.0, 44.0]

Run: nsz=16384 with 2097152 x 3 operations on String
	Elapsed: [0.828199927, 0.81986888, 0.823252579] seconds = [263.0, 261.0, 262.0] cycles per operation
	Rehashes: [42, 42, 42] in 128.0 rollovers, i.e. every [3.0476190476190474, 3.0476190476190474, 3.0476190476190474]
	Mean fill: [0.25, 0.25, 0.25]  // Mean del: [0.333343505859375, 0.333343505859375, 0.333343505859375]  // Mean maxprobe: [52.0, 42.0, 48.0]

Run: nsz=32768 with 2097152 x 3 operations on String
	Elapsed: [1.106201127, 1.105356589, 1.120198714] seconds = [352.0, 351.0, 356.0] cycles per operation
	Rehashes: [21, 21, 21] in 64.0 rollovers, i.e. every [3.0476190476190474, 3.0476190476190474, 3.0476190476190474]
	Mean fill: [0.25, 0.25, 0.25]  // Mean del: [0.3307342529296875, 0.3307342529296875, 0.3307342529296875]  // Mean maxprobe: [61.0, 49.0, 62.0]

Run: nsz=65536 with 2097152 x 3 operations on String
	Elapsed: [2.112826511, 2.114675035, 2.119493312] seconds = [672.0, 672.0, 674.0] cycles per operation
	Rehashes: [20, 20, 20] in 32.0 rollovers, i.e. every [1.6, 1.6, 1.6]
	Mean fill: [0.4765625, 0.4765625, 0.4765625]  // Mean del: [0.3307340145111084, 0.3307340145111084, 0.3307340145111084]  // Mean maxprobe: [58.0, 51.0, 88.0]

Run: nsz=2048 with 2097152 x 3 operations on Array{Int8,1}
	Elapsed: [4.229030618, 4.226041223, 4.2320911] seconds = [1344.0, 1343.0, 1345.0] cycles per operation
	Rehashes: [341, 341, 341] in 1024.0 rollovers, i.e. every [3.002932551319648, 3.002932551319648, 3.002932551319648]
	Mean fill: [0.25, 0.25, 0.25]  // Mean del: [0.330810546875, 0.330810546875, 0.330810546875]  // Mean maxprobe: [23.0, 31.0, 20.0]

Run: nsz=4096 with 2097152 x 3 operations on Array{Int8,1}
	Elapsed: [4.335759232, 4.321526315, 4.322057192] seconds = [1378.0, 1374.0, 1374.0] cycles per operation
	Rehashes: [170, 170, 170] in 512.0 rollovers, i.e. every [3.011764705882353, 3.011764705882353, 3.011764705882353]
	Mean fill: [0.25, 0.25, 0.25]  // Mean del: [0.3333740234375, 0.3333740234375, 0.3333740234375]  // Mean maxprobe: [47.0, 21.0, 37.0]

Run: nsz=8192 with 2097152 x 3 operations on Array{Int8,1}
	Elapsed: [4.529610114, 4.506440613, 4.515788685] seconds = [1440.0, 1433.0, 1436.0] cycles per operation
	Rehashes: [85, 85, 85] in 256.0 rollovers, i.e. every [3.011764705882353, 3.011764705882353, 3.011764705882353]
	Mean fill: [0.25, 0.25, 0.25]  // Mean del: [0.33856201171875, 0.33856201171875, 0.33856201171875]  // Mean maxprobe: [51.0, 50.0, 43.0]

Run: nsz=16384 with 2097152 x 3 operations on Array{Int8,1}
	Elapsed: [4.790999721, 4.758825175, 4.783033787] seconds = [1523.0, 1513.0, 1520.0] cycles per operation
	Rehashes: [42, 42, 42] in 128.0 rollovers, i.e. every [3.0476190476190474, 3.0476190476190474, 3.0476190476190474]
	Mean fill: [0.25, 0.25, 0.25]  // Mean del: [0.333343505859375, 0.333343505859375, 0.333343505859375]  // Mean maxprobe: [72.0, 43.0, 45.0]

Run: nsz=32768 with 2097152 x 3 operations on Array{Int8,1}
	Elapsed: [5.078528324, 5.114356492, 5.028439522] seconds = [1614.0, 1626.0, 1598.0] cycles per operation
	Rehashes: [21, 21, 21] in 64.0 rollovers, i.e. every [3.0476190476190474, 3.0476190476190474, 3.0476190476190474]
	Mean fill: [0.25, 0.25, 0.25]  // Mean del: [0.3307342529296875, 0.3307342529296875, 0.3307342529296875]  // Mean maxprobe: [70.0, 58.0, 47.0]

Run: nsz=65536 with 2097152 x 3 operations on Array{Int8,1}
	Elapsed: [6.046172433, 5.983605028, 5.98642407] seconds = [1922.0, 1902.0, 1903.0] cycles per operation
	Rehashes: [20, 20, 20] in 32.0 rollovers, i.e. every [1.6, 1.6, 1.6]
	Mean fill: [0.4765625, 0.4765625, 0.4765625]  // Mean del: [0.3307340145111084, 0.3307340145111084, 0.3307340145111084]  // Mean maxprobe: [48.0, 110.0, 57.0]


=== Clean post del ===

Run: nsz=2048 with 2097152 x 3 operations on Int64
	Elapsed: [0.209893824, 0.209822905, 0.209757529] seconds = [67.0, 67.0, 67.0] cycles per operation
	Rehashes: [341, 341, 341] in 1024.0 rollovers, i.e. every [3.002932551319648, 3.002932551319648, 3.002932551319648]
	Mean fill: [0.25, 0.25, 0.25]  // Mean del: [0.330810546875, 0.330810546875, 0.330810546875]  // Mean maxprobe: [26.0, 21.0, 30.0]

Run: nsz=4096 with 2097152 x 3 operations on Int64
	Elapsed: [0.216109838, 0.216090586, 0.215460263] seconds = [69.0, 69.0, 68.0] cycles per operation
	Rehashes: [170, 170, 170] in 512.0 rollovers, i.e. every [3.011764705882353, 3.011764705882353, 3.011764705882353]
	Mean fill: [0.25, 0.25, 0.25]  // Mean del: [0.3333740234375, 0.3333740234375, 0.3333740234375]  // Mean maxprobe: [40.0, 29.0, 47.0]

Run: nsz=8192 with 2097152 x 3 operations on Int64
	Elapsed: [0.225910493, 0.22604745, 0.225793936] seconds = [72.0, 72.0, 72.0] cycles per operation
	Rehashes: [85, 85, 85] in 256.0 rollovers, i.e. every [3.011764705882353, 3.011764705882353, 3.011764705882353]
	Mean fill: [0.25, 0.25, 0.25]  // Mean del: [0.33856201171875, 0.33856201171875, 0.33856201171875]  // Mean maxprobe: [37.0, 38.0, 33.0]

Run: nsz=16384 with 2097152 x 3 operations on Int64
	Elapsed: [0.244554587, 0.244818117, 0.24184763] seconds = [78.0, 78.0, 77.0] cycles per operation
	Rehashes: [42, 42, 42] in 128.0 rollovers, i.e. every [3.0476190476190474, 3.0476190476190474, 3.0476190476190474]
	Mean fill: [0.25, 0.25, 0.25]  // Mean del: [0.333343505859375, 0.333343505859375, 0.333343505859375]  // Mean maxprobe: [45.0, 43.0, 62.0]

Run: nsz=32768 with 2097152 x 3 operations on Int64
	Elapsed: [0.260114493, 0.259836346, 0.260663612] seconds = [83.0, 83.0, 83.0] cycles per operation
	Rehashes: [21, 21, 21] in 64.0 rollovers, i.e. every [3.0476190476190474, 3.0476190476190474, 3.0476190476190474]
	Mean fill: [0.25, 0.25, 0.25]  // Mean del: [0.3307342529296875, 0.3307342529296875, 0.3307342529296875]  // Mean maxprobe: [53.0, 54.0, 49.0]

Run: nsz=65536 with 2097152 x 3 operations on Int64
	Elapsed: [0.398423745, 0.395777119, 0.397542758] seconds = [127.0, 126.0, 126.0] cycles per operation
	Rehashes: [20, 20, 20] in 32.0 rollovers, i.e. every [1.6, 1.6, 1.6]
	Mean fill: [0.4765625, 0.4765625, 0.4765625]  // Mean del: [0.3307340145111084, 0.3307340145111084, 0.3307340145111084]  // Mean maxprobe: [49.364583333333336, 54.0, 65.0]

Run: nsz=2048 with 2097152 x 3 operations on String
	Elapsed: [0.540554002, 0.541780579, 0.53604065] seconds = [172.0, 172.0, 170.0] cycles per operation
	Rehashes: [341, 341, 341] in 1024.0 rollovers, i.e. every [3.002932551319648, 3.002932551319648, 3.002932551319648]
	Mean fill: [0.25, 0.25, 0.25]  // Mean del: [0.330810546875, 0.330810546875, 0.330810546875]  // Mean maxprobe: [27.0, 30.0, 28.0]

Run: nsz=4096 with 2097152 x 3 operations on String
	Elapsed: [0.577959007, 0.57953474, 0.583195204] seconds = [184.0, 184.0, 185.0] cycles per operation
	Rehashes: [170, 170, 170] in 512.0 rollovers, i.e. every [3.011764705882353, 3.011764705882353, 3.011764705882353]
	Mean fill: [0.25, 0.25, 0.25]  // Mean del: [0.3333740234375, 0.3333740234375, 0.3333740234375]  // Mean maxprobe: [32.0, 35.0, 28.0]

Run: nsz=8192 with 2097152 x 3 operations on String
	Elapsed: [0.637352039, 0.645449645, 0.638336144] seconds = [203.0, 205.0, 203.0] cycles per operation
	Rehashes: [85, 85, 85] in 256.0 rollovers, i.e. every [3.011764705882353, 3.011764705882353, 3.011764705882353]
	Mean fill: [0.25, 0.25, 0.25]  // Mean del: [0.33856201171875, 0.33856201171875, 0.33856201171875]  // Mean maxprobe: [33.0, 38.0, 44.0]

Run: nsz=16384 with 2097152 x 3 operations on String
	Elapsed: [0.790166334, 0.808178479, 0.79699872] seconds = [251.0, 257.0, 253.0] cycles per operation
	Rehashes: [42, 42, 42] in 128.0 rollovers, i.e. every [3.0476190476190474, 3.0476190476190474, 3.0476190476190474]
	Mean fill: [0.25, 0.25, 0.25]  // Mean del: [0.333343505859375, 0.333343505859375, 0.333343505859375]  // Mean maxprobe: [52.0, 42.0, 48.0]

Run: nsz=32768 with 2097152 x 3 operations on String
	Elapsed: [1.055076088, 1.054751422, 1.046970143] seconds = [335.0, 335.0, 333.0] cycles per operation
	Rehashes: [21, 21, 21] in 64.0 rollovers, i.e. every [3.0476190476190474, 3.0476190476190474, 3.0476190476190474]
	Mean fill: [0.25, 0.25, 0.25]  // Mean del: [0.3307342529296875, 0.3307342529296875, 0.3307342529296875]  // Mean maxprobe: [61.0, 49.0, 62.0]

Run: nsz=65536 with 2097152 x 3 operations on String
	Elapsed: [2.05843152, 2.045811629, 2.053591654] seconds = [654.0, 650.0, 653.0] cycles per operation
	Rehashes: [20, 20, 20] in 32.0 rollovers, i.e. every [1.6, 1.6, 1.6]
	Mean fill: [0.4765625, 0.4765625, 0.4765625]  // Mean del: [0.3307340145111084, 0.3307340145111084, 0.3307340145111084]  // Mean maxprobe: [58.0, 51.0, 88.0]

Run: nsz=2048 with 2097152 x 3 operations on Array{Int8,1}
	Elapsed: [4.223851546, 4.221084083, 4.223152545] seconds = [1343.0, 1342.0, 1343.0] cycles per operation
	Rehashes: [341, 341, 341] in 1024.0 rollovers, i.e. every [3.002932551319648, 3.002932551319648, 3.002932551319648]
	Mean fill: [0.25, 0.25, 0.25]  // Mean del: [0.330810546875, 0.330810546875, 0.330810546875]  // Mean maxprobe: [23.0, 31.0, 20.0]

Run: nsz=4096 with 2097152 x 3 operations on Array{Int8,1}
	Elapsed: [4.305847342, 4.305690362, 4.309806044] seconds = [1369.0, 1369.0, 1370.0] cycles per operation
	Rehashes: [170, 170, 170] in 512.0 rollovers, i.e. every [3.011764705882353, 3.011764705882353, 3.011764705882353]
	Mean fill: [0.25, 0.25, 0.25]  // Mean del: [0.3333740234375, 0.3333740234375, 0.3333740234375]  // Mean maxprobe: [47.0, 21.0, 37.0]

Run: nsz=8192 with 2097152 x 3 operations on Array{Int8,1}
	Elapsed: [4.506761781, 4.499188461, 4.527168197] seconds = [1433.0, 1430.0, 1439.0] cycles per operation
	Rehashes: [85, 85, 85] in 256.0 rollovers, i.e. every [3.011764705882353, 3.011764705882353, 3.011764705882353]
	Mean fill: [0.25, 0.25, 0.25]  // Mean del: [0.33856201171875, 0.33856201171875, 0.33856201171875]  // Mean maxprobe: [51.0, 50.0, 43.0]

Run: nsz=16384 with 2097152 x 3 operations on Array{Int8,1}
	Elapsed: [4.726804566, 4.745518002, 4.748586652] seconds = [1503.0, 1509.0, 1510.0] cycles per operation
	Rehashes: [42, 42, 42] in 128.0 rollovers, i.e. every [3.0476190476190474, 3.0476190476190474, 3.0476190476190474]
	Mean fill: [0.25, 0.25, 0.25]  // Mean del: [0.333343505859375, 0.333343505859375, 0.333343505859375]  // Mean maxprobe: [72.0, 43.0, 45.0]

Run: nsz=32768 with 2097152 x 3 operations on Array{Int8,1}
	Elapsed: [5.024028127, 5.017597029, 5.025202628] seconds = [1597.0, 1595.0, 1597.0] cycles per operation
	Rehashes: [21, 21, 21] in 64.0 rollovers, i.e. every [3.0476190476190474, 3.0476190476190474, 3.0476190476190474]
	Mean fill: [0.25, 0.25, 0.25]  // Mean del: [0.3307342529296875, 0.3307342529296875, 0.3307342529296875]  // Mean maxprobe: [70.0, 58.0, 47.0]

Run: nsz=65536 with 2097152 x 3 operations on Array{Int8,1}
	Elapsed: [5.92194511, 5.919796518, 5.914492556] seconds = [1883.0, 1882.0, 1880.0] cycles per operation
	Rehashes: [20, 20, 20] in 32.0 rollovers, i.e. every [1.6, 1.6, 1.6]
	Mean fill: [0.4765625, 0.4765625, 0.4765625]  // Mean del: [0.3307340145111084, 0.3307340145111084, 0.3307340145111084]  // Mean maxprobe: [48.0, 110.0, 57.0]


=== Clean post del, maintain correct delcount ===

Run: nsz=2048 with 2097152 x 3 operations on Int64
	Elapsed: [0.28987987, 0.280899159, 0.293404992] seconds = [92.0, 89.0, 93.0] cycles per operation
	Rehashes: [0, 0, 0] in 1024.0 rollovers, i.e. every [Inf, Inf, Inf]
	Mean fill: [0.25, 0.25, 0.25]  // Mean del: [0.2788505554199219, 0.27061208089192706, 0.2780354817708333]  // Mean maxprobe: [26.0, 21.0, 30.0]

Run: nsz=4096 with 2097152 x 3 operations on Int64
	Elapsed: [0.282417622, 0.27815036, 0.289923208] seconds = [90.0, 88.0, 92.0] cycles per operation
	Rehashes: [0, 0, 0] in 512.0 rollovers, i.e. every [Inf, Inf, Inf]
	Mean fill: [0.25, 0.25, 0.25]  // Mean del: [0.24767049153645834, 0.25137074788411456, 0.25818761189778644]  // Mean maxprobe: [40.0, 29.0, 47.0]

Run: nsz=8192 with 2097152 x 3 operations on Int64
	Elapsed: [0.282237378, 0.282056292, 0.280659669] seconds = [90.0, 90.0, 89.0] cycles per operation
	Rehashes: [0, 0, 0] in 256.0 rollovers, i.e. every [Inf, Inf, Inf]
	Mean fill: [0.25, 0.25, 0.25]  // Mean del: [0.2432715098063151, 0.24251524607340494, 0.24160893758138022]  // Mean maxprobe: [37.0, 38.0, 33.0]

Run: nsz=16384 with 2097152 x 3 operations on Int64
	Elapsed: [0.293992042, 0.290574431, 0.293765813] seconds = [93.0, 92.0, 93.0] cycles per operation
	Rehashes: [0, 0, 0] in 128.0 rollovers, i.e. every [Inf, Inf, Inf]
	Mean fill: [0.25, 0.25, 0.25]  // Mean del: [0.23337825139363608, 0.2338873545328776, 0.23101123174031576]  // Mean maxprobe: [45.0, 43.0, 62.0]

Run: nsz=32768 with 2097152 x 3 operations on Int64
	Elapsed: [0.294459411, 0.295019108, 0.296189533] seconds = [94.0, 94.0, 94.0] cycles per operation
	Rehashes: [0, 0, 0] in 64.0 rollovers, i.e. every [Inf, Inf, Inf]
	Mean fill: [0.25, 0.25, 0.25]  // Mean del: [0.21304583549499512, 0.21410250663757324, 0.2143253485361735]  // Mean maxprobe: [53.0, 54.0, 49.0]

Run: nsz=65536 with 2097152 x 3 operations on Int64
	Elapsed: [0.314527466, 0.314178509, 0.313073051] seconds = [100.0, 100.0, 100.0] cycles per operation
	Rehashes: [0, 0, 0] in 32.0 rollovers, i.e. every [Inf, Inf, Inf]
	Mean fill: [0.25, 0.25, 0.25]  // Mean del: [0.1893800894419352, 0.19084604581197104, 0.18872777620951334]  // Mean maxprobe: [49.0, 54.0, 65.0]

Run: nsz=2048 with 2097152 x 3 operations on String
	Elapsed: [0.708832966, 0.717375836, 0.705234764] seconds = [225.0, 228.0, 224.0] cycles per operation
	Rehashes: [0, 0, 0] in 1024.0 rollovers, i.e. every [Inf, Inf, Inf]
	Mean fill: [0.25, 0.25, 0.25]  // Mean del: [0.27261988321940106, 0.27417627970377606, 0.27217737833658856]  // Mean maxprobe: [27.0, 30.0, 28.0]

Run: nsz=4096 with 2097152 x 3 operations on String
	Elapsed: [0.729962425, 0.726126603, 0.721386671] seconds = [232.0, 231.0, 229.0] cycles per operation
	Rehashes: [0, 0, 0] in 512.0 rollovers, i.e. every [Inf, Inf, Inf]
	Mean fill: [0.25, 0.25, 0.25]  // Mean del: [0.2545096079508464, 0.25305430094401044, 0.2533702850341797]  // Mean maxprobe: [32.0, 35.0, 28.0]

Run: nsz=8192 with 2097152 x 3 operations on String
	Elapsed: [0.76941228, 0.768525509, 0.765533694] seconds = [245.0, 244.0, 243.0] cycles per operation
	Rehashes: [0, 0, 0] in 256.0 rollovers, i.e. every [Inf, Inf, Inf]
	Mean fill: [0.25, 0.25, 0.25]  // Mean del: [0.2439883550008138, 0.24417813618977866, 0.24000136057535806]  // Mean maxprobe: [33.0, 38.0, 44.0]

Run: nsz=16384 with 2097152 x 3 operations on String
	Elapsed: [0.904493895, 0.918898148, 0.907268525] seconds = [288.0, 292.0, 288.0] cycles per operation
	Rehashes: [0, 0, 0] in 128.0 rollovers, i.e. every [Inf, Inf, Inf]
	Mean fill: [0.25, 0.25, 0.25]  // Mean del: [0.23249228795369467, 0.23486328125, 0.23325077692667642]  // Mean maxprobe: [52.0, 42.0, 48.0]

Run: nsz=32768 with 2097152 x 3 operations on String
	Elapsed: [1.164284972, 1.166107558, 1.169779572] seconds = [370.0, 371.0, 372.0] cycles per operation
	Rehashes: [0, 0, 0] in 64.0 rollovers, i.e. every [Inf, Inf, Inf]
	Mean fill: [0.25, 0.25, 0.25]  // Mean del: [0.2127844492594401, 0.21442866325378418, 0.21416735649108887]  // Mean maxprobe: [61.0, 49.0, 62.0]

Run: nsz=65536 with 2097152 x 3 operations on String
	Elapsed: [1.382746189, 1.407808804, 1.379946504] seconds = [440.0, 448.0, 439.0] cycles per operation
	Rehashes: [0, 0, 0] in 32.0 rollovers, i.e. every [Inf, Inf, Inf]
	Mean fill: [0.25, 0.25, 0.25]  // Mean del: [0.19025850296020508, 0.18941895167032877, 0.18918248017628989]  // Mean maxprobe: [58.0, 51.0, 88.0]

Run: nsz=2048 with 2097152 x 3 operations on Array{Int8,1}
	Elapsed: [4.032281756, 4.050054748, 4.019090527] seconds = [1282.0, 1287.0, 1278.0] cycles per operation
	Rehashes: [0, 0, 0] in 1024.0 rollovers, i.e. every [Inf, Inf, Inf]
	Mean fill: [0.25, 0.25, 0.25]  // Mean del: [0.27365366617838544, 0.27632904052734375, 0.2746264139811198]  // Mean maxprobe: [23.0, 31.0, 20.0]

Run: nsz=4096 with 2097152 x 3 operations on Array{Int8,1}
	Elapsed: [4.106664313, 4.09290425, 4.086706549] seconds = [1305.0, 1301.0, 1299.0] cycles per operation
	Rehashes: [0, 0, 0] in 512.0 rollovers, i.e. every [Inf, Inf, Inf]
	Mean fill: [0.25, 0.25, 0.25]  // Mean del: [0.25303077697753906, 0.25693384806315106, 0.25013478597005206]  // Mean maxprobe: [47.0, 21.0, 37.0]

Run: nsz=8192 with 2097152 x 3 operations on Array{Int8,1}
	Elapsed: [4.245566861, 4.249175363, 4.245997374] seconds = [1350.0, 1351.0, 1350.0] cycles per operation
	Rehashes: [0, 0, 0] in 256.0 rollovers, i.e. every [Inf, Inf, Inf]
	Mean fill: [0.25, 0.25, 0.25]  // Mean del: [0.24123668670654297, 0.244661013285319, 0.2433156967163086]  // Mean maxprobe: [51.0, 50.0, 43.0]

Run: nsz=16384 with 2097152 x 3 operations on Array{Int8,1}
	Elapsed: [4.500339734, 4.487203034, 4.501985622] seconds = [1431.0, 1426.0, 1431.0] cycles per operation
	Rehashes: [0, 0, 0] in 128.0 rollovers, i.e. every [Inf, Inf, Inf]
	Mean fill: [0.25, 0.25, 0.25]  // Mean del: [0.23346312840779623, 0.22971550623575845, 0.23137680689493814]  // Mean maxprobe: [72.0, 43.0, 45.0]

Run: nsz=32768 with 2097152 x 3 operations on Array{Int8,1}
	Elapsed: [4.748907634, 4.754164117, 4.748759689] seconds = [1510.0, 1511.0, 1510.0] cycles per operation
	Rehashes: [0, 0, 0] in 64.0 rollovers, i.e. every [Inf, Inf, Inf]
	Mean fill: [0.25, 0.25, 0.25]  // Mean del: [0.21384398142496744, 0.21599515279134116, 0.21535865465799967]  // Mean maxprobe: [70.0, 58.0, 47.0]

Run: nsz=65536 with 2097152 x 3 operations on Array{Int8,1}
	Elapsed: [4.966804525, 4.955147626, 4.965950063] seconds = [1579.0, 1575.0, 1579.0] cycles per operation
	Rehashes: [0, 0, 0] in 32.0 rollovers, i.e. every [Inf, Inf, Inf]
	Mean fill: [0.25, 0.25, 0.25]  // Mean del: [0.18821577231089273, 0.19020942846934, 0.18940762678782144]  // Mean maxprobe: [48.0, 110.0, 57.0]

...end