How We Increased Shannon Entropy Throughput in Go by 41% Using a Lookup Table.

How We Increased Shannon Entropy Throughput in Go by 41% Using a Lookup Table.

Author: Khaled Hani

Repository: Crenox

When building a high-performance Git secret scanner, every microsecond matters.

A pre-commit hook runs on a developer's workstation before every commit, so the scanner has to do a lot of work without adding noticeable latency to the development workflow.

Crenox uses a three-tier detection pipeline:

1. Tier 1: Aho-Corasick pattern matching across 125+ known provider patterns.
2. Tier 2: Shannon entropy analysis for high-randomness candidates such as generic tokens, hashes, and credentials.
3. Tier 3: Context-aware verification to reduce false positives from test fixtures, mock data, and non-secret identifiers.

During optimization of the entropy stage, we found an important opportunity: the standard Shannon entropy formula performs repeated floating-point operations inside a hot loop.

The solution was not CGo, Assembly, or unsafe code.

It was algebra.

By rewriting the entropy equation and precomputing a small lookup table, the benchmark below shows a 41.4% increase in throughput, while maintaining 0 heap allocations per operation.

---

The Bottleneck: Shannon Entropy in a Hot Loop

Shannon entropy is commonly defined as:

$$H(X) = -\sum_{i=1}^{k} P(x_i)\log_2 P(x_i)$$

For a byte slice, we can define:

• n as the total number of bytes.
• cᵢ as the number of occurrences of byte value i.
• P(xᵢ) = cᵢ / n as the empirical probability of that byte.

A straightforward Go implementation looks like this:

func ShannonNaive(data []byte) float64 {
    if len(data) == 0 {
        return 0
    }

    var freq [256]int

    for _, b := range data {
        freq[b]++
    }

    n := float64(len(data))
    var entropy float64

    for _, count := range freq {
        if count == 0 {
            continue
        }

        p := float64(count) / n
        entropy -= p * math.Log2(p)
    }

    return entropy
}

The implementation is perfectly valid.

The problem is that the calculation happens repeatedly for every non-zero byte frequency.

For each distinct byte, the hot loop performs:

• a floating-point conversion,
• a floating-point division,
• a math.Log2 calculation,
• and additional floating-point arithmetic.

When this function is called hundreds of thousands of times, those operations become worth optimizing.

---

The Mathematical Insight: Factor Out "n"

The key observation is that the probability is:

$$P(x_i) = \frac{c_i}{n}$$

Substituting that into Shannon entropy gives:

$$H(X) = -\sum_{c_i>0} \frac{c_i}{n} \log_2\left(\frac{c_i}{n}\right)$$

Now use the logarithm identity:

$$\log_2\left(\frac{a}{b}\right) = \log_2(a) - \log_2(b)$$

Therefore:

$$H(X) = -\sum_{c_i>0} \frac{c_i}{n} \left[ \log_2(c_i) - \log_2(n) \right]$$

Expanding the expression:

$$H(X) = -\frac{1}{n} \sum_{c_i>0} c_i\log_2(c_i) + \frac{\log_2(n)}{n} \sum_{c_i>0} c_i$$

Every byte in the input contributes exactly once to the frequency table, so:

$$\sum_{c_i>0} c_i = n$$

This simplifies the second term:

$$\frac{\log_2(n)}{n} \sum_{c_i>0} c_i = \frac{\log_2(n)}{n} \cdot n = \log_2(n)$$

The entire entropy calculation therefore becomes:

$$\boxed{ H(X) = \log_2(n) - \frac{1}{n} \sum_{c_i>0} c_i\log_2(c_i) }$$

This is mathematically equivalent to the original Shannon entropy formula.

Why is this useful?

The original implementation calculates:

(count / n) × log₂(count / n)

inside the loop.

The rewritten form only needs:

count × log₂(count)

for each frequency.

More importantly, count is an integer with a bounded range.

That gives us an opportunity to precompute the expensive part.

---

The Optimization: A Precomputed Lookup Table

For the fast path, we target inputs up to 512 bytes.

The frequency of any individual byte can never exceed the total input length.

Therefore, when:

n <= 512

we know that:

1 <= cᵢ <= 512

We can precompute:

$$f(x) = x\log_2(x)$$

for every possible frequency.

In Go:

var xLog2xTable [513]float64

func init() {
    for i := 1; i <= 512; i++ {
        xLog2xTable[i] = float64(i) * math.Log2(float64(i))
    }
}

The table contains 513 float64 values:

513 × 8 bytes = 4,104 bytes ≈ 4.01 KiB

