FFT

主线位置：直接计算主线上，x.fft(None, 0, FftNorm::Backward, &mut engine) 和 matmul 一样借 engine 执行，落到 CPU 的 RustFFT / realfft 或 CUDA 的 cuFFT；traced 和 eager 主线上，FFT 是扩展算子（family tenferro-fft.fft.v1），执行模块和求导规则都由 tenferro-fft 提供。

flowchart TB
  t["Tensor fft"] --> spec["FftPlanSpec"]
  ex["FftExecutor"] --> spec
  tr["traced fft"] --> op["FftOp 扩展算子"]
  eg["eager fft"] --> op
  ip["fft_in_place"] --> cpu
  op --> spec
  spec --> probe["探测 engine"]
  probe --> cpu["CpuEngine"]
  probe --> cu["CudaEngine"]
  cpu -->|"复到复"| rf["RustFFT 逐 lane"]
  cpu -->|"实数"| rl["realfft 逐 lane"]
  cu --> cf["cuFFT"]

代码在 tenferro-fft：lib.rs（四种入口、扩展算子、AD 规则）、spec.rs（请求描述）、backend.rs（后端 trait）、cpu.rs 和 cpu/lanes.rs（CPU 执行）、cache.rs（计划缓存）、eager_in_place.rs（消耗输入的原地变换）、cuda/（cuFFT）。0.7.1 的 webgpu.rs（CubeK 在 Metal 上的 FFT）随整个 WebGPU / Metal 后端在 #2291 删掉了，CPU 和 CUDA 是仅剩的两个后端。本机没有 CUDA，下面的实测全是 CPU：实验在 exp-tenferro8/ops2-exp（fft_check、fft_timing），release，M2 Max、macOS 27、rustc 1.99.0。

上游的 tenferro-fft.md 指南和 fft-backend-execution.md 设计文档在 v0.8.0 上没跟着改：前者仍写「an explicitly selected Apple Metal path backed by CubeK」并教读者打开 webgpu feature，后者还有一整节「Apple shared execution」讲 AppleContext。这些在 0.8.0 里都不存在了。

一个请求，两个后端

用户接口是四个方法 fft、ifft、rfft、irfft，参数是可选的变换长度 n（截断或补零）、轴（可以是负数）和归一化 FftNorm（Backward 默认、Forward、Ortho，和 NumPy 一致）。它们在内部变成五种 FftOperation：

dtype 会变，所以没有 TypedTensor<T> 版本；只做一维变换，多维 FFT 要对每个轴各调一次。入口校验完操作、dtype、轴和长度后，打包成一个 FftPlanSpec，只描述「要算什么」。后端是 FftBackend（trait FftBackend: Engine），CpuEngine 和 CudaEngine 直接实现它。直接调用经 with_fft_exec_session：先探测传进来的 engine 是不是 CpuEngine，cuda feature 下再探测 CudaEngine，都不是就报 selected backend session does not expose an FFT execution capability；traced 和 eager 的扩展执行模块做同样的探测。设计文档定的规矩还在：后端处理不了就返回 Unsupported，不许自己建另一个后端、搬数据或悄悄退回 CPU。

CPU：复数走 RustFFT，实数走 realfft

impl FftBackend for CpuEngine 用 with_linalg_pool 借出 engine 的令牌和缓冲池（名字沿用线性代数那边），交给 pooled_transform。它按操作分两条路：复到复进 lanes::execute，用 RustFFT；R2cFull、R2cOnesided、C2r 进 lanes::execute_real，用 realfft。

张量是列主序的，要变换的轴不一定连续。所谓 lane 就是沿变换轴的一条一维序列，其余各轴每取一个下标就是一条。每条 lane 做四步：按步长收集进一块连续的 lane 缓冲（不足 n 的补零），变换，按归一化缩放，按步长写回输出。lane 缓冲从缓冲池借，用完还回去。并行的判断还是一个固定门槛：

    let jobs = if output_len < MIN_PARALLEL_ELEMENTS {
        1
    } else {
        exec.budget().get().min(lanes)
    };

MIN_PARALLEL_ELEMENTS 是 32 × 1024。输出不少于 32768 个元素时，把 lane 分给 min(令牌宽度, lane 数) 个任务，用 threadteam 的 exec.fork 并行；令牌来自 engine，串行 engine 的宽度是 1（见 engine 与 threadteam 池）。它不走逐元素运算那套按耗时估计的代价模型，而且并行只在 lane 之间：一条很长的一维序列只有一条 lane，在 8 线程 engine 上也是单线程算。

