Benchmarking interpolation functions.

Interpolation functions help turn low resolution discretely sampled signals back into their continuous counterparts. In this document we will be benchmarking the performance of a wide range of interpolators from MusicDSP.org, Paul Bourke, and Olli Niemitalo.

Wikipedia
In signal processing, sampling is the reduction of a continuous-time signal to a discrete-time signal. A common example is the conversion of a sound wave (a continuous signal) to a sequence of samples (a discrete-time signal). A sample is a value or set of values at a point in time and/or space

Essentially a computer will quantize a continuous-time domain signal by sampling it at a certain frequency known as the sampling rate, this leaves us with an array of points in memory that represent what was once a continuous signal now as a discretely sampled signal. If we wish to sample between the samples in the array we will need to interpolate between two given samples, commonly the most basic approach to this is to use linear interpolation which is basically a ramping function which ramps linearly from one point to the other. But, we can improve upon this by using more complicated polynomial methods of interpolation.

The application of these functions can range from audio applications, general digital signal processing such as communications, image filtering, and more.

This document has taken a number of advanced interpolation functions and benchmarked them, when it comes to the quality of these interpolators this is not a subject we will be touching upon in this document as it is generally already covered in the documents by the respective authors.

First of all, we have a bunch of random interpolation functions cobbled together from MusicDSP.com, a website that lacks somewhat in academic reputability however that is not to say it is all bad, albeit cobbled together snippets of code from the late ’90s to date of varying quality it resembles a DSP specific version of Rosetta Code, there are some real gems to be found here and some interesting insights spanning back through the years of DSP.

Second, we have a lovely selection from Paul Bourke, first published here. This includes the classic Linear Interpolation, Cosine Interpolation, Cubic/Catmull Interpolation, and Hermite Interpolation. A really great selection of interpolators to begin with.

And thirdly we have a very in-depth set of 51 different interpolators from Olli Niemitalo, these are very interesting interpolators, personally, some of my favourite since I first discovered them back in 2011, the original paper Olli published can be read over at his website here.

The benchmarks were performed using a 32-second window of subsequent executions measured in microsecond accuracy. Thus each figure represents the number of executions performed in that 32-second window.

On each iteration the rndData() function is called to randomise the array of data points the interpolators are sampling from, this helps to ensure that the compiler does not optimise away any vital code that would damage the validity of the final results.

Here are the benchmarks, -Ofast enabled…

An ODS file of the benchmark with comparison is available here.

I added class segmentation because the order tends to variate per benchmark but always tending to stay within a specific area of class rating, so for example, any interpolators in C class are likely to perform anywhere between 700,000,000 and 800,000,000 executions per 32-seconds. The class starts from the line below the class tag, so for example, osculating_45x() is part of the C class. Any interpolators with an asterisk * following them are ones I felt that held their position strongly within that class.

It goes without saying that LinearInterpolate() was always going to come out on top so to speak, but generally, many of the interpolators tended to perform around the 800,000,000 executions range which is only ~26% less than the linear interpolation function. I think that is brilliant and almost always worth the trade-off where higher quality interpolation is required! The optimal set of interpolators reached 732,867,435 executions at their lowest but I still think this is great performance, these are also my personal favourite when it comes down to a question of quality. The worst performing had to be the 65x and 65z variations which are short for 6-point, 5th-order coming in at the ~650,000,000 executions range, with the optimal variations achieving the best performance out of the 65z set coming in at 740,000,000 executions.

The code for the benchmark is available over at GitHub here.