What differences or other criteria can be used to help decide between using overlap-add and overlap-save for filtering? Both overlap-add and overlap-save are described as algorithms for doing FFT based fast convolution of data streams with FIR filter kernels. What are the latency, computational efficiency or caching locality (etc.) differences, if any? Or are they the same?
Essentially, OS is slightly more efficient since it does not require the addition of the overlapping transients. However, you may want to use OA if you need to reuse the FFTs with zero-padding rather than repeated samples.
Here is a quick overview from an article I wrote a while ago
Fast convolution refers to the blockwise use of circular convolution to accomplish linear convolution. Fast convolution can be accomplished by OA or OS methods. OS is also known as “overlap- scrap” . In OA filtering, each signal data block contains only as many samples as allows circular convolution to be equivalent to linear convolution. The signal data block is zero-padded prior to the FFT to prevent the filter impulse response from “wrapping around” the end of the sequence. OA filtering adds the input-on transient from one block with the input-off transient from the previous block. In OS filtering, shown in Figure 1, no zero-padding is performed on the input data, thus the circular convolution is not equivalent to linear convolution. The portions that “wrap around” are useless and discarded. To compensate for this, the last part of the previous input block is used as the beginning of the next block. OS requires no addition of transients, making it faster than OA.
OS efficiency can be tweaked even more by converting the filter impulse response from causal to non-causal. This Octave code snippet from Wikimedia shows two methods, as well as the usual causal-filter method:
if edge_effects_at_end_of_filter_output %Rotate the filter coefficients %Simple way % H = fft([h(M) zeros(1,N-M) h(1:M-1)]); %Fancy way H = fft( circshift([h zeros(1,N-M)], -(M-1)) ); Xb = (1:L); % indices of good output else H = fft(h,N); Xb = M-1 + (1:L); % indices of good output endif
The advantage is seen in the difference between the "indices of good output". Indices of $(1:L)$ mean that the inverse DFT output buffer of length $L+M-1$ can be positioned within the overall output array, overlapping the previous output segment by $M-1$. So $M-1$ previous outputs are simply overwritten (discarded), and there is no need to copy the $L$ "good" outputs from one buffer to another.