• Josh Bleecher Snyder's avatar
    runtime: change map iteration randomization to use intra-bucket offset · 3be4d957
    Josh Bleecher Snyder authored
    Map iteration previously started from a random bucket, but walked each
    bucket from the beginning. Now, iteration always starts from the first
    bucket and walks each bucket starting at a random offset. For
    performance, the random offset is selected at the start of iteration
    and reused for each bucket.
    
    Iteration over a map with 8 or fewer elements--a single bucket--will
    now be non-deterministic. There will now be only 8 different possible
    map iterations.
    
    Significant benchmark changes, on my OS X laptop (rough but consistent):
    
    benchmark                              old ns/op     new ns/op     delta
    BenchmarkMapIter                       128           121           -5.47%
    BenchmarkMapIterEmpty                  4.26          4.45          +4.46%
    BenchmarkNewEmptyMap                   114           111           -2.63%
    
    Fixes #6719.
    
    R=khr, bradfitz
    CC=golang-codereviews
    https://golang.org/cl/47370043
    3be4d957
hashmap.c 35.3 KB