Comfy-Org / Comfy-Org/ComfyUI_frontend
Optimize curvesToLUT: Replace binary search with monotonic segment walk
- Dominant language
- TypeScript
- Stars
- 2k
- Forks
- 699
- Avg merge
- 1d 7h
- Merged PRs (30d)
- 490
Description
## Context
In PR #8860, the `curvesToLUT` function currently calls `createMonotoneInterpolator` which performs a binary search for each of the 256 samples to locate the correct curve segment.
## Optimization Opportunity
Since `x = i / 255` is strictly increasing in the sampling loop, we can walk through the curve segments linearly instead of performing a binary search for every sample. This would improve the time complexity from O(256 log n) to O(256 + n).
## Proposed Approach
- Extract the interpolation logic (xs, ys, slopes) into a reusable precomputation function
- In `curvesToLUT`, maintain `lo` and `hi` segment indices across iterations
- Advance the segment pointers monotonically as x increases
- Inline the Hermite interpolation formula
## References
- PR: https://github.com/Comfy-Org/ComfyUI_frontend/pull/8860
- Discussion: https://github.com/Comfy-Org/ComfyUI_frontend/pull/8860#discussion_r2838856892
- Requested by: @christian-byrne
┆Issue is synchronized with this [Notion page](https://www.notion.so/Issue-9118-Optimize-curvesToLUT-Replace-binary-search-with-monotonic-segment-walk-3106d73d365081f89c48c31ec31af9af) by [Unito](https://www.unito.io)
Contributor guide
Assessment
This issue has not been assessed yet.