# Chapter: Performance Parity with Ollama & llama.cpp

## Introduction

This chapter covers the implementation of performance parity between Realizar and production-grade LLM inference engines like Ollama and llama.cpp. We follow the Toyota Production System principles and EXTREME TDD methodology to achieve measurable, reproducible performance improvements.

## Prerequisites

Before reading this chapter, you should be familiar with:
- Rust basics and the Realizar crate structure
- Quantization formats (Q4_0, Q8_0, Q4_K)
- Transformer architecture fundamentals
- Basic benchmarking concepts

## Learning Objectives

By the end of this chapter, you will understand:
1. How to implement SIMD-accelerated dequantization
2. Memory-mapped weight streaming for large models
3. Fused attention kernels for improved throughput
4. KV cache optimization strategies
5. Batch processing and prefill optimization

## 1. The Performance Challenge

### Current State vs Target

| Runtime | Backend | p50 Latency | Throughput | Status |
|---------|---------|-------------|------------|--------|
| llama.cpp | CUDA | 162ms | 256 tok/s | Production |
| Ollama | CUDA | ~120ms | ~260 tok/s | Production |
| Realizar | CPU | ~500ms | ~2 tok/s | Educational |
| Realizar | WGPU | TBD | TBD | In Development |

### Milestones

| Milestone | Target | Metric |
|-----------|--------|--------|
| M1: CPU Parity | 10x improvement | 20 tok/s CPU |
| M2: WGPU Basic | GPU inference working | Any tok/s |
| M3: WGPU Parity | 50% of llama.cpp | 128 tok/s |
| M4: Full Parity | 90% of llama.cpp | 230+ tok/s |

## 2. Toyota Production System Framework

We apply TPS principles throughout our optimization work:

### Genchi Genbutsu (Go and See)
Measure actual performance, not theoretical. Always benchmark before and after changes.

### Jidoka (Stop on Defects)
If a change regresses performance, stop immediately and investigate.

### Kaizen (Continuous Improvement)
Small, incremental improvements compound over time.

### Poka-yoke (Error-proofing)
Build benchmark infrastructure that catches regressions automatically.

## 3. SIMD-Accelerated Dequantization (IMP-001)

### The Problem

Q4_K quantization stores 256 values in a 144-byte super-block. Dequantization involves:
1. Reading scale factors (d, dmin)
2. Unpacking 4-bit values
3. Applying scales and minimums
4. Converting to f32

### Scalar Implementation

```rust
pub fn dequantize_q4_k(data: &[u8]) -> Result<Vec<f32>> {
    const SUPER_BLOCK_BYTES: usize = 144;

    // Process each super-block sequentially
    let num_super_blocks = data.len() / SUPER_BLOCK_BYTES;
    let mut result = Vec::with_capacity(num_super_blocks * 256);

    for sb_idx in 0..num_super_blocks {
        let sb_data = &data[sb_idx * SUPER_BLOCK_BYTES..];
        // Read d (f16), dmin (f16), scales, quantized values
        // Dequantize: value = d * q + dmin
        // ...
    }

    Ok(result)
}
```

### SIMD Implementation

```rust
pub fn dequantize_q4_k_simd(data: &[u8]) -> Result<Vec<f32>> {
    #[cfg(target_arch = "x86_64")]
    {
        if is_x86_feature_detected!("avx2") {
            return unsafe { dequantize_q4_k_avx2_parallel(data) };
        }
    }
    // Fallback to parallel scalar
    dequantize_q4_k_parallel(data)
}
```

### Performance Results

| Implementation | Throughput | Speedup |
|----------------|------------|---------|
| Scalar | ~2.5 GB/s | 1.0x |
| SIMD (AVX2) | ~10+ GB/s | 4x+ |
| SIMD + Rayon | ~40+ GB/s | 16x+ |

### Test

