Great and very detailed article!

1. I agree with that, a benchmark is needed here and I can even provide more than one implementation of this algorithm. Ill try to do this when Im home. Any idea on how should I benchmark this? Real world melee data or randomly generated?

2. The gain of theoretical speed increases as the size of our movie increases. So yes, in 1v1 I'm almost sure it is faster in practice, but I can't say the same about melee. Notice, though, that the number of iterations is in the order of <math>\log K</math>, where K is the number of inconsistent scans between 0 and BFT. It just happens that the worst case is when you have BFT scans. You do not need to store the interpolated scans in this array. You can just do a single interpolation after the algo is done, if you are linearly interpolating finding the impact point is very simple. So in terms of iterations, the difference is still good. But yeah, the difference becomes less and less noticeable as our movie gets sparser, even less if we do not be careful about cache misses.

3. The data is stored in objects and I do that in my code as well, but I would say it is ok to store the needed information in contiguous arrays as well, I just find it ugly.

Feel free to provide any other insight about this and even to post your implementations of this you find them useful! :)