A 41% Throughput Win That Was Algebra, Not Assembly

Khaled Hani, writing about the Crenox Git secret scanner, reports that the entropy stage of its detection pipeline got 41.4% more throughput after the Shannon entropy formula was algebraically restructured and the expensive part moved into a precomputed lookup table ^[1][2]. The interesting part is what was not used: the post is explicit that the fix was not CGo, assembly, or unsafe ^[3], which is the usual destination when someone decides a hot loop is out of headroom.

The constraint is real. Crenox runs as a pre-commit hook on a developer workstation before every commit, so the scanner has to finish its work without adding noticeable latency to the commit ^[4]. Detection runs in three tiers: Aho-Corasick matching over 125-plus known provider patterns, then Shannon entropy analysis on high-randomness candidates such as generic tokens, hashes and credentials, then context-aware verification to suppress false positives from test fixtures and mock data ^[5]. Tier 2 is called hundreds of thousands of times, according to the author, which is what makes per-call floating point arithmetic worth attacking ^[6].

The naive implementation builds a 256-entry frequency table, then for each non-zero count computes p = count/n and accumulates -p*log2(p): a float conversion, a division, a math.Log2 call and more arithmetic per distinct byte value ^[7][8]. Substituting p = c/n and applying the logarithm identity gives H = log2(n) - (1/n) * sum(c*log2(c)), because every byte contributes exactly once to the frequency table so the counts sum to n ^[9]. Mathematically identical, per the post ^[10], but the loop body is now c*log2(c) on an integer with a bounded range ^[11].

Bounded is the operative word. If the input is at most 512 bytes, no individual byte frequency can exceed 512, so every value of c*log2(c) the loop will ever need can be computed once at init into a [513]float64 array, sized 513 rather than 512 because Go arrays are zero-indexed and a run of 512 identical bytes needs index 512 ^[12][13][14]. That table is 4,104 bytes, roughly 4.01 KiB ^[15]. The fast path then does one math.Log2, on n, instead of one per distinct byte present, which in the naive version can be up to 256 ^[17]. Inputs over 512 bytes fall back to the original calculation ^[16]. Allocations stayed at zero per operation ^[2].

Read the 41.4% figure the right way. A 41.4% throughput increase corresponds to about 29% less time per call, which is a solid but not exotic result for removing a transcendental function from a loop ^[18]. It also only applies below the 512-byte threshold; anything larger takes the fallback and gets nothing ^[16].

What to watch: whether real scanner inputs actually sit under 512 bytes in practice, because a line-oriented scanner will and a blob-oriented one will not; whether the fallback path becomes the new hot path on large files, which would argue for a segmented or chunked table rather than a bigger one; and whether the two code paths agree closely enough at the entropy thresholds that drive Tier 3, since a candidate sitting on the boundary can be classified differently by two routines that are equivalent on paper. The transferable lesson is the ordering: rewrite the expression, bound the domain, precompute, and only then consider the escape hatches.