The hash was uniform and the buckets were not

# Self-authored for the EML case corpus (no external origin). The hash was
# tested for uniformity and passed. The bucket occupancy in production is
# counted below, from the same hash.
#
# Both decisions here are the standard ones. A power-of-two bucket count turns
# the modulo into a bit mask, which is one instruction instead of a division,
# and it is what every hash table in every standard library does. Testing the
# hash by feeding it random keys and checking that the buckets come out level
# is also right, and the test passes, and it would catch a genuinely bad hash.
#
# Uniformity is not a property of a hash function. It is a property of a hash
# function together with an input distribution, and the test supplies its own
# input. Random keys are the one distribution the allocator never produces.
#
# The order ids come from a legacy allocator that hands out blocks of eight, so
# every id is a multiple of eight apart from its neighbour. That input is
# perfectly uniform over its own domain - it is not skewed, no value is hotter
# than another, and no key repeats. It simply shares a factor with the bucket
# count, and a modulo cannot separate a value from a multiple of its divisor.

8 => stride
1000 => first_id
512 => id_count

# ids as the allocator produces them: first_id, first_id + 8, first_id + 16 ...
[first_id + stride * i for i in [0:511]] => ids

"ids            : " + str(len(ids)) + ", from " + str(ids[0]) + " to " + str(ids[len(ids) - 1]) ^0
"allocator step : " + str(stride) ^0
"distinct ids   : " + str(len(ids)) + ", no key repeats, no key is hotter than another" ^0
"" ^0

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

def buckets_used(n):
    "|" => seen
    0 => used
    for k in ids:
        str(k % n) => slot
        if not ("|" + slot + "|" in seen):
            seen + slot + "|" => seen
            used + 1 => used
    return used

def busiest(n):
    0 => worst
    for b in [0:n - 1]:
        0 => here
        for k in ids:
            if k % n == b:
                here + 1 => here
        if here > worst:
            here => worst
    return worst

# ---- what each bucket count does with these keys ----

"buckets   gcd(step,buckets)   predicted used   counted used   busiest   even share" ^0
for n in [16, 32, 63, 64, 100, 101, 128]:
    gcd(stride, n) => g
    int(n / g) => predicted
    buckets_used(n) => counted
    busiest(n) => worst
    int(len(ids) / n) => fair
    ("  %-9s %-19s %-16s %-14s %-9s %s" % (str(n), str(g), str(predicted), str(counted), str(worst), str(fair)))^0
"" ^0

"  the predicted and the counted column are two different methods and agree" ^0
"  on every row: one divides by the common factor, the other bucket-counts" ^0
"  all " + str(len(ids)) + " keys" ^0
"" ^0

# ---- the deployed configuration ----

64 => deployed
gcd(stride, deployed) => g_dep
buckets_used(deployed) => used_dep
busiest(deployed) => worst_dep
int(len(ids) / deployed) => fair_dep

"the deployed configuration, " + str(deployed) + " buckets" ^0
("  buckets that receive a key      : %s of %s" % (str(used_dep), str(deployed)))^0
("  buckets that receive nothing    : %s" % str(deployed - used_dep))^0
("  keys in the busiest bucket      : %s" % str(worst_dep))^0
("  keys per bucket if spread even  : %s" % str(fair_dep))^0
("  the busiest bucket carries      : %sx its share" % str(int(worst_dep / fair_dep)))^0
"" ^0

# ---- the control ----
#
# The same hash, the same keys, the same code path. Only the bucket count
# changes, from a power of two to a prime, so that it shares no factor with
# the allocator's step.

101 => prime_buckets
"control - the same keys with " + str(prime_buckets) + " buckets" ^0
("  gcd(%s, %s) : %s" % (str(stride), str(prime_buckets), str(gcd(stride, prime_buckets))))^0
("  buckets used : %s of %s" % (str(buckets_used(prime_buckets)), str(prime_buckets)))^0
("  busiest      : %s against an even share of %s" % (str(busiest(prime_buckets)), str(int(len(ids) / prime_buckets))))^0
"  the hash function is not edited, so the hash function was not the fault" ^0
"" ^0

# ---- the control that the test ran ----
#
# Keys with a step of 1 stand in for the random keys the uniformity test uses.
# Against a step of 1, every bucket count shares no factor worth having.

"control - what the uniformity test measured" ^0
for s in [1, 3, 8]:
    gcd(s, deployed) => g2
    ("  step %-3s -> gcd %-3s -> %s of %s buckets used" % (str(s), str(g2), str(int(deployed / g2)), str(deployed)))^0
"  a step of 1 uses every bucket, which is what the test saw and reported" ^0
"  the test was correct about the input it was given" ^0
"" ^0

# ---- what would have caught it ----

"what each check can and cannot see" ^0
"  uniformity test with random keys : passes, and would fail a bad hash" ^0
"  uniformity test with real ids    : fails immediately, and was never run" ^0
"  a count of empty buckets in production : " + str(deployed - used_dep) + " of " + str(deployed) + ", no such metric" ^0
"  the bucket count was chosen for the mask, the step was chosen in 2014" ^0
"  and neither decision is wrong beside the other one on a page" ^0
"" ^0

"A power-of-two bucket count is a mask instead of a division and the hash" ^0
"passes a uniformity test on random keys. The allocator's step of " + str(stride) + " shares" ^0
"that factor: " + str(used_dep) + " of " + str(deployed) + " buckets hold every key, the busiest at " + str(int(worst_dep / fair_dep)) + "x its share," ^0
"and changing " + str(deployed) + " to " + str(prime_buckets) + " uses " + str(buckets_used(prime_buckets)) + " of them with the same hash." ^0