实数变换在 #2232（首次进入 v0.8.0）之前是「把实数补成复数、做全长复数 FFT、再丢掉一半」。现在 cached_real_plan 给出 realfft 的 RealToComplex / ComplexToReal 计划，R2cFull 再用共轭对称补出负频率那一半。C2r 交给 realfft 之前先把直流的虚部清零，偶数长度时再清掉 Nyquist 点的虚部：realfft 拒绝这两个位置带虚部的频谱，而 irfft 本来就忽略它们。奇数长度没有 Nyquist 点，最后一个频点的虚部要保留，这是后来的提交 872c244c（「fix(fft): preserve odd-length real spectra and inverse bins」）修的一个错误。

realfft 的「半长」只对偶数长度成立。它的 planner 对奇数长度建的是 RealToComplexOdd，内部直接做一个全长的复数 FFT。

正确性

fft_check 第 1、2 段把结果和朴素的 O(n²) DFT 比较（C64 / F64），实数变换取偶数、奇数和素数三种长度，沿 [3, n] 的第 1 轴：

n=    8: fft max err 8.88e-16 (max |X| 5.1), ifft max err 1.11e-16
n=   12: fft max err 2.70e-15 (max |X| 9.3), ifft max err 2.31e-16
n= 1009: fft max err 2.04e-11 (max |X| 50855.9), ifft max err 1.45e-14
n=   12: rfft [3,12] axis 1 -> [3, 7] (C64), row 0 err 1.41e-15; real-input fft -> [3, 12] err 1.41e-15; irfft round trip err 5.55e-16
n=   13: rfft [3,13] axis 1 -> [3, 7] (C64), row 0 err 2.32e-15; real-input fft -> [3, 13] err 2.32e-15; irfft round trip err 6.66e-16
n= 1009: rfft [3,1009] axis 1 -> [3, 505] (C64), row 0 err 1.09e-11; real-input fft -> [3, 1009] err 1.09e-11; irfft round trip err 1.46e-13
irfft n=8 with Im(DC)=3, Im(Nyquist)=7 equals with both 0: true
irfft n=9: last bin's imaginary part changes the result: true

n = 1009 的绝对误差 2e-11 相对于 5e4 的幅值是 4e-16 量级，大头来自朴素 DFT 自己的累加。最后两行就是上面那两条规则：偶数长度时直流和 Nyquist 的虚部被丢掉，奇数长度时最后一个频点的虚部参与运算。

实测：计划比变换还贵

fft_timing 在串行 engine 上对一维 f64 信号比较：rfft、实数输入的 fft（R2cFull）、先转成 C64 再 fft（相当于 0.7.1 的实数路径）、irfft，以及用 FftExecutor 反复调同一个变换。一维 15 到 50 次取最小值，跑三轮，负载 3 左右，下表取三轮的最小值（µs）：

• 偶数长度，rfft 比复数 FFT 快 1.4 到 2.2 倍：一次性调用时是 1.4–1.8 倍，用 FftExecutor 时是 1.6–2.2 倍。奇数长度（4097、65537、524289）完全没有区别，原因就是上面说的 RealToComplexOdd。
• 一次性调用的一半时间花在建计划上。 TensorFftExt::fft 这些方法每次新建一个容量为 1 的计划缓存（execute_concrete_fft_op），文档说它们「do not retain hidden process-global, thread-local, or backend-owned plan state between calls」。FftExecutor 自己持有一个缓存（默认 64 项），2^20 点的 rfft 从 8.7 ms 降到 4.3 ms，4096 点从 27.4 µs 降到 11.8 µs。traced 和 eager 用 engine 自己的扩展缓存（命名空间 rustfft-plans），同一个 engine 上重复执行也不重建。
• 素数因子大的长度很慢。 524289 = 3 × 174763，RustFFT 要走 Bluestein 一类算法，比 524288 慢 6 到 9 倍。

release notes 写的是「on a 524289-point input rfft takes 8.1 ms against 4.3 ms for MKL」，worklog 写的是「524289-point fixtures」。按字面理解成 524289 个实数输入，本机一次性 rfft 是 27 ms，和 8.1 ms 对不上；如果指的是 2^20 个实数输入、524289 个输出频点，本机一次性调用是 8.7 ms，和 8.1 ms 接近，用 FftExecutor 是 4.3 ms。仓库里找不到这个测量的输入定义，哪一种说法对没法确认；上游的测量机是 x86。

批量变换的并行，[n, 64] 的 C64 沿第 0 轴（64 条 lane），第二轮的输出：

