CategoricalStats::update is O(n*m) due to HLL count on every insert

[lakshmanpasala]

Summary

CategoricalStats::update() in src/stats.rs calls hll.count() on every single update after the cardinality cap (10,000 unique values) is hit. HyperLogLogPlus::count() is O(m) where m = 2^precision = 65,536 registers. This turns the per-line stats accumulation from O(1) to O(m) per line, causing quadratic scaling at large inputs.

Evidence

Benchmarked with synthetic logs at multiple scales:

Lines	Time	Expected (linear)	Actual ratio vs linear
10K	0.08s	—	baseline
50K	1.94s	0.4s	4.9x over linear
100K	6.77s	0.8s	8.5x over linear
1M	105s	8s	13x over linear

Isolated the cause:

• 100K constant lines (no variables): 0.21s
• 100K lines with same variable values: 0.20s
• 100K lines with high-cardinality variables (100K unique hex IDs): 3.09s

The cost is entirely in high-cardinality variable processing, not CLP encoding or Drain3 clustering.

Root cause

src/stats.rs lines 127-135:

if self.capped {
    if let Some(count) = self.exact_counts.get_mut(value) {
        *count += 1;
    }
    if let Some(ref mut hll) = self.hll {
        hll.insert(&value.to_string());       // unnecessary String allocation
        self.cached_unique = hll.count().round() as u64;  // O(65536) on EVERY call
    }
}

Two issues:

1. hll.count() called on every update — this is O(2^16) = O(65536) per call. After the 10K cap, every remaining line pays this cost. At 100K lines × 4 variable slots × 65K register scans ≈ 26 billion operations.
2. value.to_string() allocation — unnecessary heap allocation on every insert in capped mode.

Fix

1. Remove hll.count() from the hot loop — compute it lazily in unique_count() only when called
2. Track a dirty flag or just always recompute in unique_count() (called once per pattern at output time, not per line)
3. Avoid the .to_string() allocation if the HLL API accepts &str

Expected improvement: 100K lines should drop from ~6.8s to ~0.3-0.5s (in line with the constant-line baseline).