stride = 8
first_id = 1000
id_count = 512
ids = [first_id + stride * i for i in range(0, 512)]
print("ids            : " + str(len(ids)) + ", from " + str(ids[0]) + " to " + str(ids[len(ids) - 1]))
print("allocator step : " + str(stride))
print("distinct ids   : " + str(len(ids)) + ", no key repeats, no key is hotter than another")
print("")

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

def buckets_used(n):
    seen = "|"
    used = 0
    for k in ids:
        slot = str(k % n)
        if not "|" + slot + "|" in seen:
            seen = seen + slot + "|"
            used = used + 1
    return used

def busiest(n):
    worst = 0
    for b in range(0, n):
        here = 0
        for k in ids:
            if k % n == b:
                here = here + 1
        if here > worst:
            worst = here
    return worst

print("buckets   gcd(step,buckets)   predicted used   counted used   busiest   even share")
for n in [16, 32, 63, 64, 100, 101, 128]:
    g = gcd(stride, n)
    predicted = int(n / g)
    counted = buckets_used(n)
    worst = busiest(n)
    fair = int(len(ids) / n)
    print("  %-9s %-19s %-16s %-14s %-9s %s" % (str(n), str(g), str(predicted), str(counted), str(worst), str(fair)))
print("")
print("  the predicted and the counted column are two different methods and agree")
print("  on every row: one divides by the common factor, the other bucket-counts")
print("  all " + str(len(ids)) + " keys")
print("")
deployed = 64
g_dep = gcd(stride, deployed)
used_dep = buckets_used(deployed)
worst_dep = busiest(deployed)
fair_dep = int(len(ids) / deployed)
print("the deployed configuration, " + str(deployed) + " buckets")
print("  buckets that receive a key      : %s of %s" % (str(used_dep), str(deployed)))
print("  buckets that receive nothing    : %s" % str(deployed - used_dep))
print("  keys in the busiest bucket      : %s" % str(worst_dep))
print("  keys per bucket if spread even  : %s" % str(fair_dep))
print("  the busiest bucket carries      : %sx its share" % str(int(worst_dep / fair_dep)))
print("")
prime_buckets = 101
print("control - the same keys with " + str(prime_buckets) + " buckets")
print("  gcd(%s, %s) : %s" % (str(stride), str(prime_buckets), str(gcd(stride, prime_buckets))))
print("  buckets used : %s of %s" % (str(buckets_used(prime_buckets)), str(prime_buckets)))
print("  busiest      : %s against an even share of %s" % (str(busiest(prime_buckets)), str(int(len(ids) / prime_buckets))))
print("  the hash function is not edited, so the hash function was not the fault")
print("")
print("control - what the uniformity test measured")
for s in [1, 3, 8]:
    g2 = gcd(s, deployed)
    print("  step %-3s -> gcd %-3s -> %s of %s buckets used" % (str(s), str(g2), str(int(deployed / g2)), str(deployed)))
print("  a step of 1 uses every bucket, which is what the test saw and reported")
print("  the test was correct about the input it was given")
print("")
print("what each check can and cannot see")
print("  uniformity test with random keys : passes, and would fail a bad hash")
print("  uniformity test with real ids    : fails immediately, and was never run")
print("  a count of empty buckets in production : " + str(deployed - used_dep) + " of " + str(deployed) + ", no such metric")
print("  the bucket count was chosen for the mask, the step was chosen in 2014")
print("  and neither decision is wrong beside the other one on a page")
print("")
print("A power-of-two bucket count is a mask instead of a division and the hash")
print("passes a uniformity test on random keys. The allocator's step of " + str(stride) + " shares")
print("that factor: " + str(used_dep) + " of " + str(deployed) + " buckets hold every key, the busiest at " + str(int(worst_dep / fair_dep)) + "x its share,")
print("and changing " + str(deployed) + " to " + str(prime_buckets) + " uses " + str(buckets_used(prime_buckets)) + " of them with the same hash.")

ids            : 512, from 1000 to 5088
allocator step : 8
distinct ids   : 512, no key repeats, no key is hotter than another

buckets   gcd(step,buckets)   predicted used   counted used   busiest   even share
  16        8                   2                2              256       32
  32        8                   4                4              128       16
  63        1                   63               63             9         8
  64        8                   8                8              64        8
  100       4                   25               25             21        5
  101       1                   101              101            6         5
  128       8                   16               16             32        4

  the predicted and the counted column are two different methods and agree
  on every row: one divides by the common factor, the other bucket-counts
  all 512 keys

the deployed configuration, 64 buckets
  buckets that receive a key      : 8 of 64
  buckets that receive nothing    : 56
  keys in the busiest bucket      : 64
  keys per bucket if spread even  : 8
  the busiest bucket carries      : 8x its share

control - the same keys with 101 buckets
  gcd(8, 101) : 1
  buckets used : 101 of 101
  busiest      : 6 against an even share of 5
  the hash function is not edited, so the hash function was not the fault

control - what the uniformity test measured
  step 1   -> gcd 1   -> 64 of 64 buckets used
  step 3   -> gcd 1   -> 64 of 64 buckets used
  step 8   -> gcd 8   -> 8 of 64 buckets used
  a step of 1 uses every bucket, which is what the test saw and reported
  the test was correct about the input it was given

what each check can and cannot see
  uniformity test with random keys : passes, and would fail a bad hash
  uniformity test with real ids    : fails immediately, and was never run
  a count of empty buckets in production : 56 of 64, no such metric
  the bucket count was chosen for the mask, the step was chosen in 2014
  and neither decision is wrong beside the other one on a page

A power-of-two bucket count is a mask instead of a division and the hash
passes a uniformity test on random keys. The allocator's step of 8 shares
that factor: 8 of 64 buckets hold every key, the busiest at 8x its share,
and changing 64 to 101 uses 101 of them with the same hash.

Trace event types