zombie-rs

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

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

# 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

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

[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

// 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

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

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

Memory Limit

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

When to Use

Based on the Zombie paper:

Benchmarking

# 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)

[dependencies]
zombie_utils = "0.0.3"

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:

zombie_derive

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

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):

struct Wrapper(external_crate::SomeType);

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

zombie_profiler

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/ — Usage examples (basic → advanced)
• tests/ — Test cases and edge cases
• paper/ — Academic paper (Typst format)
• 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:

References

• Zombie Paper — Original LaTeX
• C++ Implementation

License

MIT