```rust
#[test]
fn test_imp_001_q4k_simd_dequantize() {
    use crate::quantize::{dequantize_q4_k, dequantize_q4_k_simd};

    let data = vec![0u8; 144 * 4]; // 4 super-blocks

    // Verify correctness
    let scalar = dequantize_q4_k(&data).unwrap();
    let simd = dequantize_q4_k_simd(&data).unwrap();

    assert_eq!(scalar.len(), simd.len());
    for (s, p) in scalar.iter().zip(simd.iter()) {
        assert!((s - p).abs() < 1e-4);
    }
}
```

## 4. Memory-Mapped Weight Streaming (IMP-002)

### The Problem

A 7B parameter model requires ~4GB of weights (with Q4 quantization). Loading all weights into RAM wastes memory and causes slow startup.

### Solution: memmap2

```rust
use memmap2::Mmap;

pub fn load_weights_mmap(path: &Path) -> Result<Mmap> {
    let file = File::open(path)?;
    let mmap = unsafe { Mmap::map(&file)? };
    Ok(mmap)
}
```

### Benefits

1. **Lazy Loading**: Only pages accessed are loaded
2. **Shared Memory**: Multiple processes can share the same mapping
3. **OS Cache**: The OS manages caching automatically
4. **Fast Startup**: Model "loads" in milliseconds

### Test

```rust
#[test]
fn test_imp_002_mmap_weight_streaming() {
    let temp_file = std::env::temp_dir().join("test_mmap.bin");
    let weight_data: Vec<f32> = (0..1024).map(|i| i as f32).collect();
    let bytes: Vec<u8> = weight_data.iter().flat_map(|f| f.to_le_bytes()).collect();

    std::fs::write(&temp_file, &bytes).unwrap();

    let file = File::open(&temp_file).unwrap();
    let mmap = unsafe { Mmap::map(&file).unwrap() };

    // Access memory without loading everything
    assert_eq!(mmap.len(), bytes.len());
}
```

## 5. Fused Attention Kernel (IMP-003)

### The Problem

Standard attention requires:
1. Compute Q*K^T (O(n^2) memory)
2. Apply softmax
3. Multiply by V

This creates large intermediate tensors.

### Solution: Fused QKV Attention

```rust
pub struct FusedQKVAttention {
    head_dim: usize,
    qkv_proj: Linear,  // Single projection for Q, K, V
    out_proj: Linear,
}

impl FusedQKVAttention {
    pub fn forward(&self, x: &Tensor) -> Result<Tensor> {
        // Single fused operation
        let qkv = self.qkv_proj.forward(x)?;

        // Split and compute attention in blocks
        let (q, k, v) = split_qkv(&qkv, self.head_dim);
        let attn = scaled_dot_product_attention(&q, &k, &v)?;

        self.out_proj.forward(&attn)
    }
}
```

### Performance Impact

| Approach | Memory | Latency |
|----------|--------|---------|
| Separate Q,K,V | O(3n) | 1.0x |
| Fused QKV | O(n) | ~2x faster |

## 6. KV Cache Optimization (IMP-004)

### The Problem

During autoregressive generation, we recompute K and V for all previous tokens, wasting compute.

### Solution: KV Cache

```rust
pub struct KVCache {
    k_cache: Vec<f32>,  // [layers, max_seq, hidden_dim]
    v_cache: Vec<f32>,
    seq_len: usize,
}

impl KVCache {
    pub fn store(&mut self, layer: usize, k: &[f32], v: &[f32]) {
        // Append new K, V to cache
        let offset = layer * self.max_seq_len * self.hidden_dim
                   + self.seq_len * self.hidden_dim;
        self.k_cache[offset..offset + k.len()].copy_from_slice(k);
        self.v_cache[offset..offset + v.len()].copy_from_slice(v);
        self.seq_len += 1;
    }

    pub fn get_k(&self, layer: usize) -> &[f32] {
        // Return all cached K values for this layer
        let start = layer * self.max_seq_len * self.hidden_dim;
        let end = start + self.seq_len * self.hidden_dim;
        &self.k_cache[start..end]
    }
}
```

### Performance Impact

Without KV cache: O(n^2) compute per token
With KV cache: O(n) compute per token (3x+ speedup for long contexts)

