Crate rssn_advanced

Expand description

§rssn-advanced

rssn-advanced is the symbolic computation engine of the rssn project. It provides a hash-consed expression DAG, a Cranelift-backed JIT compiler, heuristic and e-graph simplification, multi-architecture inline-asm presets, and a flat extern "C" API for embedding in C/C++ and other languages.

§Architecture

Module	Role
`dag`	Hash-consed expression DAG — the canonical, deduplicated store for all symbolic nodes
`ast`	Lightweight local tree projection of a DAG subgraph via relative `i32` pointers
`parser`	`nom`-based infix parser: `"x^2 + 2*x + 1"` → DAG root
`jit` (feature: `cranelift-jit`)	Cranelift JIT; emits scalar `f64` closures and 2-row ILP batch functions
`heuristic`	Configurable greedy/beam simplifier with a pluggable `heuristic::rule_registry::RuleRegistry`
`egraph`	Lightweight equality saturation over the DAG (no `egg` dependency)
`custom`	Unified custom-operator system — one `custom::descriptor::CustomOpDescriptor` wires into JIT + simplifier + e-graph
`simd`	Slice-level batch arithmetic using the inline-asm presets
`asm_presets`	Hand-written `f64×2` / `f64×4` kernels for `x86_64` (SSE2/AVX2/AES-NI), `AArch64` (NEON/crypto), riscv64 (RVV/Zkn)
`ffi`	Flat `extern "C"` surface generated by `cbindgen`; includes a fiber-backed async bridge
`parallel`	Fiber-based parallel simplification via the `dtact` runtime
`storage`	Disk-backed DAG spillover and a frequency-based hot-node cache
`error`	Cold-path error types and the `rssn_error!` macro

§Quick start

§Parse and evaluate

use rssn_advanced::dag::builder::DagBuilder;
use rssn_advanced::parser::expr::parse_expression;

let mut builder = DagBuilder::new();
// parse_expression(input, &mut builder) -> Result<DagNodeId, ParseError>
let root = parse_expression("x^2 + 2*x + 1", &mut builder).unwrap();
let _ = root;

§JIT-compile and bulk-evaluate

use rssn_advanced::dag::builder::DagBuilder;
use rssn_advanced::parser::expr::parse_expression;
use rssn_advanced::ast::convert::dag_to_ast;
use rssn_advanced::jit::compiler::JitCompiler;

let mut builder = DagBuilder::new();
let root = parse_expression("x^2 + 2*x + 1", &mut builder).unwrap();

let mut compiler = JitCompiler::try_new().unwrap();
let ast = dag_to_ast(builder.arena(), root);
let f   = compiler.compile(&ast).unwrap();

// CompiledExprFn = extern "C" fn(*const f64) -> f64
assert_eq!(f([3.0_f64].as_ptr()), 16.0); // (3+1)^2

// 2-row ILP batch path; returns None if expression is not vectorizable
let _batch = compiler.compile_batch_f64x2(&ast).unwrap();

§Register a custom operator

use std::sync::Arc;
use rssn_advanced::dag::builder::DagBuilder;
use rssn_advanced::custom::descriptor::{CustomOpDescriptor, CustomOpRegistry, EvalFn};
use rssn_advanced::egraph::egraph::{EGraph, EGraphConfig};
use rssn_advanced::jit::compiler::JitCompiler;

extern "C" fn my_relu(x: f64) -> f64 { x.max(0.0) }

let mut builder = DagBuilder::new();
// intern_function returns the FnId used to identify this operator
let fn_id = builder.intern_function("relu");

let desc = CustomOpDescriptor::builder(fn_id, "relu", EvalFn::Arity1(my_relu))
    .vectorizable()   // safe to duplicate in the 2-row ILP batch path
    .cost(1.0)
    .build();

let mut reg = CustomOpRegistry::new();
reg.register(desc).unwrap();
let reg = Arc::new(reg);

