• Josh Bleecher Snyder's avatar
    runtime: limit the number of map overflow buckets · 9980b70c
    Josh Bleecher Snyder authored
    Consider repeatedly adding many items to a map
    and then deleting them all, as in #16070. The map
    itself doesn't need to grow above the high water
    mark of number of items. However, due to random
    collisions, the map can accumulate overflow
    buckets.
    
    Prior to this CL, those overflow buckets were
    never removed, which led to a slow memory leak.
    
    The problem with removing overflow buckets is
    iterators. The obvious approach is to repack
    keys and values and eliminate unused overflow
    buckets. However, keys, values, and overflow
    buckets cannot be manipulated without disrupting
    iterators.
    
    This CL takes a different approach, which is to
    reuse the existing map growth mechanism,
    which is well established, well tested, and
    safe in the presence of iterators.
    When a map has accumulated enough overflow buckets
    we trigger map growth, but grow into a map of the
    same size as before. The old overflow buckets will
    be left behind for garbage collection.
    
    For the code in #16070, instead of climbing
    (very slowly) forever, memory usage now cycles
    between 264mb and 483mb every 15 minutes or so.
    
    To avoid increasing the size of maps,
    the overflow bucket counter is only 16 bits.
    For large maps, the counter is incremented
    stochastically.
    
    Fixes #16070
    
    Change-Id: If551d77613ec6836907efca58bda3deee304297e
    Reviewed-on: https://go-review.googlesource.com/25049
    Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
    TryBot-Result: Gobot Gobot <gobot@golang.org>
    Reviewed-by: default avatarKeith Randall <khr@golang.org>
    9980b70c
hashmap_fast.go 12.2 KB