## 7. Batch Prefill (IMP-005)

### The Problem

Processing prompt tokens one at a time is inefficient.

### Solution: Batch Processing

```rust
pub fn prefill(&self, tokens: &[usize]) -> Result<Tensor> {
    // Process all prompt tokens in parallel
    let embeddings = self.embed_tokens(tokens)?;  // [seq_len, hidden_dim]

    // Single forward pass through transformer
    let hidden = self.transformer.forward(&embeddings)?;

    // Return logits for last position only (for generation)
    Ok(hidden.slice_last())
}
```

### Performance Impact

| Approach | Throughput |
|----------|------------|
| Sequential | ~100 tok/s |
| Batch prefill | ~1000+ tok/s |

## 8. Running the Benchmarks

### Example Command

```bash
cargo run --example performance_parity --release
```

### Sample Output

```
╔══════════════════════════════════════════════════════════════════╗
║        Performance Parity Benchmark Suite (PERF-PARITY-001)      ║
╚══════════════════════════════════════════════════════════════════╝

┌─────────────────────────┬────────────┬────────────┬────────────┬────────┐
│ Benchmark               │ Metric     │ Value      │ Target     │ Status │
├─────────────────────────┼────────────┼────────────┼────────────┼────────┤
│ IMP-001: SIMD Q4_K      │ Throughput │ 12.34 GB/s │ 10.00 GB/s │ ✅ PASS │
│ IMP-002: Mmap Streaming │ Throughput │ 8.50 GB/s  │ 5.00 GB/s  │ ✅ PASS │
│ IMP-003: Fused Attention│ Latency    │ 5.20 ms    │ 10.00 ms   │ ✅ PASS │
│ IMP-004: KV Cache       │ Ops/sec    │ 150K ops/s │ 100K ops/s │ ✅ PASS │
│ IMP-005: Batch Prefill  │ Speedup    │ 6.2x       │ 5.0x       │ ✅ PASS │
└─────────────────────────┴────────────┴────────────┴────────────┴────────┘
```

## 9. Quality Assurance

### The 50-Point QA Checklist

Our implementation is validated by 50 QA tests covering:

1. **Correctness (QA-001 to QA-010)**: Output matches reference implementations
2. **Performance (QA-011 to QA-020)**: Throughput and latency targets met
3. **Reliability (QA-021 to QA-030)**: Graceful error handling
4. **Benchmarking (QA-031 to QA-040)**: Statistical validity
5. **Integration (QA-041 to QA-050)**: CI/CD integration

### Running Tests

```bash
# Run all IMP tests
cargo test --lib test_imp_

# Run all QA tests
cargo test --lib test_qa_

# Run full suite
cargo test --lib
```

## 10. Next Steps

After mastering these fundamentals, explore:

1. **GPU Acceleration (Phase 2)**: WGPU compute shaders
2. **Advanced Quantization (Phase 3)**: Q5_K, Q6_K, I-quant
3. **Attention Optimization (Phase 4)**: Flash Attention, GQA
4. **System Integration (Phase 5)**: Continuous batching, speculative decoding

## Summary

Key takeaways:
- SIMD dequantization provides 4x+ speedup
- Memory-mapped I/O enables efficient large model loading
- Fused kernels reduce memory traffic
- KV cache eliminates redundant computation
- Batch prefill maximizes throughput

The Toyota Production System principles guide our optimization work:
- **Genchi Genbutsu**: Measure everything
- **Jidoka**: Stop on quality issues
- **Kaizen**: Continuous improvement
- **Poka-yoke**: Automated regression detection

## References

1. Liker, J.K. "The Toyota Way" (2004)
2. Hoefler & Belli, "Scientific Benchmarking of Parallel Computing Systems" (SC'15)
3. Dao et al., "FlashAttention: Fast and Memory-Efficient Exact Attention" (NeurIPS 2022)
4. Kwon et al., "Efficient Memory Management with PagedAttention" (SOSP '23)
5. Dettmers et al., "LLM.int8(): 8-bit Matrix Multiplication" (NeurIPS 2022)
