Commit a0a4cc0ebff7ac940262b60dbfe1006e6ea3efda separates parallel from sequential versions of fast_interpolate. The resulting benchmarks shows that there is no threshold for which fast_interpolate is faster than lagrange_interpolate, even though one would expect such a threshold to exist based on the asymptotics. I suspect the issue is due to these lines
let (left_zerofier, right_zerofier) = (
Self::zerofier(left_domain_half),
Self::zerofier(right_domain_half),
);
let (left_offset, right_offset) = (
right_zerofier.batch_evaluate(left_domain_half),
left_zerofier.batch_evaluate(right_domain_half),
);
which, in a recursive context, will end up computing the same zerofiers (or factors thereof) over and over again. To make the fast interpolation fast, we need to memoize the zerofiers or otherwise avoid doing redundant work.
[ ] pinpoint cause of slowness
[ ] fix slowness
This task is not critical because, as far as I can tell, no component in Triton VM or Neptune relies on it.
Commit a0a4cc0ebff7ac940262b60dbfe1006e6ea3efda separates parallel from sequential versions of
fast_interpolate. The resulting benchmarks shows that there is no threshold for whichfast_interpolateis faster thanlagrange_interpolate, even though one would expect such a threshold to exist based on the asymptotics. I suspect the issue is due to these lineswhich, in a recursive context, will end up computing the same zerofiers (or factors thereof) over and over again. To make the fast interpolation fast, we need to memoize the zerofiers or otherwise avoid doing redundant work.
This task is not critical because, as far as I can tell, no component in Triton VM or Neptune relies on it.