MATLAB interpolations, griddedInterpolant() ,faster

[azev77]

This issue came up on Discourse a few months ago: https://discourse.julialang.org/t/why-are-my-linear-interpolations-10x-faster-in-matlab/41232/25 still not resolved...

[mkitti]

This is the first that I am hearing about it. I probably was not maintainer then.

Was there a specific solution in that thread that needed to be implemented? It seems most of the issues were resolved outside of Interpolations.jl?

[azev77]

I'm not sure, but I think it's a good idea to keep this discussion on our radar

[mkitti]

Can you provide fresh benchmarks?

[azev77]

The original benchmarks were made by @elenev

[disberd]

Hi,

I just tried this on my computer with a very simple example as I was interested in this issue and indeed the MATLAB code seems faster even when disabling threading (griddedInterpolant is inherently multithreaded in MATLAB).

Here is my versioninfo: Julia Version 1.6.0 Commit f9720dc2eb (2021-03-24 12:55 UTC) Platform Info: OS: Windows (x86_64-w64-mingw32) CPU: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz WORD_SIZE: 64 LIBM: libopenlibm LLVM: libLLVM-11.0.1 (ORCJIT, skylake)

And here is a minimal MWE

using Interpolations, BenchmarkTools

a = 0:.01:1
b = a .^ 2
c = rand(10^6)
itp1 = LinearInterpolation((a,),b) # Regular Grid
itp2 = LinearInterpolation((b,),a) # Irregular Grid
@benchmark itp1($c)
@benchmark itp2($c)

Which gives me for the regular grid:

BenchmarkTools.Trial:
  memory estimate:  7.63 MiB
  allocs estimate:  2
  --------------
  minimum time:     9.028 ms (0.00% GC)
  median time:      10.242 ms (0.00% GC)
  mean time:        11.296 ms (7.81% GC)
  maximum time:     23.541 ms (30.73% GC)
  --------------
  samples:          442
  evals/sample:     1

and for the irregular grid:

BenchmarkTools.Trial:
  memory estimate:  7.63 MiB
  allocs estimate:  2
  --------------
  minimum time:     75.273 ms (0.00% GC)
  median time:      77.860 ms (0.00% GC)
  mean time:        78.652 ms (0.98% GC)
  maximum time:     88.830 ms (6.12% GC)
  --------------
  samples:          64
  evals/sample:     1

Timings with the same nodes and values using the griddedInterpolant (with method 'linear') on Matlab and timed with the builtin timeit function are the following:

~ 11ms for the regular grid ~ 42ms for the irregular one

Which is almost a 2x speedup for the irregular case w.r.t. Julia.

I don't know whether things could be done better in the Julia version though.

[mkitti]

To summarize, Interpolations.jl seems as fast on a regular grid, but is slow on an irregular grid compared to MATLAB. That is useful information. Thank you.

[MatFi]

Profiling revealed that it is because c is not sorted.

a = 0:.01:1
b = a .^ 2
c = sort(rand(10^6))  
itp1 = LinearInterpolation((a,),b) # Regular Grid
itp2 = LinearInterpolation((b,),a) # Irregular Grid
@benchmark itp1($c)
@benchmark itp2($c)

gave me

BenchmarkTools.Trial: 
  memory estimate:  7.63 MiB
  allocs estimate:  2
  --------------
  minimum time:     6.053 ms (0.00% GC)
  median time:      6.926 ms (0.00% GC)
  mean time:        6.955 ms (2.47% GC)
  maximum time:     11.225 ms (0.00% GC)
  --------------
  samples:          716
  evals/sample:     1

and on the irregular gird

BenchmarkTools.Trial: 
  memory estimate:  7.63 MiB
  allocs estimate:  2
  --------------
  minimum time:     26.695 ms (0.00% GC)
  median time:      27.518 ms (0.00% GC)
  mean time:        27.938 ms (0.56% GC)
  maximum time:     41.204 ms (0.00% GC)
  --------------
  samples:          179
  evals/sample:     1

the core of the problem seems to be this line https://github.com/JuliaMath/Interpolations.jl/blob/4f6f488f4457d9f9f8751bb30d240a0b33846d6b/src/gridded/indexing.jl#L148