[  256, 64] =   16384 elements: serial     56.0  team8     56.5  speedup 0.99
[  512, 64] =   32768 elements: serial    116.7  team8     32.5  speedup 3.59
[ 1024, 64] =   65536 elements: serial    248.0  team8     78.8  speedup 3.15
[ 1009, 64] =   64576 elements: serial   1111.2  team8    193.8  speedup 5.73

16384 个元素在门槛以下，8 线程 engine 也是单任务；32768 起分成 8 个任务。素数长度每条 lane 的计算量大，加速比更接近线程数。8 线程这一列每轮之间波动较大（512 那一行三轮是 38.2、32.5、67.2 µs）。

输出回到缓冲池

0.7.1 里 FFT 是唯一一个输出 drop 后回到缓冲池的运算；0.8.0 里所有运算族的池化输出都这样做了（#2098、#2100、#2103，见逐元素、SIMD 与融合）。FFT 这边的代码没变，pooled_transform 的最后一步：

    let mut output = PooledUninitOutput::<O>::new(buffers, shape)?;
    // SAFETY: Some(input) selects the out-of-place path with borrowed reads and
    // a disjoint fresh destination. Successful execution joins all writers and
    // initializes every element before the owning handoff.
    unsafe {
        if matches!(
            spec.operation(),
            FftOperation::R2cFull | FftOperation::R2cOnesided | FftOperation::C2r
        ) {
            lanes::execute_real(
                // ...
            )?;
        } else {
            lanes::execute(
                // ...
            )?;
        }
        output.assume_init_recycled()
    }

lane 内核直接写进这块最终的输出，不经过整块的中间缓冲。CpuEngine 还保留着一条给共享分配域（SharedTensorAllocationDomain）的路：先算进主机暂存缓冲，再整块拷进域里分配的输出。0.7.1 里用它的是 AppleContext，0.8.0 删掉之后只有测试里的假实现还在用（见存储与所有权）。

消耗输入的原地 FFT

eager 张量上有 fft_in_place / ifft_in_place（EagerTensorFftExt），只收 C32 / C64、紧凑列主序、没有别的句柄引用着的输入，在原分配上变换后交回一个不跟踪梯度的 eager 张量。apply 先校验，校验失败时 EagerFftInPlaceError::Rejected 把原输入原样还给调用方；拿到所有权之后再失败，输入就没了，不回滚。fft_check 第 5 段对 1..=6 的切片 [2..6] 做一次正变换、一次逆变换，再看整个底层分配：

slice [2..6] of 1..=6: fft = [Complex { re: 18.0, im: 0.0 }, Complex { re: -2.0, im: 2.0 }, Complex { re: -2.0, im: 0.0 }, Complex { re: -2.0, im: -2.0 }], same pointer: true
ifft back = [Complex { re: 3.0, im: 0.0 }, Complex { re: 4.0, im: 0.0 }, Complex { re: 5.0, im: 0.0 }, Complex { re: 6.0, im: 0.0 }]
whole root after the round trip = [Complex { re: 1.0, im: 0.0 }, Complex { re: 2.0, im: 0.0 }, Complex { re: 3.0, im: 0.0 }, Complex { re: 4.0, im: 0.0 }, Complex { re: 5.0, im: 0.0 }, Complex { re: 6.0, im: 0.0 }]
stride-2 slice: Err(in-place FFT input rejected: fft_in_place: unsupported operation: in-place FFT requires compact column-major input; use the borrowed FFT for strided views)

只变换切片那 4 个元素，指针不变，切片外的 1、2 没被碰过。步长为 2 的切片不紧凑，被拒绝，报错里给了替代办法。

AD 规则：只有复到复

FFT 的规则 FftAdRule 三种角色都注册了（semantic_ad_rules），内容很短，因为 DFT 是线性的。linearize 对切向量做同一个 FFT；转置和直接 VJP 共用 semantic_fft_adjoint，做方向相反、归一化取伴随的那个 FFT：

    pub(crate) fn c2c_adjoint(self) -> Self {
        match self {
            Self::Backward => Self::Forward,
            Self::Forward => Self::Backward,
            Self::Ortho => Self::Ortho,
        }
    }

（FftNorm::c2c_adjoint。）不缩放的正变换 F 的伴随是不缩放的逆变换 n · F⁻¹，即归一化取 Forward 的 ifft；Ortho 是酉变换，伴随就是逆。指定了 n 时，伴随的结果长度是 n，restore_semantic_c2c_adjoint_input_length 用 ShapeOf、DynamicTruncate、PadToMatch 把它截或补回输入的长度，这就是规则要把输入 0 声明为残差的原因（只读它的形状）。linearize 和 semantic_fft_adjoint 开头都有同一个判断：

        if !fft_op.operation.is_c2c() {
            return Err(semantic_fft_unsupported(
                fft_op.operation,
                SemanticAdRuleKind::Linearize,
            ));
        }

