search

sisl / GridInterpolations.jl

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

Allocations in interpolants #51

Open zsunberg opened 1 month ago

zsunberg commented 1 month ago

It would be nice to avoid allocations altogether at interpolation time (see also #50).

This problem can alternatively be stated as "where should the memory for interpolants live?" I see three options:

  1. The user provides it. At first glance, one might think that a filling method like interpolate! might be able to solve this. However, the memory is needed for the return values of interpolants, not interpolate, so that is not the memory that we need.
  2. It is stored in the grid object. Before #44, we had vectors in the grid object. The only issue I see with this is that it might not be threadsafe (i.e. if one thread starts interpolating, and is interrupted by another, it could overwrite the weights without the first knowing)
  3. It is on the stack. This is conceptually the best way and what we pursued in #44. The problem is that the current algorithm involves mutating array elements, and it is difficult and unreliable to coax Julia into allocating MVectors on the stack. We could likely get this to work again, but it may not be sustainable.
  4. Avoid storing the interpolants altogether. Currently, the algorithms first computes the interpolants and then performs the weighted summing in the interpolate function. If we did it all in the same function, it may be easier to do everything on the stack.

@mykelk it seems like we might need to actually go back and understand the original algorithm for this :smile: . Do you remember where you got it from? A textbook or paper or something?

mykelk commented 1 month ago

For the algorithms, I was inspired by this paper when implementing the value function approximation for collision avoidance.

I think we do want to be able to support an API that returns the indices, but the function that does the interpolation does not have to call the index creating function.

zsunberg commented 1 month ago

I did a little more playing around, and found that in the benchmarks, interpolate for RectangleGrid does not allocate, so I think there is just an issue with using @ballocate in the tests for some reason.

Unfortunately, SimplexGrid does still allocate. I am not planning to fix it at this time, but if anyone wants to take a stab at it, PRs are welcome.

Since there does not appear to be a regression from previous performance, I am going to tag a new release with the recent changes.