# Performance Review Report

**Branch**: feat-176-empirical-sparse-ngram-weights -> main
**Date**: 2026-05-13

## Issues in Your Changes (BLOCKING)

### CRITICAL

(none)

### HIGH

**Const table bloat: 9596-entry `BIGRAM_WEIGHTS` static slice embeds ~56 KiB into every binary linking rskim-search** - `crates/rskim-search/src/weights.rs:15`
**Confidence**: 82%
- Problem: The `BIGRAM_WEIGHTS` const table contains 9596 `(u16, f32)` tuples (6 bytes each = ~56 KiB raw data). Since `rskim-search` is a library crate, this static data is embedded in every binary that links it. Currently only `rskim` links `rskim-search`, so the impact is a single binary. However, as more crates in the workspace start depending on `rskim-search` (the PR description says this is Wave 0 / foundation), the 56 KiB table will be duplicated per binary if statically linked. Additionally, the 350 KiB source file (`weights.rs`) adds measurable compile time cost on every change to `rskim-search` (the compiler must parse and type-check all 9596 entries).
- Fix: Consider a compact binary format loaded at startup via `include_bytes!` or a lazy static, instead of a const array literal. For example:
  ```rust
  // In build.rs or a data file:
  static WEIGHTS_DATA: &[u8] = include_bytes!("../data/bigram_weights.bin");
  
  // Interpret as &[(u16, f32)] at runtime with zero-copy:
  fn weights() -> &'static [(u16, f32)] {
      // Safety: data is generated by codegen with known alignment
      // Or use bytemuck/zerocopy for safe transmute
  }
  ```
  This would reduce source file size from 350 KiB to ~1 KiB, cut compile time for this module, and keep the same O(log n) binary search performance. The 56 KiB binary payload stays the same either way (data must live somewhere), but the compile-time cost drops significantly.

## Issues in Code You Touched (Should Fix)

### MEDIUM

**`is_border_bigram` called per-bigram with full token scan: O(bigrams * tokens) per query** - `crates/rskim-research/src/validate.rs:62`
**Confidence**: 80%
- Problem: In `border_weighted_selectivity`, for each bigram window in the query, `is_border_bigram` iterates over all tokens. For a query of length L with T tokens, this is O(L * T). The function is called from `run_validation` across 9 test queries, so the total work is modest today. However, if the validation suite grows or this scoring function is promoted to the production search path, the per-bigram linear scan over tokens becomes a bottleneck.
- Fix: Pre-compute a `HashSet<u16>` of border bigram keys before the main loop:
  ```rust
  let border_keys: HashSet<u16> = tokens.iter()
      .flat_map(|t| {
          let mut keys = Vec::new();
          if t.len() >= 2 {
              keys.push(encode_bigram(t[0], t[1]));
              keys.push(encode_bigram(t[t.len()-2], t[t.len()-1]));
          }
          keys
      })
      .collect();
  // Then in the loop:
  let multiplier = if border_keys.contains(&key) { BORDER_MULTIPLIER } else { 1.0 };
  ```
  This reduces per-bigram lookup from O(T) to O(1).

**`covering_set_heuristic` has O(n^2) coverage check** - `crates/rskim-research/src/validate.rs:174`
**Confidence**: 80%
- Problem: Inside the selection loop, `covered.iter().all(|&c| c)` scans the entire `covered` vec on every iteration. For a query of length L with C candidates, worst case is O(L * C). Since queries are short strings (< 30 bytes), this is not a practical concern today, but it violates the project's reliability principle of bounded complexity in loops.
- Fix: Track a `remaining_uncovered` counter and decrement it when marking positions:
  ```rust
  let mut remaining = bytes.len();
  for (key, _, pos) in candidates {
      let newly_covered = (!covered[pos] as usize) + (!covered[pos + 1] as usize);
      if newly_covered > 0 {
          covered[pos] = true;
          covered[pos + 1] = true;
          remaining -= newly_covered;
          selected.push(key);
      }
      if remaining == 0 { break; }
  }
  ```

## Pre-existing Issues (Not Blocking)

(none -- all code is new in this branch)

## Suggestions (Lower Confidence)

- **`extract_bigrams_from_corpus` is single-threaded with SHA-256 per file** - `crates/rskim-research/src/extract.rs:73` (Confidence: 65%) -- The corpus iteration hashes every file with SHA-256 and accumulates bigram DFs sequentially. With 98 files this is fast, but if the corpus grows to thousands of files, parallelizing extraction (e.g., with rayon) would help. The mutable state (`df_map`, `seen_hashes`) would need a two-phase approach: parallel extraction then serial merge.

- **552 KiB JSON data file checked into the repo** - `crates/rskim-search/data/bigram_weights.json` (Confidence: 62%) -- The 38K-line JSON file is a generated artifact. If it is only consumed by `codegen` at development time, it could live in a `.gitignore`d location and be regenerated on demand, reducing repo clone size. However, having it checked in ensures reproducibility, which may be the deliberate choice.

- **`border_weighted_selectivity` false-positive border detection** - `crates/rskim-research/src/validate.rs:87` (Confidence: 70%) -- The condition `window[0] == first2[0] || window[0] == last2[0]` matches any bigram whose first byte equals the first byte of any token's border, which is very broad. For single-character tokens like `*` in "SELECT * FROM", every bigram containing `*` gets the border multiplier. This over-triggers the multiplier and may skew validation results, though the performance impact is negligible -- the concern is correctness/accuracy of the scoring, not speed.

## Summary

| Category | CRITICAL | HIGH | MEDIUM | LOW |
|----------|----------|------|--------|-----|
| Blocking | 0 | 1 | 0 | - |
| Should Fix | - | 0 | 2 | - |
| Pre-existing | - | - | 0 | 0 |

**Performance Score**: 7/10
**Recommendation**: APPROVED_WITH_CONDITIONS

The production-facing change is well-designed: a sorted const table with O(log n) binary search lookup (`bigram_weight`) is the right data structure for this use case. The 56 KiB static data payload is reasonable for a code search library. The HIGH finding about compile-time cost of the 350 KiB source file is worth addressing before the table grows (e.g., when real corpus data replaces synthetic data), but is not blocking for Wave 0. The MEDIUM findings in the research crate are algorithmic inefficiencies that are acceptable for a developer-only tool at current scale but should be cleaned up before the scoring logic migrates to production.
