# 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 thereductionof 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…

Executions in 32 seconds (higher is better) …

Fastest to slowest …LinearInterpolate()-- 1,043,021,450*- A CLASS

hermite4()----------- 864,143,335

CubicInterpolate()--- 861,368,667

hermite1()----------- 852,650,628

watte_42z()---------- 849,978,125 *

parabolic_42x()------ 845,329,016 *

parabolic_42z()------ 843,051,682 * - B CLASS

optimal32_42z()------ 842,327,674

optimal16_42z()------ 842,173,284

lagrange_43x()------- 824,777,726

optimal8_42z()------- 818,573,293

optimal4_43z()------- 817,554,978

CatmullInterpolate()- 817,184,839 *

optimal2_42z()------- 817,017,749

hermite3()----------- 815,787,715

optimal8_43z()------- 814,932,498

optimal_32z()-------- 814,597,788

optimal2_43z()------- 814,205,750

optimal16_43z()------ 813,596,244

optimal32_43z()------ 813,219,182

watte_42x()---------- 808,266,048

optimal2_44z()------- 808,242,622

HermiteInterpolate()- 803,204,436 * - C CLASS

lagrange_43z()------- 794,197,574

optimal16_23z()------ 793,989,204

hermite2()----------- 793,803,450

optimal4_42z()------- 787,663,466

optimal32_44z()------ 787,217,022

bspline_43x()-------- 785,941,426

bspline_43z()-------- 784,983,803

optimal4_44z()------- 780,245,345

optimal2_23z()------- 779,379,641

optimal16_44z()------ 778,057,097

optimal8_44z()------- 777,514,336

hermite_43x()-------- 776,101,332

optimal8_64z()------- 773,369,284

optimal16_64z()------ 772,615,012

optimal4_23z()------- 772,374,874

optimal2_64z()------- 769,535,479

hermite_43z()-------- 768,493,305

optimal8_23z()------- 766,868,773

optimal4_64z()------- 762,666,104

optimal32_64z()------ 759,502,144

osculating_45z()----- 754,361,072

optimal16_65z()------ 746,048,605

optimal32_65z()------ 743,849,077 *

optimal2_65z()------- 741,950,936

optimal8_65z()------- 740,090,345

order3Spline()------- 735,844,776

optimal4_65z()------- 732,867,435

hermite_63x()-------- 714,680,545

hermite_63z()-------- 709,276,578

osculating_45x()----- 706,546,540 - D CLASS

lagrange_65x()------- 699,041,053

bspline_65x()-------- 688,782,582

lagrange_65z()------- 678,868,756

osculating_65z()----- 671,200,187

hermite_65z()-------- 669,898,731

hermite_65x()-------- 646,029,454

osculating_65x()----- 626,678,371 *

CosineInterpolate()-- 555,128,841 *

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.