impulse response - How do real-time convolution plugins process audio so quickly

Okay, so in Logic Pro I can load up a Space Designer plugin (convolution reverb) with an impulse that's 9.1 seconds long, turn my mic on, and get real-time convolution reverb as the mic records incoming audio.

My question is: How could this be possible? My I/O buffer size is 32 samples. Is my computer capable of performing the convolution of a 401,310 sample impulse with a 32 sample block of audio in under 0.0007 seconds? If so, what kind of black magic do I need to get my own convolution reverb to do this?

I should mention that I am trying to develop real time convolution in C with portaudio. It works great when it's not real-time, but it's way too slow in real-time (the convolution I mentioned above takes 0.8 seconds using frequency-domain convolution which is supposed to be faster for impulses of that size, no?

Anyway any insight would be helpful, as I would really like to understand how this kind of real-time processing is possible.

Answer

Real-time low-latency partitioned convolution reverb with a long impulse response works by dividing the impulse response into unequally sized partitions. The shortest partitions (blocks) are at the beginning of the impulse response, and the partition length grows towards the end of the impulse response:

Each partition length can be processed separately, giving for each a latency that is for fast Fourier transform (FFT) -based convolution perhaps a couple of times the partition length. Convolution outputs for all partition lengths are summed forming the final composite output. When partitioning the impulse response, the partition of a particular length must not appear before the time that equals the latency of convolution of that partition length. A time-domain finite impulse response (FIR) filter can be used for the beginning of the impulse response because that may be more efficient than doing the low-length convolution by FFT.

What is the optimal partitioning for a given impulse response length and the optimal split point between time-domain FIR and FFT convolution should be tested on the target platform. A challenging aspect of non-uniform partitioned convolution is scheduling of the work.

Non-uniform partitioned convolution was popularized by William G. Gardner, Efficient Convolution without Input-Output Delay, J. Audio Eng. Soc., Vol. 43, No. 3, 1995 March, available online at http://www.cs.ust.hk/mjg_lib/bibs/DPSu/DPSu.Files/Ga95.PDF.