forgo.cloud
Sign in
Repo workspace

forkjoin-ai/gnosis

WASM SIMD FFT Migration Plan

distributed-inference-host/docs/wasm-simd-fft-plan.md
forkjoin-ai/gnosis
Repo overview Open in workbench

WASM SIMD FFT Migration Plan

Plan-of-record for replacing the pure-JS FFT in fft2.ts with a SIMD-accelerated WASM kernel. This document is scope, not implementation. Pick it up later as a discrete work item.

Context

Current state: fft2.ts is pure-TS Cooley-Tukey radix-2. StructuralErrorgle 512x512 forward FFT in Node measures ~80ms; round-trip pair (fft+ifft) ~160ms. Wiener for one RGB channel does 2 forward + 1 inverse = ~240ms. RGB image: ~720ms. Way over 60fps budget (16ms/frame).

Goal: SIMD-accelerated 2D FFT to bring per-channel cost under ~5ms, enabling 60fps single-thread or 240fps with worker fan-out. Numbers above are measured on the existing JS path; the ~5ms target is aspirational and validated by the bench harness in Phase C.

Existing inventory

  • open-source/aether/src/wasm-simd/standalone.ts and simd-kernels-standalone.c: ~10KB, no Emscripten, runs in CF Workers + Node + Bun. Has matmul, dot product, tanh; does NOT have FFT.
  • Build script at open-source/aether/src/wasm-simd/build-standalone.sh: requires Homebrew LLVM + lld (brew install llvm lld).
  • ISIMDRuntime interface (apps/edge-workers/src/lib/wasm-inference/simd-runtime.ts): unified shim, fallback chain standalone WASM -> legacy Emscripten -> pure JS.
  • The Rust crate at open-source/gnosis/distributed-inference/src/ has math primitives (math.rs, math_batched.rs, matvec_memo.rs) and wasm-bindgen at wasm_bindings.rs, but no FFT — verified 2026-04-27. Adding an FFT kernel to that crate is one valid host; the other is aether/src/wasm-simd/simd-kernels-standalone.c alongside its matmul kernel. The standalone WASM path is preferred because it already has the JS bridge pattern (ISIMDRuntime fallback chain) and is consumed by edge-workers + browser, while the gnosis Rust crate is currently only loaded server-side.
  • Sibling wasm modules in this monorepo: gnosis-chaos-wasm (chaos analysis, Cargo crate), gnosis-betti-wasm (Betti number computation, Cargo crate). Neither has FFT — they are precedent for "small focused wasm crates" if we decide a separate gnosis-fft-wasm crate is the right home.
  • open-source/gnosis/gnosis-frf is the parallelism substrate for the Rust path. Drop-in subset replacement for rayon, ~16-20x faster than rayon at small uniform-N dispatch (200ns vs rayon's 5us), self-regulating spin via the same sqrt(5) ≈ 2.236 Hurwitz attractor we use in attractor.ts for σ-selection. Has a WASM fallback that compiles to sequential Iterator loops (no SharedArrayBuffer required). Phase A's fft1d_complex should use par_iter_mut().with_sub_chunks_auto() for the row-pass and column-pass loops; the sequential WASM fallback path is what ships in the browser/CF Workers build, but a native Rust binding (e.g. via napi-rs or neon) would benefit from the parallel path on Node.
  • Orthogonal but worth naming so they don't get confused with this work: polyglot/ ships gnexec (Rust-native TS runtime, 4.3x faster than node — addresses spawn overhead, not hot-loop math) and x-gnosis is the nginx-compatible web server (request scheduling, not numerical kernels). Neither path accelerates FFT butterflies.

Gaps stated explicitly:

  • No 2D FFT in aether's wasm-simd C kernel.
  • No JS shim that routes fft2 calls to WASM.
  • No bench harness comparing JS vs WASM FFT.

Migration shape (three phases)

Phase A: 1D radix-2 FFT in C

  • Add a fft1d_complex(re_inout, im_inout, n, sign) function to simd-kernels-standalone.c. Same Cooley-Tukey skeleton as fft2.ts:36 but using wasm_v128 SIMD primitives for the butterfly.
  • Critical optimization: process 4 complex butterflies per SIMD instruction (8 floats per v128).
  • Pre-compute twiddle factors as a static lookup table for n up to 512.
  • Estimated effort: ~300 LOC of C, ~1 day.

Phase B: 2D FFT and JS bridge

  • Add fft2d_real(input, w, h, re_out, im_out) and ifft2d(re, im, w, h, out) C functions. They allocate work buffers on the bump allocator (already in standalone.c via allocate / resetHeap / getHeapPtr), call fft1d_complex per row then per column.
  • Add a TS shim wasm-fft.ts that loads the WASM module and exposes the same surface as fft2.ts (fft2, ifft2, fft2Complex, ifft2Complex).
  • fft2.ts reorganized: keep pure-JS impl as fft2-js.ts for fallback; the public fft2.ts becomes a router that prefers WASM and falls back to JS.
  • Estimated effort: ~150 LOC of C + ~80 LOC of TS, ~1 day including round-trip parity tests.

Phase C: validation + perf bench

  • Bench harness: __tests__/fft2-bench.ts - compare WASM vs JS on 64x64, 128x128, 256x256, 512x512, 1024x1024, log Hz/ms.
  • Parity test: ifft2(fft2(x)) round-trip RMSE < 1e-5 on the existing test fixtures, BOTH paths must pass.
  • Acceptance criterion: 512x512 forward+inverse pair under 10ms in Node on Apple Silicon (vs ~160ms JS).

Risks and unknowns

  • WASM SIMD float precision: f32 path has cumulative rounding error after large n. Must match JS f32 path to within 1e-5; if it doesn't, the round-trip test will catch it.
  • Twiddle table size: precomputed for n=2..1024 is ~16KB. Acceptable in wasm bytes budget.
  • Build dependency: requires Homebrew LLVM 17+. CI must install this. Document in package.json prepare if necessary.
  • Fallback path must stay green: if WASM init fails (older Node, sandboxed env), all callers must transparently get the JS path. The existing ISIMDRuntime fallback chain in aether is the precedent.
  • Browser target: wasm-bindgen + standalone.ts already work in CF Workers, browser, Node. No new compatibility surface expected - but the bigger twiddle table + larger compiled wasm needs a size budget review.

What this does NOT do

  • Does not change Wiener or Richardson-Lucy math; only the FFT primitive.
  • Does not push the Rust crate into the host shim. The WASM kernel here is in aether/wasm-simd, separate from the gnosis Rust crate.
  • Does not implement worker_threads parallelism - that's a separate axis (already implemented in video-deblur.ts).

Done when

  • fft2.test.ts round-trip < 1e-5 on the WASM path.
  • 512x512 fft+ifft pair < 10ms in Node on Apple Silicon.
  • Pure-JS fallback automatically engaged when WASM module fails to load, without exception propagating to callers.
  • One bench/ artifact (text or JSON) showing the JS vs WASM crossover by image size.