ZeroText가 prefix-sum binary search로 텍스트 줄 바꿈 알고리즘을 O(n)에서 O(log n)로 최적화하며 메모리 할당 없이 구현한다

Context

기존 텍스트 레이아웃 구현체는 한 문자씩 순차 탐색하며 너비를 누적하는 방식을 사용한다. 이 방식은 줄당 O(n) 시간 복잡도를 가지며, Canvas measureText 호출마다 새로운 TextMetrics 객체가 생성되는 할당 문제를 수반한다.

Technical Solution

• Float64Array prefix-sum 배열을 미리 계산하여 임의 구간 [a, b)의 총 너비를 O(1)로 조회한다
• 단조 증가하는 prefix-sum 배열에서 upper-bound binary search를 적용하여 줄 바꿈 위치를 O(log n)에 탐색한다
• Arena pool 패턴으로 Float64Array를 재사용하며 프레임 간 커서만 초기화한다
• ASCII(0-127) 문자에 대해 direct-index Float32Array로 해시 테이블 조회를 완전히 회피한다
• FNV-1a 해시로 텍스트를 해싱하여 LRU 캐시 키로 활용한다

Impact

10,000자 문서에서 500줄 처리 시 약 6,500번의 비교만 수행한다. Cold layout은 약 5.6μs, Hot layout(캐시 적중)은 약 100ns이다. Bundle size는 약 5KB minzipped이며 GC 일시 정지가 0이다.

Key Takeaway

누적 가중치로 시퀀스를 분할하는 모든 문제에서 prefix-sum 전처리와 binary search 조합이 선형 스캔을 대체하는 일반적 최적화 패턴이다.