zombie-rs 0.0.4

# zombie-rs

[![Rust](https://img.shields.io/badge/rust-nightly-orange.svg)](https://www.rust-lang.org/)
[![License](https://img.shields.io/badge/license-MIT-blue.svg)](LICENSE)

A Rust implementation of the **Zombie** monad for memory-efficient lazy evaluation with automatic eviction and recomputation.

> **Core Idea**: Trade computation time for memory — evict values when memory is tight, recompute on demand.

## Performance: 97% Memory Reduction

**Scenario**: 200-stage dependency chain, each stage = 80 MiB, total = 15 GiB

| Metric | Standard Rust | Zombie-rs (200 MiB Limit) |
|--------|--------------|---------------------------|
| **Peak Memory** | **14.1 GiB** | **402 MiB** |
| **Build Time** | 2.1s | 0.5s |
| **Access Time** | 0.8s | 7.2s |
| **Total Time** | 8.0s | 12.7s |

> **Trade-off**: +60% time for **97% memory reduction**. Zombie computes eagerly, evicts when memory limit exceeded, replays from checkpoints on access.

### How the Benchmark Works

Both benchmarks create a **dependency chain** where each stage depends on the previous:

```
stage[0] = initial data (80 MiB)
stage[i] = f(stage[i-1])  ← each stage transforms the previous
```

**Standard Rust** (`bench_standard.rs`):
- Must keep ALL 200 stages in memory to support random access
- Any stage access is O(1) but memory = O(n × stage_size)

**Zombie-rs** (`bench_limited.rs`):
- Sets `memory_limit = 200 MiB` (only ~2-3 stages fit)
- During build: computes eagerly, automatically evicts old stages
- During access: if stage was evicted, replays from nearest checkpoint
- Memory bounded regardless of chain length

```bash
# Run yourself (use /usr/bin/time -l to measure peak memory)
/usr/bin/time -l cargo run --release --example bench_standard
/usr/bin/time -l cargo run --release --example bench_limited
```

## Quick Start

```rust
use zombie_rs::prelude::*;

fn main() {
    Runtime::init();

    let x = Zombie::new(42);
    let y = x.map(|v| v * 2);
    let z = y.bind(|v| Zombie::new(v + 1));

    println!("{}", z.get()); // 85
}
```

> **Note**: `Runtime::init()` initializes thread-local state. This is a Rust-specific design for thread safety.

## Installation

```toml
[dependencies]
zombie-rs = "0.0.4"
```

**Feature Flags:**
- `derive` (default) — `#[derive(ZombieOps)]` macro
- `profiler` (default) — Memory tracking utilities
- `cli` — Benchmark CLI (not included by default)

## Core API

```rust
// Create
let z = Zombie::new(value);

// Access (recomputes if evicted)
let val = z.get();
z.with(|v| use_ref(v));

// Transform
let z2 = z.map(|v| transform(v));
let z3 = z.bind(|v| Zombie::new(compute(v)));
```

## Key Concepts

### Evictable vs Non-Evictable

```rust
// NOT evictable - RootContext
let root = Zombie::new(data);

// Evictable - created via combinators
let evictable = root.map(|v| process(v));
```

### Memory Limit

```rust
let config = ZombieConfig::default()
    .with_memory_limit(100 * 1024 * 1024); // 100MB
Runtime::init_with_config(config);
```

## When to Use

Based on the [Zombie paper](https://github.com/MarisaKirisame/zombie_paper):

| Good| Poor |
|-------------------|-------------------|
| **Large intermediate values** — Images, matrices, large data | **Tiny values** — Overhead exceeds benefit (< 1KB) |
| **Huge input** — Large images, GB-sized logs, huge projects | **Need all values simultaneously** |
| **Low memory environments** — WASM (2GB limit), embedded, GPU | **High-frequency random access** |
| **Intermediate state** — Time-travel debug, Jupyter, autodiff | **Side effects** — Must be pure/deterministic |
| **Linear dependencies** — Pipelines, streaming transforms | **Extremely expensive recomputation** |

## Benchmarking

```bash
# Note: `./benches.sh <ARGS>` is just a wrapper script for `cargo run --release --features cli -- <ARGS>`

# Quick benchmark
./benches.sh --runs 100

# Full benchmark with baseline comparison (500+ runs recommended)
./benches.sh --runs 500 --full

# Save results as baseline
./benches.sh --runs 500 --full --save
```

**Metrics**: CV (noise), Time (median), Peak (memory), Meta (overhead)

> Data from zombie-rs v0.0.1; future versions may differ.

## Additional Utilities (zombie_utils)

```toml
[dependencies]
zombie_utils = "0.0.3"
```

```rust
use zombie_rs::prelude::*;
use zombie_utils::prelude::*;

fn main() {
    Runtime::init();

    let a = Zombie::new(10);
    let b = Zombie::new(20);
    let c = Zombie::new(30);

    // zbind! macro - ergonomic multi-argument bind (like C++ bindZombie)
    let sum2 = zbind!(|x, y| x + y, a.clone(), b.clone());
    let sum3 = zbind!(|x, y, z| x + y + z, a.clone(), b.clone(), c.clone());

    // Or use bind2, bind3, ... bind23 directly
    let product = bind2(a.clone(), b.clone(), |x, y| x * y);

    // Combinators
    let zombies = vec![a.clone(), b.clone()];
    let collected = sequence(&zombies);           // Vec<Zombie<T>> -> Zombie<Vec<T>>
    let paired = zip(&a, &b);                     // -> Zombie<(T, U)>
    let summed = zip_with(&a, &b, |x, y| x + y);  // -> Zombie<R>

    println!("sum2={}, sum3={}, product={}", sum2.get(), sum3.get(), product.get());
}
```

## Crate Architecture

The project is organized as a Cargo workspace with the following crates:

| Crate | Description |
|-------|-------------|
| **zombie-rs** | Core library - `Zombie<T>`, `Runtime`, `Timeline`, `bind_zombie`, memory management |
| **zombie_derive** | Proc macro `#[derive(ZombieOps)]` for auto-implementing size calculation on custom types |
| **zombie_profiler** | Zero-overhead profiling utilities: `TrackingAllocator`, `BenchmarkSuite`, formatted reports |
| **zombie_utils** | Ergonomic helpers: `zbind!` macro, `bind2`-`bind23`, combinators (`sequence`, `zip`, `traverse`) |

### zombie_derive

The `ZombieOps` trait determines memory size for eviction decisions. Use `#[derive(ZombieOps)]` for automatic implementation:

```rust
use zombie_rs::meter::ZombieOps;

#[derive(Clone, ZombieOps)]
struct MyData {
    buffer: Vec<u8>,   // heap_size = capacity
    name: String,      // heap_size = capacity
    count: usize,      // heap_size = 0 (primitive)
}
```

**How it works:**
- `stack_size()` — Always `size_of::<Self>()` (compile-time constant)
- `heap_size()` — Sum of all fields' `heap_size()` (generated by derive)
- `get_size()` — `stack_size() + heap_size()` (used by eviction algorithm)

**For external types** (orphan rule workaround):

```rust
struct Wrapper(external_crate::SomeType);

impl ZombieOps for Wrapper {
    fn heap_size(&self) -> usize {
        0  // Or estimate if type has heap allocations
    }
}
```

### zombie_profiler

```rust
use zombie_profiler::{TrackingAllocator, BenchmarkSuite};

#[global_allocator]
static GLOBAL: TrackingAllocator = TrackingAllocator;

let mut suite = BenchmarkSuite::new("My Benchmark");
suite.bench("Version A", || computation_a());
suite.bench("Version B", || computation_b());
suite.report(); // Pretty-prints comparison table
```

## Documentation

- [examples/](examples/) — Usage examples (basic → advanced)
- [tests/](tests/) — Test cases and edge cases
- [paper/](paper/) — Academic paper (Typst format)
- [ARCHITECTURE_REVIEW.md](ARCHITECTURE_REVIEW.md) — Internal architecture and algorithm details

## Naming & Renaming

To provide a more modern and intuitive API, we have renamed core internal components from their original Sanskrit names (used in the C++ implementation) to English descriptors:

| New Name | Original Name | Meaning |
|----------|---------------|---------|
| **Runtime** | Trailokya | The global state manager |
| **Timeline** | Akasha | The context/tock tree |
| **Zombie** | Zombie | Values that "die" (evict) and "resurrect" (recompute) |

## References

- [Zombie Paper](https://github.com/MarisaKirisame/zombie_paper) — Original LaTeX
- [C++ Implementation](https://github.com/MarisaKirisame/zombie)

## License

MIT