// Wire into the JIT (registers the eval_fn pointer)
let mut compiler = JitCompiler::try_new().unwrap();
reg.apply_to_jit(&mut compiler);

// Wire into the heuristic simplifier
let _rule_reg = reg.build_rule_registry();

// Wire into the e-graph saturation engine
{
    let mut egraph = EGraph::new(&mut builder, EGraphConfig::default());
    reg.apply_to_egraph(&mut egraph);
}

§Performance

Benchmark: bulk evaluation of N = 1,000,000 rows, best of 5 runs. Hardware: Dell Latitude 5400, Intel i7-8665U @ 1.90 GHz (laptop-class, 16 MB L3), Fedora Linux 44, kernel 6.19. Compared against hand-optimised NumPy 1.x (BLAS-linked, SIMD-enabled).

Expression	JIT bulk	JIT batch	`NumPy`	Speedup (bulk / batch)
`x + y + 10.0` (trivial baseline)	1.87 ns	1.13 ns	2.82 ns	1.5× / 2.5×
`(x-y)^4` — degree-4 polynomial	2.73 ns	1.28 ns	19.21 ns	7× / 15×
cubic surface (10 terms, 3 vars)	3.73 ns	1.77 ns	75.75 ns	20× / 43×
rational expression w/ CSE	2.53 ns	1.27 ns	15.91 ns	6× / 13×

Why the gap grows with complexity: NumPy allocates one f64[N] scratch array per arithmetic operation. A 10-term expression at N = 10⁶ creates ~200 MB of temporaries that thrash L3 cache. The JIT keeps every intermediate value in a CPU register across the full expression, paying exactly one memory round-trip per input column.

Honest caveats:

Numbers are from a single laptop; server CPUs with larger L3 caches will show a smaller gap for simple expressions.
The batch path unrolls 2 rows for ILP but does not emit wide-vector AVX/AVX-512 instructions; the asm_presets / simd paths are faster for fixed-width kernels.
Cranelift’s code quality is good but not hand-tuned; gcc -O3 / LLVM can sometimes produce tighter loops for simple expressions.

§Feature flags

Flag	Default	Effect
`cranelift-jit`	on	Enables the `jit` module, JIT compilation, and the batch-evaluate path

Disable with --no-default-features for embedded or size-constrained targets. The parser, DAG, heuristic simplifier, e-graph, and SIMD presets are all available without the JIT feature.

§Known limitations

Parser scope: handles +, -, *, /, ^, %, unary negation, and registered named functions. Transcendentals (sin, exp, …) must be registered as custom operators.
Single-threaded JIT context: compilation requests from multiple threads serialise on a global Mutex.
No GPU or BLAS integration.
asm_presets on Windows: some NEON / RVV paths are x86/AArch64/riscv64 specific; the scalar fallback is always available.
e-graph extractor is greedy: the current cost-minimising extractor uses a greedy bottom-up pass; optimal extraction is NP-hard and not yet implemented.

Modules§

asm_presets: Inline-assembly preset suite (AVX2 / AES-NI / scalar fallback).
ast: Local AST (Abstract Syntax Tree) projection for computation.
custom: Unified custom-operator extension system.
dag: Global DAG (Directed Acyclic Graph) storage for symbolic expressions.
egraph: Lightweight E-graph for equality saturation.
error: Cold-path error infrastructure.
ffi: C/C++ Foreign Function Interface.
heuristic: Heuristic search toolbox for NP-hard pattern matching.
jit: JIT compilation pipeline for symbolic derivation rules.
parallel: Parallel computation engine.
parser: Symbolic expression parser.
runtime: Fiber-based task runtime built on dtact.
simd: SIMD-optimized preset function library.
storage: Streaming storage and dynamic caching.
util: Allocator-light shared utilities (worklist traversals, helpers). Generic, allocator-light utilities shared across modules.
zerocopy: Zero-copy borrowed containers and bincode-next BorrowDecode glue.