🌀 Secret Technique Scroll

Architecture

The inner workings of instant-grep — from regex to result in under a millisecond. Every technique honed to perfection.

🌀 Rasengan Pipeline

The complete query pipeline — six stages of pure concentrated energy.

╔══════════════════════════════════════════════════════════════════╗
║          ✦ RASENGAN PIPELINE — FORBIDDEN SCROLL OF SEARCH ✦          ║
╚══════════════════════════════════════════════════════════════════╝

  User Input
      │
      ▼
┌─────────────────────────────────────────┐
│  Stage 1 · regex-syntax Extractor       │  query/extract.rs
│  "async fn" → literal fragments         │
└─────────────────┬───────────────────────┘
                  │
                  ▼
┌─────────────────────────────────────────┐
│  Stage 2 · Sparse N-gram Generation     │  index/ngram.rs
│  fragments → variable-length n-grams    │
└─────────────────┬───────────────────────┘
                  │
                  ▼
┌─────────────────────────────────────────┐
│  Stage 3 · Shadow Clone Selection       │  index/ngram.rs
│  all n-grams → minimal covering set     │  build_covering_ngrams()
└─────────────────┬───────────────────────┘
                  │
                  ▼
┌─────────────────────────────────────────┐
│  Stage 4 · Hash Table Lookup            │  index/reader.rs
│  n-grams → posting list offsets (mmap)  │
└─────────────────┬───────────────────────┘
                  │
                  ▼
┌─────────────────────────────────────────┐
│  Stage 5 · Posting List Intersection    │  index/reader.rs
│  sorted file ID lists → candidates      │
└─────────────────┬───────────────────────┘
                  │
                  ▼
┌─────────────────────────────────────────┐
│  Stage 6 · Parallel Regex Verification  │  Rayon threadpool
│  candidates → verified matches          │
└─────────────────────────────────────────┘
                  │
                  ▼
            ✓ Results  (p50: 0.9ms)

📂 Module Structure

src/index/ngram.rs

Core Algorithm

Sparse n-gram generation and covering set selection

hash_bigram() build_all_ngrams() build_covering_ngrams()

src/index/writer.rs

Index Build Pipeline

Walks filesystem, builds and serializes the index

build_index() write_lexicon() write_postings()

src/index/reader.rs

Index Query

mmap-backed hash table + posting list intersection

query_index() intersect_postings() mmap_open()

src/query/extract.rs

Regex → N-gram Conversion

Parses regex AST to extract searchable literal fragments

extract_ngrams() literal_fragments() NgramQuery

src/daemon.rs

Sage Mode Daemon

Unix socket server for sub-ms repeated queries

start_daemon() handle_connection() serve_query()

src/main.rs

CLI Entry Point

Command dispatch via clap — routes to index, search, status, watch, daemon, query

Commands enum clap::Parser dispatch()

💾 On-disk Format (.ig/ directory)

Three binary files, all memory-mapped for zero-copy access. INDEX_VERSION must be bumped when the format changes.

.ig/
├── lexicon.bin    — Hash table: u64(n-gram hash) → u32(posting offset) + u32(count)
├── postings.bin   — Sorted u32[] file IDs per n-gram (delta-encoded)
└── metadata.bin   — u32 version + u64[] mtime + []string file paths (null-separated)

lexicon.bin

Open-addressing hash table. Each slot: 8B key (n-gram hash) + 8B value (offset + count). Load factor: 0.7.

postings.bin

Concatenated sorted lists of file IDs. Each list referenced by lexicon offset + length. Intersection runs in O(n+m).

metadata.bin

Maps file IDs to paths. Stores mtimes for incremental rebuild detection. First 4 bytes: INDEX_VERSION.

🌀 Rasengan Algorithm — Sparse N-grams

Port of github.com/danlark1/sparse_ngrams (GitHub Blackbird)

Traditional trigram search uses every contiguous 3-character substring — expensive and produces many false positives. The Rasengan Algorithm uses variable-length n-grams that adapt to the string being indexed, concentrating energy where it matters.

✗ Naive Trigrams (weak jutsu)

"async" → trigrams:
"asy", "syn", "ync"
Problems:
• Fixed length loses selectivity
• Many false candidates
• Large index size

✓ Sparse N-grams (Rasengan)

"async fn" → covering set:
"async", "fn"
Advantages:
• Variable length = high selectivity
• Fewer candidates to verify
• Smaller index, faster lookup

How hash_bigram() works:

Each n-gram is hashed by combining its characters using a polynomial rolling hash with a prime base. The hash fits in a u64 — enabling the open-addressing hash table lookup to be a single memory access when the index is warm in the OS page cache (or the daemon's mmap).

👥 Shadow Clone Selection — Covering Algorithm

From all possible n-grams for a query, we need only the minimal covering set — the smallest collection of n-grams that together guarantee we find all matching files. Like selecting the perfect shadow clones: enough to cover every angle, no redundancy.

build_covering_ngrams() pseudocode:

fn build_covering_ngrams(ngrams: Vec<Ngram>) → Vec<Ngram> {
    sort ngrams by (position, length desc)
    greedily select ngrams that cover uncovered positions
    return minimal subset that covers the full query string
}

🐸 Sage Mode — Daemon Architecture

In Sage Mode, the ninja draws power from nature without moving — the daemon keeps the index mmap'd in process memory, eliminating OS page cache warmup on every query.

Without Sage Mode

• Cold start: open files, read mmap headers
• OS page faults on first access
• ~5-15ms for cold index
• ~0.9ms when OS cache is warm

With Sage Mode (daemon)

• Index already in process memory
• Unix socket: no TCP overhead
• Sub-0.5ms consistent latency
• Perfect for AI agent repeated queries

# Start Sage Mode
ig daemon .  # runs in background, socket at .ig/daemon.sock

# Query via socket (0.3ms)
ig query "async fn" .