Comfy-Org / Comfy-Org/ComfyUI_frontend

Optimize curvesToLUT: Replace binary search with monotonic segment walk

Open
#9,118 0 comments 0 reactions 1 assignee Claimed by @christian-byrne View on GitHub
developer experience
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.