Should Dict avoid GC allocations for isbits key/value types?

Internals & Design
,
1

Resizing arrays, when elements have primitive types or more generally isbits types, does not trigger any GC, as this is handled by the C runtime. Dictionaries are also allocation-free during most operations, except during rehashing, which happens if you insert more elements than the current capacity. rehash is called to allocate larger arrays inside the Dict object before data from the original arrays are copied over. The original arrays are then discarded and eventually garbage-collected.

It seems that with a little bit of extra work, Dict for primitive and isbits keys/values can completely avoid GC-tracked allocations. You just need to make a C call to malloc in the Dict constructor and call free in the rehashing function and the finalizer.

Would such changes be worthwhile, given that some Julia users want to write allocation-free code? Tooling for this purpose includes e.g. AllocCheck.jl.

2

This isn’t correct.

function f(n)
    a = Int[]
    s = 10
    resize!(a, 2)
    GC.enable_logging()
    for i in 1:n
        resize!(a, s)
        s *= 2
    end
end
julia> f(10)
julia> f(20)
GC: pause 4.40ms. collected 38.487091MB. incr 
Heap stats: bytes_mapped 64.02 MB, bytes_resident 49.39 MB,
heap_size 118.52 MB, heap_target 124.45 MB, Fragmentation 1.096

GC: pause 2.86ms. collected 2.213348MB. incr 
Heap stats: bytes_mapped 64.02 MB, bytes_resident 49.39 MB,
heap_size 125.36 MB, heap_target 131.69 MB, Fragmentation 0.799

GC: pause 13.28ms. collected 4.490547MB. full 
Heap stats: bytes_mapped 64.02 MB, bytes_resident 49.39 MB,
heap_size 139.05 MB, heap_target 146.01 MB, Fragmentation 0.769

GC: pause 24.31ms. collected 82.068169MB. incr 
Heap stats: bytes_mapped 64.02 MB, bytes_resident 49.39 MB,
heap_size 93.38 MB, heap_target 100.71 MB, Fragmentation 1.292

GC: pause 0.30ms. collected 18.182655MB. incr 
Heap stats: bytes_mapped 64.02 MB, bytes_resident 49.39 MB,
heap_size 148.21 MB, heap_target 156.45 MB, Fragmentation 0.506
2 Likes
3

Point taken. I have a codebase where I’ve eliminated almost all allocations, except for Dict (rehashing) allocations which are essentially unsolvable without radical change in algorithms. It shouldn’t be hard to create a fork of Base Dict, where the internal Memory objects (fixed-size arrays) holding the dictionary data are replaced by MallocArray from StaticTools.jl, since the allocation patterns in dict.jl are very simple.

4

Why would you do that? You don’t save on allocations, your only gain is that you can immediately free the memory on rehash / dict growth, and don’t have to wait for GC.

The main thing I could imagine is that you want to disable GC because you cannot afford latency spikes?

Due to the exponential growth of Dict sizings, you can just disable GC and leak that memory. The total overhead is at most a factor 2 on dict sizes (geometric series – amount of leaked memory is less than amount of used memory).

3 Likes