fft_check 第 3 段：L(x) = Σ w_k |FFT(x)_k|²，x 是 8 个实数，先 convert(DType::C64) 再 fft；第二个损失在 [8, 2] 上用 n = 16 补零、Ortho 归一化；再对 rfft、实数输入的 fft 和 irfft(rfft(x)) 各求一次导：

c2c fft: max|grad - fd| = 1.37e-8 (max |grad| 30.96)
c2c fft n=16 on [8, 2]: grad len 16, max|grad - fd| = 1.89e-9
rfft: grad Err(unsupported vjp AD rule for tenferro-fft.rfft.v1)
fft of real input: grad Err(unsupported vjp AD rule for tenferro-fft.rfft.v1)
irfft(rfft(x)): grad Err(unsupported vjp AD rule for tenferro-fft.irfft.v1)
c2c via TracedTensorAdExt::grad: Err(unsupported vjp AD rule for tenferro-fft.fft.v1)

复到复的两个都和中心差分一致，补零后截回长度那一步也对，打印出来的两个误差和 0.7.1 时一样。实数输入的 fft（R2cFull）、rfft、irfft 都不可微，报错里的 family 名按操作给出（tenferro-fft.rfft.v1、tenferro-fft.irfft.v1），注册用的仍是 tenferro-fft.fft.v1。最后一行：TracedTensorAdExt::grad 的规则集是空的，要用带 FFT 规则的 AdContext（见 semantic AD 与扩展）。

CUDA（只读源码）

cuda feature 下 tenferro-fft 在运行期加载 cuFFT：先试环境变量 TENFERRO_CUFFT_PATH，再试 libcufft.so.11、.10、libcufft.so，找不到就报类型化错误，不会退回 RustFFT。cuFFT 计划和设备绑定，所以只放在 engine 自己的扩展缓存（命名空间 cufft-plans）里，调用方的 FftExecutor 缓存不会收到它；直接调用时先 take_extension_caches 把 engine 的缓存借出来，用完再还回去（上游 worklog issue-2206-fft-cuda-engine-ownership.md）。这些只来自源码，本机没有 CUDA，engine 本身见 CUDA。

动脑筋答案

fft_check 第 4 段：

fft: before         BufferPoolStats { buffers: 0, capacity_bytes: 0 }
fft: output alive   BufferPoolStats { buffers: 1, capacity_bytes: 65536 }
fft: output dropped BufferPoolStats { buffers: 2, capacity_bytes: 131072 }
matmul: before         BufferPoolStats { buffers: 0, capacity_bytes: 0 }
matmul: output alive   BufferPoolStats { buffers: 0, capacity_bytes: 0 }
matmul: output dropped BufferPoolStats { buffers: 1, capacity_bytes: 32768 }

• FFT 的输出还活着时，池里已经有 1 个 65536 字节的缓冲：那是串行时唯一一个任务的 lane 缓冲（4096 个 Complex64），变换完就还回了池。
• drop 输出后变成 2 个、131072 字节：输出本身（又是 4096 个 Complex64）也回来了。
• matmul 的输出（4096 个 f64，32768 字节）drop 后同样回池。0.7.1 里这一行是 0：那时只有 FFT 用 assume_init_recycled，现在每个运算族都用。

小结

• 四个方法变成五种 FftOperation，打包成与后端无关的 FftPlanSpec，按 engine 类型分派到 FftBackend：CPU 是 RustFFT 和 realfft，CUDA 是运行期加载的 cuFFT；WebGPU / Metal 路径已删除（#2291），上游的 FFT 指南和设计文档还在描述它。
• CPU 逐条 lane 收集、变换、缩放、写回，输出不少于 32768 个元素时按 lane 并行，宽度来自 engine 的令牌；一条长的一维序列不并行。
• 实数变换走 realfft（#2232，v0.8.0），偶数长度比复数 FFT 快 1.4–2.2 倍，奇数长度没有区别。
• 一次性调用每次重建计划，大约占一半时间；重复变换用 FftExecutor，traced / eager 用 engine 的扩展缓存。
• 输出和 lane 缓冲都回缓冲池，这在 0.8.0 里不再是 FFT 独有。fft_in_place 接受带偏移的紧凑切片（#2023 / #2173，v0.8.0），只写切片内的元素。
• AD 只覆盖复到复：线性化是同一个 FFT，转置是反方向、伴随归一化的 FFT，补零时截回原长度，与差分一致。rfft、irfft、实数输入的 fft 仍不可微，先转成复数再变换可以绕过。