665bfac0b339
nn.rs
//! The few neural-network kernels MobileSAM needs, on token-major feature maps (`[pixels, channels]`
//! row-major, i.e. NHWC with a batch of one): dense layers on a parallel GEMM (ndarray's safe
//! `general_mat_mul`, which picks AVX/FMA kernels at run time), convolutions as patch matrices
//! times weights, depthwise and transposed convolutions, layer norm, exact GELU and softmax.
//! Weights are re-laid out once at load so every inner loop runs over contiguous channels.
use ndarray::linalg::general_mat_mul;
use ndarray::{ArrayView2, ArrayViewMut2};
use rayon::prelude::*;
/// Rows of the left matrix per parallel task.
const ROW_BLOCK: usize = 64;
/// `out[m×n] += a[m×k] · b[k×n]` (row-major), rows split across threads.
pub fn gemm(a: &[f32], m: usize, k: usize, b: &[f32], n: usize, out: &mut [f32]) {
if m == 0 || n == 0 || a.len() < m * k || b.len() < k * n || out.len() < m * n {
return;
}
let Ok(bv) = ArrayView2::from_shape((k, n), &b[..k * n]) else { return };
let block = |r0: usize, oc: &mut [f32]| {
let rows = oc.len() / n;
if let (Ok(av), Ok(mut cv)) = (ArrayView2::from_shape((rows, k), &a[r0 * k..(r0 + rows) * k]), ArrayViewMut2::from_shape((rows, n), oc)) {
general_mat_mul(1.0, &av, &bv, 1.0, &mut cv);
}
};
if m <= ROW_BLOCK {
block(0, &mut out[..m * n]);
} else {
out[..m * n].par_chunks_mut(ROW_BLOCK * n).enumerate().for_each(|(i, oc)| block(i * ROW_BLOCK, oc));
}
}
/// A dense layer (also a 1×1 convolution): `y = x·Wᵀ + b`, with `W` stored transposed.
#[derive(Clone, Debug, Default)]
pub struct Linear {
/// `[inp × out]`.
pub wt: Vec<f32>,
pub b: Vec<f32>,
pub inp: usize,
pub out: usize,
}
impl Linear {
/// From PyTorch's `[out × inp]` weight (a 1×1 conv's `[out × inp × 1 × 1]` too).
pub fn new(w: &[f32], b: Option<&[f32]>, out: usize, inp: usize) -> Option<Linear> {
if w.len() != out * inp || b.is_some_and(|b| b.len() != out) {
return None;
}
let mut wt = vec![0.0; inp * out];
for o in 0..out {
for i in 0..inp {
wt[i * out + o] = w[o * inp + i];
}
}
Some(Linear { wt, b: b.map_or_else(|| vec![0.0; out], <[f32]>::to_vec), inp, out })
}
/// `rows` tokens of `inp` channels → `rows × out`.
pub fn forward(&self, x: &[f32], rows: usize) -> Vec<f32> {
let mut y: Vec<f32> = (0..rows).flat_map(|_| self.b.iter().copied()).collect();
gemm(x, rows, self.inp, &self.wt, self.out, &mut y);
y
}
}
/// A `ks×ks` convolution (any stride and padding, one group) on `h×w×inp` → `oh×ow×out`, as a
/// patch matrix times the weights, built a block of output rows at a time.
#[derive(Clone, Debug, Default)]
pub struct Conv {
/// `[(ky·ks + kx)·inp + ci] × out`.
pub wt: Vec<f32>,
pub b: Vec<f32>,
pub inp: usize,
pub out: usize,
pub ks: usize,
pub stride: usize,
pub pad: usize,
}
impl Conv {
/// From PyTorch's `[out × inp × ks × ks]`.
pub fn new(w: &[f32], b: Option<&[f32]>, out: usize, inp: usize, ks: usize, stride: usize, pad: usize) -> Option<Conv> {
if w.len() != out * inp * ks * ks || b.is_some_and(|b| b.len() != out) || stride == 0 {
return None;
}
let kk = ks * ks * inp;
let mut wt = vec![0.0; kk * out];
for o in 0..out {
for ci in 0..inp {
for t in 0..ks * ks {
wt[(t * inp + ci) * out + o] = w[(o * inp + ci) * ks * ks + t];
}
}
}
Some(Conv { wt, b: b.map_or_else(|| vec![0.0; out], <[f32]>::to_vec), inp, out, ks, stride, pad })
}
pub fn out_size(&self, n: usize) -> usize {
(n + 2 * self.pad).saturating_sub(self.ks) / self.stride + 1
}
pub fn forward(&self, x: &[f32], h: usize, w: usize) -> (Vec<f32>, usize, usize) {
let (oh, ow) = (self.out_size(h), self.out_size(w));
(self.forward_sized(x, h, w, oh, ow, [self.pad; 2]), oh, ow)
}
/// An `oh×ow` output with `pad` (top, left) zero rows and columns before the input; what
/// falls past the input's far edges is zero too (so asymmetric "same" padding works).
pub fn forward_sized(&self, x: &[f32], h: usize, w: usize, oh: usize, ow: usize, pad: [usize; 2]) -> Vec<f32> {
let kk = self.ks * self.ks * self.inp;
let mut y: Vec<f32> = (0..oh * ow).flat_map(|_| self.b.iter().copied()).collect();
if x.len() < h * w * self.inp || self.wt.len() < kk * self.out {
return y;
}
y.par_chunks_mut(ow * self.out).enumerate().for_each(|(oy, row)| {
// This output row's patches.
let mut patch = vec![0.0f32; ow * kk];
for ox in 0..ow {
for ky in 0..self.ks {
let iy = (oy * self.stride + ky) as isize - pad[0] as isize;
if iy < 0 || iy >= h as isize {
continue;
}
for kx in 0..self.ks {
let ix = (ox * self.stride + kx) as isize - pad[1] as isize;
if ix < 0 || ix >= w as isize {
continue;
}
let src = (iy as usize * w + ix as usize) * self.inp;
let dst = ox * kk + (ky * self.ks + kx) * self.inp;
patch[dst..dst + self.inp].copy_from_slice(&x[src..src + self.inp]);
}
}
}
if let (Ok(av), Ok(bv), Ok(mut cv)) = (
ArrayView2::from_shape((ow, kk), &patch[..]),
ArrayView2::from_shape((kk, self.out), &self.wt[..]),
ArrayViewMut2::from_shape((ow, self.out), row),
) {
general_mat_mul(1.0, &av, &bv, 1.0, &mut cv);
}
});
y
}
}
/// A depthwise `ks×ks` convolution (one filter per channel) on `h×w×c`.
#[derive(Clone, Debug, Default)]
pub struct Depthwise {
/// `[tap × c]`.
pub w: Vec<f32>,
pub b: Vec<f32>,
pub c: usize,
pub ks: usize,
pub stride: usize,
}
impl Depthwise {
/// From PyTorch's `[c × 1 × 3 × 3]`.
pub fn new(w: &[f32], b: Option<&[f32]>, c: usize, stride: usize) -> Option<Depthwise> {
if w.len() != c * 9 || b.is_some_and(|b| b.len() != c) || stride == 0 {
return None;
}
let mut wt = vec![0.0; 9 * c];
for ch in 0..c {
for t in 0..9 {
wt[t * c + ch] = w[ch * 9 + t];
}
}
Some(Depthwise { w: wt, b: b.map_or_else(|| vec![0.0; c], <[f32]>::to_vec), c, ks: 3, stride })
}
/// 3×3 with padding 1.
pub fn forward(&self, x: &[f32], h: usize, w: usize) -> (Vec<f32>, usize, usize) {
let (oh, ow) = ((h + 2 - 3) / self.stride + 1, (w + 2 - 3) / self.stride + 1);
(self.forward_sized(x, h, w, oh, ow, [1, 1]), oh, ow)
}
/// An `oh×ow` output with `pad` (top, left) before the input, as [`Conv::forward_sized`].
pub fn forward_sized(&self, x: &[f32], h: usize, w: usize, oh: usize, ow: usize, pad: [usize; 2]) -> Vec<f32> {
let (c, ks) = (self.c, self.ks);
let mut y = vec![0.0f32; oh * ow * c];
if x.len() < h * w * c || self.w.len() < ks * ks * c || self.b.len() < c {
return y;
}
y.par_chunks_mut(ow * c).enumerate().for_each(|(oy, row)| {
for ox in 0..ow {
let out = &mut row[ox * c..(ox + 1) * c];
out.copy_from_slice(&self.b);
for ky in 0..ks {
let iy = (oy * self.stride + ky) as isize - pad[0] as isize;
if iy < 0 || iy >= h as isize {
continue;
}
for kx in 0..ks {
let ix = (ox * self.stride + kx) as isize - pad[1] as isize;
if ix < 0 || ix >= w as isize {
continue;
}
let src = &x[(iy as usize * w + ix as usize) * c..][..c];
let tap = &self.w[(ky * ks + kx) * c..][..c];
for ((o, s), k) in out.iter_mut().zip(src).zip(tap) {
*o += s * k;
}
}
}
}
});
y
}
}
/// A 2×2, stride-2 transposed convolution (each input pixel paints a 2×2 block):
/// `h×w×inp` → `2h×2w×out`.
#[derive(Clone, Debug, Default)]
pub struct Upconv {
/// One dense layer per output tap (dy, dx).
pub taps: Vec<Linear>,
pub out: usize,
}
impl Upconv {
/// From PyTorch's ConvTranspose2d `[inp × out × 2 × 2]`.
pub fn new(w: &[f32], b: &[f32], inp: usize, out: usize) -> Option<Upconv> {
if w.len() != inp * out * 4 || b.len() != out {
return None;
}
let taps = (0..4)
.map(|t| {
let mut wt = vec![0.0; inp * out];
for i in 0..inp {
for o in 0..out {
wt[i * out + o] = w[(i * out + o) * 4 + t];
}
}
Linear { wt, b: b.to_vec(), inp, out }
})
.collect();
Some(Upconv { taps, out })
}
pub fn forward(&self, x: &[f32], h: usize, w: usize) -> Vec<f32> {
let (ow, c) = (2 * w, self.out);
let mut y = vec![0.0f32; 4 * h * w * c];
for (t, lin) in self.taps.iter().enumerate() {
let (dy, dx) = (t / 2, t % 2);
let part = lin.forward(x, h * w);
for p in 0..h * w {
let (py, px) = (p / w, p % w);
let dst = ((2 * py + dy) * ow + 2 * px + dx) * c;
if let (Some(d), Some(s)) = (y.get_mut(dst..dst + c), part.get(p * c..(p + 1) * c)) {
d.copy_from_slice(s);
}
}
}
y
}
}
/// Layer norm over the channels of each token.
#[derive(Clone, Debug, Default)]
pub struct Norm {
pub w: Vec<f32>,
pub b: Vec<f32>,
pub eps: f32,
}
impl Norm {
pub fn forward(&self, x: &mut [f32]) {
let c = self.w.len();
if c == 0 {
return;
}
x.par_chunks_mut(c).for_each(|t| {
let mean = t.iter().sum::<f32>() / c as f32;
let var = t.iter().map(|v| (v - mean) * (v - mean)).sum::<f32>() / c as f32;
let inv = 1.0 / (var + self.eps).sqrt();
for ((v, w), b) in t.iter_mut().zip(&self.w).zip(&self.b) {
*v = (*v - mean) * inv * w + b;
}
});
}
}
/// The error function (Abramowitz & Stegun 7.1.26 refined: |error| < 1.5e-7).
fn erf(x: f32) -> f32 {
let s = x.signum();
let x = x.abs() as f64;
let t = 1.0 / (1.0 + 0.327_591_1 * x);
let y = 1.0 - (((((1.061_405_429 * t - 1.453_152_027) * t) + 1.421_413_741) * t - 0.284_496_736) * t + 0.254_829_592) * t * (-x * x).exp();
s * y as f32
}
/// GELU (the exact, erf form, as PyTorch's `nn.GELU`), in place.
pub fn gelu(x: &mut [f32]) {
x.par_chunks_mut(4096).for_each(|c| {
for v in c {
*v = 0.5 * *v * (1.0 + erf(*v * std::f32::consts::FRAC_1_SQRT_2));
}
});
}
pub fn relu(x: &mut [f32]) {
for v in x {
*v = v.max(0.0);
}
}
/// `a += b`.
pub fn add(a: &mut [f32], b: &[f32]) {
a.par_chunks_mut(4096).zip(b.par_chunks(4096)).for_each(|(a, b)| {
for (x, y) in a.iter_mut().zip(b) {
*x += y;
}
});
}
/// Softmax of each row of `n` values, in place.
pub fn softmax_rows(x: &mut [f32], n: usize) {
if n == 0 {
return;
}
for row in x.chunks_mut(n) {
let m = row.iter().copied().fold(f32::NEG_INFINITY, f32::max);
let mut s = 0.0;
for v in row.iter_mut() {
*v = (*v - m).exp();
s += *v;
}
let inv = 1.0 / s.max(1e-30);
for v in row.iter_mut() {
*v *= inv;
}
}
}
/// Token counts and channel layout shared by the query, key and value tensors.
#[derive(Clone, Copy, Debug)]
pub struct AttentionShape {
pub query_tokens: usize,
pub key_tokens: usize,
pub heads: usize,
pub head_dim: usize,
}
/// Multi-head scaled dot-product attention with token-major tensors, heads side by side,
/// and an optional per-head bias `[heads × query_tokens × key_tokens]`.
pub fn attention(q: &[f32], k: &[f32], v: &[f32], shape: AttentionShape, bias: Option<&[f32]>) -> Vec<f32> {
let AttentionShape { query_tokens: nq, key_tokens: nk, heads, head_dim: hd } = shape;
let dim = heads * hd;
let mut out = vec![0.0f32; nq * dim];
if q.len() < nq * dim || k.len() < nk * dim || v.len() < nk * dim {
return out;
}
let scale = 1.0 / (hd as f32).sqrt();
for h in 0..heads {
// This head's q, kᵀ and v as contiguous matrices.
let qh: Vec<f32> = (0..nq).flat_map(|i| q[i * dim + h * hd..][..hd].iter().map(|x| x * scale)).collect();
let mut kt = vec![0.0f32; hd * nk];
for j in 0..nk {
for d in 0..hd {
kt[d * nk + j] = k[j * dim + h * hd + d];
}
}
let vh: Vec<f32> = (0..nk).flat_map(|j| v[j * dim + h * hd..][..hd].iter().copied()).collect();
let mut s = match bias.and_then(|b| b.get(h * nq * nk..(h + 1) * nq * nk)) {
Some(b) => b.to_vec(),
None => vec![0.0; nq * nk],
};
gemm(&qh, nq, hd, &kt, nk, &mut s);
softmax_rows(&mut s, nk);
let mut oh = vec![0.0f32; nq * hd];
gemm(&s, nq, nk, &vh, hd, &mut oh);
for i in 0..nq {
out[i * dim + h * hd..][..hd].copy_from_slice(&oh[i * hd..][..hd]);
}
}
out
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn multi_head_cross_attention_matches_direct_sums() {
let shape = AttentionShape { query_tokens: 2, key_tokens: 3, heads: 2, head_dim: 2 };
let q = [1.0, -0.5, 0.25, 2.0, -1.0, 0.75, 1.5, -0.25];
let k = [0.5, 1.0, -0.5, 0.25, 1.5, -0.25, 0.75, 1.0, -1.0, 0.5, 2.0, -1.5];
let v = [1.0, 2.0, 3.0, 4.0, -1.0, 0.5, 1.5, -2.0, 0.25, 0.75, -0.5, 2.5];
let bias = [0.0, 0.5, -0.5, 1.0, 0.0, -1.0, -0.25, 0.25, 0.5, 0.0, -0.5, 1.0];
for bias in [None, Some(bias.as_slice())] {
let actual = attention(&q, &k, &v, shape, bias);
for query in 0..shape.query_tokens {
for head in 0..shape.heads {
let mut scores: Vec<f32> = (0..shape.key_tokens)
.map(|key| {
let dot: f32 = (0..shape.head_dim).map(|channel| q[query * 4 + head * 2 + channel] * k[key * 4 + head * 2 + channel]).sum();
dot / (shape.head_dim as f32).sqrt() + bias.map_or(0.0, |b| b[(head * 2 + query) * 3 + key])
})
.collect();
let max = scores.iter().copied().fold(f32::NEG_INFINITY, f32::max);
for score in &mut scores {
*score = (*score - max).exp();
}
let total: f32 = scores.iter().sum();
for channel in 0..shape.head_dim {
let expected: f32 = scores.iter().enumerate().map(|(key, score)| score / total * v[key * 4 + head * 2 + channel]).sum();
assert!((actual[query * 4 + head * 2 + channel] - expected).abs() < 1e-6);
}
}
}
}
}
#[test]
fn gemm_matches_naive() {
let (m, k, n) = (130, 17, 9);
let a: Vec<f32> = (0..m * k).map(|i| ((i * 7) % 13) as f32 - 6.0).collect();
let b: Vec<f32> = (0..k * n).map(|i| ((i * 5) % 11) as f32 - 5.0).collect();
let mut c = vec![1.0f32; m * n];
gemm(&a, m, k, &b, n, &mut c);
for i in 0..m {
for j in 0..n {
let want: f32 = 1.0 + (0..k).map(|p| a[i * k + p] * b[p * n + j]).sum::<f32>();
assert_eq!(c[i * n + j], want);
}
}
}
#[test]
fn convolutions_match_direct_sums() {
// 3×3 stride-2 conv on a 5×4×2 input vs. the definition.
let (h, w, inp, out) = (5, 4, 2, 3);
let x: Vec<f32> = (0..h * w * inp).map(|i| (i % 7) as f32 * 0.5).collect();
let wt: Vec<f32> = (0..out * inp * 9).map(|i| ((i % 5) as f32 - 2.0) * 0.25).collect();
let b = [0.1, -0.2, 0.3];
let conv = Conv::new(&wt, Some(&b), out, inp, 3, 2, 1).unwrap();
let (y, oh, ow) = conv.forward(&x, h, w);
assert_eq!((oh, ow), (3, 2));
for oy in 0..oh {
for ox in 0..ow {
for o in 0..out {
let mut s = b[o];
for ci in 0..inp {
for ky in 0..3 {
for kx in 0..3 {
let (iy, ix) = ((oy * 2 + ky) as isize - 1, (ox * 2 + kx) as isize - 1);
if iy >= 0 && ix >= 0 && iy < h as isize && ix < w as isize {
s += x[(iy as usize * w + ix as usize) * inp + ci] * wt[((o * inp + ci) * 3 + ky) * 3 + kx];
}
}
}
}
assert!((y[(oy * ow + ox) * out + o] - s).abs() < 1e-5);
}
}
}
// Depthwise == a grouped conv: compare with Conv on each channel alone.
let dw_w: Vec<f32> = (0..inp * 9).map(|i| (i as f32 - 8.0) * 0.1).collect();
let dw = Depthwise::new(&dw_w, None, inp, 1).unwrap();
let (yd, _, _) = dw.forward(&x, h, w);
for ci in 0..inp {
let xc: Vec<f32> = (0..h * w).map(|p| x[p * inp + ci]).collect();
let single = Conv::new(&dw_w[ci * 9..ci * 9 + 9], None, 1, 1, 3, 1, 1).unwrap();
let (yc, _, _) = single.forward(&xc, h, w);
for p in 0..h * w {
assert!((yd[p * inp + ci] - yc[p]).abs() < 1e-5);
}
}
}
#[test]
fn gelu_and_softmax() {
let mut x = [-3.0f32, -1.0, 0.0, 1.0, 3.0];
gelu(&mut x);
// PyTorch's exact GELU values.
let want = [-0.004_049_7, -0.158_655_3, 0.0, 0.841_344_7, 2.995_950_3];
for (a, b) in x.iter().zip(want) {
assert!((a - b).abs() < 1e-5, "{a} {b}");
}
let mut s = [1.0f32, 2.0, 3.0];
softmax_rows(&mut s, 3);
assert!((s.iter().sum::<f32>() - 1.0).abs() < 1e-6 && s[2] > s[1]);
}
}
No file is open. Choose one in the tree, or press Ctrl+O (⌘O on a Mac) to find one by name.
Syntax highlighting could not load. The unmodified read-only text remains available above.