증분 계산은 언제 전체 재계산을 이기나
입력이 조금 바뀌었을 뿐인데 모든 것을 다시 계산하는 코드는 어디에나 있다. 파일 한 줄을 고치면 프로젝트 전체를 다시 타입 검사하고, 셀 하나를 바꾸면 리포트 전체를 다시 만든다. 해법은 단순해 보인다. 무엇이 무엇에 의존하는지 기록해 두고, 바뀐 부분만 다시 실행하면 된다.
문제는 그 기록에도 비용이 든다는 점이다. 의존성 그래프를 만들고 유지하며, 변경할 때마다 훑어야 한다. 따라서 증분 계산은 단순히 적용하면 빨라지는 기법이 아니라 분명한 손익분기점이 있는 거래다. 이 글에서는 실제 구현에서 공개한 수치를 바탕으로 그 분기점을 살펴본다.
그래프 전파는 무엇을 아끼고, 어떤 비용을 치르는가
Jane Street의 Incremental은 이 거래를 비교적 솔직하게 문서화한 사례다. 이 라이브러리는 입력 변수(Var.create), 조합 연산자(map2·bind), 관찰자(observe)를 이용해 방향성 비순환 그래프를 만든다. 값을 바꿔도 계산이 바로 실행되지는 않는다. Var.set은 입력만 갱신하고, 실제 재계산은 stabilize()를 호출할 때 영향을 받은 부분 그래프에서만 일어난다. 변경과 계산을 분리했기 때문에 한 틱 안에서 여러 입력이 바뀌어도 재계산은 한 번이면 된다.
그에 따른 비용도 같은 문서에 나와 있다. 노드 하나를 처리하는 데 약 30ns가 든다(blog.janestreet.com). 이 수치가 손익분기점을 정한다. 노드 하나가 수행하는 작업이 30ns보다 훨씬 무겁거나, 전체 그래프에서 실제로 다시 계산할 부분이 매우 작아야 이득이 남는다.
반대로 각 노드가 덧셈 한 번 정도만 수행하고, 입력이 바뀔 때마다 그래프 대부분이 영향을 받는다면 처음부터 모두 다시 계산하는 편이 빠르다. 같은 글에는 배열을 이진 트리 형태로 묶어 갱신 비용을 log(n)으로 줄이는 예가 나온다. 이는 단순히 기법이 좋아서가 아니라 의존성 구조를 의도적으로 얕게 설계했기 때문이다. 그래프의 깊이와 팬아웃은 라이브러리가 아니라 설계자가 결정한다.
진짜 절약은 조기 차단에서 나온다
의존성만 따라가는 단순한 구현은 생각보다 자주 불필요한 일을 한다. 입력이 바뀌면 의존하는 계산을 모두 무효화하지만, 중간 결과가 이전과 같은 경우도 흔하기 때문이다. 파일에 공백 하나를 추가하면 파싱 결과는 달라질 수 있어도 타입 시그니처는 그대로일 수 있다. 이 지점에서 전파를 멈출 수 있느냐가 성능을 가른다.
Salsa가 rustc에서 이어받은 red-green 알고리즘은 이 문제를 정면으로 다룬다. 데이터베이스는 현재 리비전을 관리하고, 입력이 설정될 때마다 그 값을 올린다. 각 입력에는 값이 마지막으로 바뀐 리비전을 기록한다. 추적 함수는 자신이 의존한 다른 추적 함수와 그 함수들이 마지막으로 변경된 리비전도 함께 저장한다. 다시 호출됐을 때 의존성이 하나도 바뀌지 않았다면 캐시된 값을 반환하고 실행을 건너뛴다.
핵심은 백데이팅(backdating)이다. 입력이 바뀌어 함수를 다시 실행했더라도 출력이 이전과 같으면, 시스템은 해당 출력이 실질적으로 바뀌지 않은 것으로 기록한다(salsa-rs.github.io). 그러면 무효화가 후속 계산으로 더 퍼지지 않는다.
이것이 조기 차단이며, 실무에서 증분 계산이 효과를 내는 핵심 요인이다. 의존성 추적은 다시 확인할 범위를 좁혀줄 뿐이다. 실제 작업량을 줄이는 것은 재계산한 결과가 이전과 같은지 값싸게 판단하는 능력이다. 결과값을 비교하는 비용이 크다면 이 장점도 사라진다.
검증 비용까지 없애는 두 번째 축
조기 차단에도 한계는 있다. 아무것도 다시 계산하지 않더라도 캐시가 유효한지 확인하려면 그래프를 따라가야 한다. 재계산 비용은 없어도 검증 비용은 남는다.
rust-analyzer는 이 문제를 크게 겪었다. 사용자가 입력할 때마다 프로젝트 코드는 바뀌지만, 표준 라이브러리는 대개 세션 내내 그대로다. 그런데도 src/lib.rs를 한 번 수정할 때마다 표준 라이브러리와 관련된 쿼리를 모두 검증해야 했고, 이 작업에만 약 300ms가 걸렸다(rust-analyzer.github.io). 재계산이 아니라 순수한 확인 비용이었다. 자동완성 응답에 300ms가 추가되는 것은 치명적이다.
해법은 전역 버전 번호 하나를 내구성 등급별 성분으로 나눈 버전 벡터였다. 표준 라이브러리 입력은 durable, 사용자 코드는 volatile로 표시한다. 파생 쿼리는 자신이 직접 의존하는 입력 가운데 가장 낮은 내구성을 자동으로 물려받는다. 낮은 내구성의 성분은 높은 내구성의 성분이 오를 때 함께 오른다.
검증할 때는 쿼리의 내구성 등급에 해당하는 성분만 비교한다. 그 성분이 바뀌지 않았다면 하위 그래프 전체를 건너뛸 수 있다. 개별 의존성 간선을 따라갈 필요도 없다. 여기서 얻을 수 있는 교훈은 분명하다. 변경 빈도가 다른 입력을 같은 등급으로 묶으면, 가장 자주 바뀌는 입력이 전체 검증 비용을 결정한다.
수요 주도와 갱신 주도는 다르다
증분 계산 구현은 크게 두 방식으로 나뉜다. 입력이 바뀌는 즉시 변경을 아래로 전파하는 갱신 주도 방식과, 누군가 결과를 요청할 때까지 계산을 미루는 수요 주도 방식이다.
Adapton은 후자를 명시적인 설계 원칙으로 삼는다. 관찰자가 요구한 계산만 다시 실행하고, 변경 사항은 요구 계산 그래프(demanded computation graph)에 계층적으로 기록한다(cs.umd.edu). 아무도 사용하지 않는 중간 결과는 갱신하지 않는다. 나중에 실제로 요청됐을 때 최신 입력을 기준으로 계산한다. Incremental의 observe도 비슷하다. 관찰되지 않는 노드는 안정화 대상이 아니다.
이 차이는 UI와 서버에서 서로 다른 결과를 낳는다. 화면에 보이는 결과만 필요한 UI에서는 수요 주도가 효과적이다. 스크롤 밖에 있는 행 1만 개를 계산할 이유가 없다.
반면 알림이나 모니터링처럼 아무도 보고 있지 않아도 조건이 충족되는 순간을 놓쳐서는 안 되는 시스템에서는 수요 주도가 위험할 수 있다. 관찰자가 없으면 계산도 일어나지 않기 때문이다. 이런 시스템에서는 관찰자를 상주시켜 사실상 갱신 주도로 동작하게 해야 한다. 라이브러리를 고르기 전에 결과가 언제 필요한지부터 정해야 한다.
도입하지 말아야 할 신호
앞의 수치를 반대로 보면 증분 계산을 도입하지 말아야 할 조건도 드러난다.
노드당 작업이 30ns 안팎으로 가볍고 그래프도 작다면 관리 비용이 이득을 삼킨다. 입력이 바뀔 때마다 결과도 거의 항상 바뀌는 영역에서는 조기 차단이 작동하지 않는다. 전체를 다시 계산하면서 그래프 유지 비용까지 추가로 내는 셈이다.
결과값의 동등성 비교가 비싸거나 부정확해도 백데이팅의 효과가 줄어든다. 큰 구조체를 매번 깊게 비교해야 하는 경우가 대표적이다. 변경 빈도가 서로 다른 입력을 등급 구분 없이 한데 묶으면, rust-analyzer가 겪었던 300ms 같은 순수 검증 비용도 발생할 수 있다.
반대 조건이라면 도입을 검토할 만하다. 전체 입력 가운데 다시 계산할 대상이 극히 일부이고, 중간 결과가 자주 그대로 유지되며, 노드 하나를 계산하는 비용이 크고, 같은 계산을 초당 여러 번 반복하는 경우다. 컴파일러 프런트엔드, 실시간 대시보드, 트레이딩 시스템의 파생 지표가 여기에 몰려 있는 것은 우연이 아니다.
마지막으로 구현 비용도 고려해야 한다. Jane Street는 Incremental을 일곱 번 다시 구현했다(janestreet.com). 인터페이스만 바꾼 것이 아니라 그래프 유지, 실행 순서 결정, 메모리 회수 전략을 계속 고쳤다. 증분 계산 시스템을 직접 만들 생각이라면 첫 번째 구현이 마지막이 아닐 가능성까지 예산에 넣어야 한다.
참고
[1] Jane Street. Introducing Incremental. Jane Street Tech Blog.
[2] Jane Street. Seven Implementations of Incremental. Jane Street Tech Talks.
[3] Salsa. The “red-green” algorithm. Salsa Reference.
[4] rust-analyzer. Durable Incrementality. 2023-07-24.
[5] Hammer, M. 외. Adapton: Composable, Demand-Driven Incremental Computation. PLDI 2014.
[6] Jane Street. janestreet/incremental. GitHub.