O(n³) 컴파일 병목을 해결한 RNA 폴딩 알고리즘 기반 최적 스케줄링

Context

GHC의 ApplicativeDo 최적화 플래그가 O(n³)의 시간 복잡도로 인해 기본 비활성화된 상태임. Greedy 알고리즘은 컴파일 속도는 빠르나 독립적인 연산을 그룹화하지 못해 네트워크 Round-trip 횟수를 증가시켜 런타임 성능을 저하시킴.

Technical Solution

• Dependency Graph 모델링을 통한 문장 간 의존성 분석 및 Tree 구조의 최소 비용 경로 탐색
• RNA Folding 예측에 사용되는 Dynamic Programming 기법을 도입하여 최적의 Parallel/Sequential 조합 도출
• 전체 스팬을 독립적인 조각으로 분할하여 고비용 연산을 희소한 Dense Blob 영역으로 한정하는 Segment Decomposition 적용
• Longest-chain Tie-breaker와 Extreme-cut Shortcut을 통해 불필요한 탐색 공간을 제거하고 컴파일 시간 단축
• Matrix Multiplication 기반의 sub-cubic 알고리즘보다 실제 컴파일러 환경에 적합한 Local 최적화 경로 채택