I Hashed Every Word Twice to Count It Once

I was profiling a log parser last week. Nothing dramatic, it just counts how often each error code shows up in a day of lines. The hot loop is a dictionary bump: see a code, increment its counter. It's the most boring code in the file. It also sat higher in the profiler than I expected, so I went looking, and the reason turned out to be almost funny.

Here's the loop, more or less how everyone writes it:

if (counts.TryGetValue(code, out int c))
    counts[code] = c + 1;
else
    counts[code] = 1;

Reads exactly like what you mean. And it hashes the key twice. TryGetValue computes the hash, walks the bucket, finds the entry. Then counts[code] = ... throws all of that away and does the whole thing over to write. Same key, same hash, same bucket walk, twice per token. On the miss path it's the same story: one lookup to fail, another to insert.

There's a method that skips the second trip. CollectionsMarshal.GetValueRefOrAddDefault finds or creates the slot once and hands you a ref pointing straight into it:

ref int slot = ref CollectionsMarshal.GetValueRefOrAddDefault(counts, code, out _);
slot++;

One hash, one bucket walk, then you mutate the storage in place. If the key was missing it gets added as default(int), which is 0, so the first slot++ lands it at 1. The out bool tells you whether the key already existed. I don't need that here, so I throw it away.

The measurement

I wanted a real number, so I built a small counter over 5 million tokens drawn from a 20,000-word vocabulary, skewed so a handful of words dominate and there's a long rare tail. Roughly what actual text looks like. Both versions run the same input. I assert the two histograms come out identical first, then time each as the median of 11 runs. Allocations come from GC.GetAllocatedBytesForCurrentThread. Workstation GC, small Linux container. This isn't a lab and I'm not chasing microseconds, I care about the ratio.

tokens: 5,000,000, distinct vocab: 20,000

identical results: True  (distinct keys: 20,000)

TryGetValue + indexer (two lookups)        median   160.0 ms   ~   1,914 KB/run
GetValueRefOrAddDefault (one lookup)       median    95.0 ms   ~   1,914 KB/run

About 1.7x faster on the loop, and it held every run I did. The two-lookup version bounced between 157 and 170 ms. The ref version parked around 95.

Now the part I actually like, because it's the honest part. Look at the allocations column. They're identical. Both build the same dictionary, same 20,000 string keys, same backing arrays. GetValueRefOrAddDefault doesn't save you a single byte. It's not a memory trick. All it removes is CPU: the redundant hash and probe on every one of those 5 million bumps. If your workload is allocation-bound, this changes nothing for you. If it's counting or aggregating in a tight loop, it's most of the cost.

Why the gap is that big

The saving scales with how often you land on a key that already exists. In a Zipf-ish corpus most tokens are repeats, so most iterations take the "found it" path, which is the exact path where the naive version pays for two full lookups. Feed it 5 million unique keys instead and the gap shrinks, because the add path does real work either way. The win is proportional to your update-to-insert ratio, and counters live at the far update-heavy end of that. That's why this one shows off so well and a mostly-insert workload wouldn't.

There's a sharp edge here, and it's worth saying out loud. The ref you get back points directly into the dictionary's internal storage, and it stays valid only until the next structural change. Add or remove a key while you're still holding that ref and it can dangle. After a resize you might be writing into the wrong slot entirely. So the rule is simple: grab the ref, mutate it, let it go. Don't stash it, don't hold it across another insert into the same dictionary. For a bump-in-place loop that's how you'd naturally write it anyway, which is exactly why counters fit and a dictionary you're rewriting mid-iteration does not.

One more caution before you sprinkle this everywhere. The namespace is CollectionsMarshal. That word is telling you it's the low-level door. For a dictionary you touch a few hundred times, TryGetValue is clearer and nobody will ever measure the difference. My honest take is that the ref version earns its keep only when the counter loop is genuinely hot, which for me means parsing and aggregation. Everywhere else readability wins and I leave the boring version exactly where it is.

Full runnable sample: https://github.com/ssukhpinder/dev-to-code-samples/tree/main/022-dictionary-ref-upsert

What's the hottest dictionary loop in your codebase, and have you ever actually counted the lookups it does? I'd be curious whether the ratio holds on real data.

— still timing loops nobody asked me to time