Improve runtime performance of simplex interpolation

[ptoman]

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.

"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]

Thanks for reporting this, @ptoman