search

sisl / GridInterpolations.jl

Multidimensional grid interpolation in arbitrary dimensions
Other
52 stars 12 forks source link

Improve runtime performance of simplex interpolation #11

Open ptoman opened 7 years ago

ptoman commented 7 years ago

Simplex interpolation runs surprisingly slowly in benchmarks from December 2016. See images below. Simplex is blue; multilinear interpolation is red. Simplex interpolation is always slower than multilinear interpolation for up to 1 million points in a grid (the largest number of points tested).

I profiled the code to look into this and I marked the lines in the code that execute a large number of times. sortperm! is the biggest offender (currently line 276 of GridInterpolations.jl). Switching to the native Julia sortperm has minimal effect, which suggests the call needs to be removed entirely to stand a chance of faster performance with simplex than multilinear interpolation. To my fast-and-dirty read of the code, this may in fact be possible. It seems like sortperm might only be used to present the data in a conveniently sorted way to the user, a piece that I suspect we could drop from the API without further ado since multilinear interpolation doesn't uphold that requirement.

There is a branch named simplex_optimization, which I haven't looked at. There is a chance this issue is being addressed there.

speed_growing speed_constant "Where multilinear interpolation is almost instantaneous, simplex interpolation is between twice and ten times slower for all tests. It is possible that above 1 million points – when the lattice stops fitting in RAM – that simplex interpolation may perform better, although at that point, a coarser lattice may be more appropriate."

zsunberg commented 7 years ago

Thanks for reporting this, @ptoman