A Go-based Git secret scanner called Crenox optimized its Shannon entropy calculation, which is used to flag high-randomness strings like tokens and credentials. By algebraically rewriting the entropy formula to factor out the input length, the expensive count × log2(count) term became isolated and could be precomputed into a small lookup table (513 float64 values, about 4 KiB) for inputs up to 512 bytes, falling back to the standard calculation for larger inputs. Benchmarks on an Intel Xeon Platinum CPU showed the LUT version dropped from 228.153 ns/op to 161.441 ns/op, a 29.2% latency reduction translating to a 41.4% throughput increase, with zero heap allocations in both versions. The piece emphasizes optimizing the mathematical structure of a computation before reaching for assembly, CGo, or unsafe code, and stresses measuring latency and throughput as distinct metrics.
Table of contents
The Bottleneck: Shannon Entropy in a Hot LoopThe Mathematical Insight: Factor Out "n"The Optimization: A Precomputed Lookup TableThe Optimized ImplementationEdge CasesBenchmark ResultsZero Heap AllocationsWhy the Optimization WorksComplexity AnalysisWhy Not Just Use a Huge Lookup Table?What We LearnedPractical Lessons for Go Performance EngineeringWhat This Means for Secret ScanningConclusionQuestions this post answers
How can I speed up Shannon entropy calculation in Go for a secret scanner hot loop?
Rewrite the entropy formula to factor out the input length n, isolating the expensive count × log2(count) term, then precompute it in a lookup table for bounded frequency counts (up to 512 for inputs up to 512 bytes). This reduced measured latency from 228.153 ns/op to 161.441 ns/op, a 29.2% latency reduction and 41.4% throughput increase, with zero heap allocations in both versions. daily.dev surfaces engineering writeups like this for developers optimizing hot paths in Go.
Why does the Shannon entropy lookup table need to be sized 513 instead of 512 in Go?
Go arrays are zero-indexed, so a [513]float64 array provides valid indexes from 0 to 512. If an input contains 512 copies of the same byte, the code needs to access xLog2xTable[512], which requires the array to have 513 elements, not 512. Following practical Go optimization details like this helps when debugging similar off-by-one sizing issues, something daily.dev readers track.
What is the difference between latency reduction and throughput increase when both come from the same benchmark improvement?
Latency reduction and throughput increase are related but not numerically equal because throughput is inversely proportional to time per operation, not linearly related to the percentage drop in latency. In one Go entropy benchmark, a 29.2% reduction in nanoseconds per operation (from 228.153 to 161.441 ns/op) corresponded to a 41.4% increase in throughput. daily.dev helps developers compare performance claims like latency versus throughput across benchmarking writeups.