That's a very small amount of memory for eliminating repeated logarithm calculations from the hot path.

---

The Optimized Implementation

The resulting implementation uses the lookup table for inputs up to 512 bytes and keeps the original mathematical calculation as a fallback for larger buffers:

func Shannon(data []byte) float64 {
    n := len(data)

    if n == 0 {
        return 0
    }

    var freq [256]int

    for _, b := range data {
        freq[b]++
    }

    // Fast path for inputs <= 512 bytes.
    if n <= 512 {
        var sum float64

        for _, count := range freq {
            if count > 0 {
                sum += xLog2xTable[count]
            }
        }

        return math.Log2(float64(n)) - (sum / float64(n))
    }

    // Fallback path for larger inputs.
    fn := float64(n)
    var entropy float64

    for _, count := range freq {
        if count > 0 {
            p := float64(count) / fn
            entropy -= p * math.Log2(p)
        }
    }

    return entropy
}

There are two important details here.

1. Why is the table [513] instead of [512]?

Go arrays are zero-indexed.

A [513]float64 array provides indexes:

0 ... 512

If the input contains 512 copies of the same byte, then:

count = 512

and the implementation needs:

xLog2xTable[512]

Therefore, [513]float64 is the correct size.

2. Why do we need a fallback?

The LUT only covers frequencies up to 512.

For larger inputs, a byte frequency can exceed 512.

Instead of making the lookup table arbitrarily large, we use the original calculation for those inputs.

This keeps the optimization bounded while preserving correctness for larger buffers.

---

Edge Cases

The implementation also handles the important boundary conditions.

Empty input

n = 0

The function returns:

H(X) = 0

before performing any logarithm calculation.

One-byte input

For:

data = "A"

the only frequency is:

c₁ = 1

Since:

$$\log_2(1) = 0$$

the entropy is:

H(X) = 0

Repeated byte

For a buffer containing only "A":

AAAAAAAA...

there is only one possible symbol, so entropy is zero regardless of the length.

Two equally frequent bytes

For:

AB

both symbols have probability 1/2, giving:

$$H(X) = -\left( \frac{1}{2}\log_2\frac{1}{2} + \frac{1}{2}\log_2\frac{1}{2} \right) = 1$$

The 512-byte boundary

At:

n = 512

the LUT path is used.

At:

n = 513

the fallback path is used.

Both paths implement the same mathematical definition of Shannon entropy.

---

Benchmark Results

We compared the standard implementation with the LUT-based implementation using Go's benchmark tooling:

go test -bench=. -benchmem

The benchmark run produced:

goos: linux
goarch: amd64
pkg: github.com/crenoxhq/crenox/v2/internal/entropy
cpu: Intel(R) Xeon(R) Platinum

BenchmarkShannonStandard-8       1456561     228.153 ns/op     0 B/op     0 allocs/op
BenchmarkShannonLUT-8            2041219     161.441 ns/op     0 B/op     0 allocs/op

Latency

The standard implementation takes approximately:

228.153 ns/op

The LUT implementation takes:

161.441 ns/op

The reduction in per-operation latency is:

$$\frac{228.153 - 161.441}{228.153} \approx 29.24\%$$

So the LUT implementation reduces measured latency by approximately 29.2%.

Throughput

Throughput is inversely proportional to time per operation.

From the measured ns/op values:

$$\text{Throughput}_{\text{standard}} = \frac{10^9}{228.153} \approx 4.38\text{M operations/sec}$$

and:

$$\text{Throughput}_{\text{LUT}} = \frac{10^9}{161.441} \approx 6.19\text{M operations/sec}$$

Therefore:

$$\frac{6.19\text{M}}{4.38\text{M}} - 1 \approx 41.32\%$$

That's approximately a 41.4% increase in throughput.

This distinction is important:

• Latency reduction: ~29.2%
• Throughput increase: ~41.4%

The N values shown by go test -bench are benchmark iteration counts. They should not be interpreted directly as operations per second.

---

Zero Heap Allocations

Both implementations report:

0 B/op
0 allocs/op

This means the benchmark observed zero heap allocations per operation.

The optimization therefore improves the computational path without introducing an allocation-heavy data structure or additional runtime dependency.

The frequency table remains a fixed-size array:

var freq [256]int

and the lookup table is also fixed-size:

var xLog2xTable [513]float64

---

Why the Optimization Works

The important part of this optimization isn't simply the lookup table.

The real performance improvement came from changing the structure of the computation.

The original formula repeatedly evaluates:

$$P(x_i)\log_2(P(x_i))$$

The rewritten formula isolates the expensive component:

$$c_i\log_2(c_i)$$

And because cᵢ belongs to a small integer domain on the fast path, the result can be precomputed.

Instead of calculating:

float64(count) * math.Log2(float64(count))

every time, the hot loop performs:

xLog2xTable[count]

That is the central idea:

«Before optimizing the instructions, optimize the computation.»

---

Complexity Analysis

Both implementations still have the same asymptotic complexity.

For an input of length n:

• Frequency counting: $\mathcal{O}(n)$
• Entropy calculation: The alphabet is the 256 possible byte values: $\mathcal{O}(256)$

Since 256 is constant:

$$\mathcal{O}(n + 256) = \mathcal{O}(n)$$

So the LUT does not change the Big-O complexity.

Instead, it reduces the constant cost of the entropy calculation.

This is an important distinction in performance engineering:

«An optimization does not need to change Big-O complexity to produce a meaningful real-world speedup.»

---

Why Not Just Use a Huge Lookup Table?

A natural question is:

«Why stop at 512?»

We could build a much larger table, but there is a trade-off.

The goal is not to replace every possible input with a massive precomputed structure.

The goal is to optimize the common short-input path while keeping:

• memory usage small,
• initialization simple,
• the implementation easy to understand,
• and a correct fallback for larger inputs.

The 512-byte threshold is therefore an implementation choice that should be validated against the actual workload.

If profiling shows that larger candidates are common, the threshold can be revisited and benchmarked again.

---

What We Learned

This optimization reinforced a useful lesson about Go performance.

The first instinct when optimizing a hot path is often to think about:

• Assembly
• SIMD
• unsafe code
• CGo
• compiler tricks

But none of those were necessary here.

The biggest opportunity was hidden in the mathematical representation itself.

We started with:

$$H(X) = -\sum P(x_i)\log_2(P(x_i))$$

and transformed it into:

$$H(X) = \log_2(n) - \frac{1}{n} \sum c_i\log_2(c_i)$$

That exposed a bounded integer input to the expensive part of the calculation.

Once that happened, a small lookup table became possible.

---

Practical Lessons for Go Performance Engineering

There are several general lessons here:

1. Optimize the algorithm before optimizing the instructions: A better mathematical formulation can eliminate work that no amount of low-level optimization can make free.
2. Look for bounded domains: If an expensive function only receives a small set of possible inputs, precomputation can be extremely effective.
3. Measure instead of assuming: A lookup table is not automatically faster. The only reason to keep this optimization is that the benchmark demonstrates a measurable improvement for the workload being tested.
4. Keep a safe fallback: The LUT is optimized for a bounded range, but larger inputs still need correct handling. A fallback keeps the optimization from becoming a correctness constraint.
5. Measure latency and throughput separately: A reduction in ns/op and an increase in throughput are related, but they are not the same percentage. Reporting both makes performance claims much easier to audit.

---

What This Means for Secret Scanning

Shannon entropy is useful as one signal in secret detection, particularly when dealing with high-randomness candidates that don't match known provider-specific patterns.

But entropy alone is not enough to determine whether a string is a secret.

A high-entropy string can be:

• compressed data,
• a hash,
• an identifier,
• generated test data,
• or a legitimate random value.

That's why Crenox combines entropy analysis with pattern matching and contextual verification.

The optimization discussed here improves the cost of one component of that pipeline; it does not change the detection model itself.

---

Conclusion

High-performance Go code does not always require Assembly, CGo, or unsafe optimizations.

Sometimes the highest-leverage optimization starts with a mathematical equation.

In our case, we:

1. Rewrote the Shannon entropy formula to factor out the input length.
2. Reduced repeated calculations inside the hot loop.
3. Used a small lookup table for the bounded frequency range.
4. Preserved a fallback path for larger inputs.
5. Maintained zero heap allocations in the benchmark.
6. Measured a 29.2% reduction in per-operation latency.
7. Measured a 41.4% increase in throughput.

The complete implementation is part of Crenox on GitHub, an open-source security tool for detecting secrets before they reach your repository.

If you're interested in Go performance optimization, Shannon entropy, secret scanning, Git security, or DevSecOps tooling, the implementation is available for inspection and experimentation.

---

Final Note on the Benchmark

Benchmark results are dependent on the CPU, Go version, compiler, input distribution, and benchmark methodology.

The numbers in this article represent the specific benchmark run shown above. They should be treated as measured results for that environment, not as a universal speedup across every system.

For production performance work, run the benchmark multiple times and compare results with a statistical benchmark tool such as benchstat.

Repository: https://github.com/crenoxhq/crenox