Incremental Computation Graphs
증분 계산 그래프
Yabu의 인터랙티브 타입 검사와 컴파일을 빠르게 하려고 계산을 의존성 그래프로 묶고 결과를 메모이제이션하는 방법을 설명합니다. 입력이 바뀌면 의존 경로를 red-green 방식으로 검증해 실제 값이 달라진 계산만 다시 실행합니다.
- 주제
에디터 노트
증분 계산에서 비용을 줄이는 기준은 입력이 바뀌었는지가 아니라 의존성 검증 뒤 결과가 달라졌는지입니다. 원문은 각 계산의 verified-at과 의존성 changed-at을 비교해 유효성을 확인하고, 확인한 하위 그래프를 같은 revision에서 재사용하는 절차를 보여줍니다. 다만 예시 컴파일러는 타입 검사 방향과 staging을 생략한 설명용 코드라 실제 Yabu 구현의 범위와 구분해야 합니다. 댓글에서 polywolf는 의존성의 변경 시점을 저장할 필요성을 질문하고, 작성자는 마지막 검증 이후 의존성이 바뀌지 않았음을 판단하는 데 쓴다고 답합니다. polywolf의 선제 재조회 방식은 값이 그대로인 의존성을 확인해 비싼 계산 재실행을 피하려는 별도 최적화입니다. 두 설명은 검증과 재실행을 줄이는 지점이 다르므로, 이 글의 설명만으로 Salsa와 다른 구현의 세부 동작까지 일반화할 수는 없습니다.
AI 요약
Yabu를 개발하면서 대화형 속도로 재컴파일하고 코드를 다시 생성하며 타입을 검사해야 했던 경험을 바탕으로 증분 계산 그래프를 설명합니다. 구현은 Salsa를 참고합니다. 그래프에는 외부에서 바뀌는 입력과 입력 또는 다른 계산의 결과만 사용하는 순수 계산이 있습니다. 입력은 함수 정의의 소스 문자열처럼 외부 변화의 출발점입니다. 계산 결과는 메모이제이션하고, 입력이 바뀌면 의존 관계를 따라 유효성을 다시 확인합니다.
입력에서 계산 그래프로
소스 문자열을 입력으로 두면 파서(parse)가 AST를 만들고, 타입 검사(typecheck)가 AST와 호출 함수들의 타입 시그니처를 확인하며, 컴파일(compile)이 결과물을 만듭니다. 이 계산들을 일반 함수 호출처럼 구성하되 호출한 계산을 기록하면 실행 중 의존성 그래프가 생깁니다. 예를 들어 컴파일은 타입 검사에 의존하고, 타입 검사는 파싱 결과와 AST에 등장하는 함수들의 타입 시그니처에 의존합니다. 함수 하나의 타입 시그니처가 바뀌면 그 함수를 참조하는 타입 검사 결과가 무효화됩니다. 관련 없는 계산은 그대로 재사용하므로 큰 프로그램도 인터랙티브하게 검사할 수 있다는 설명입니다.
본문의 compile 예시는 실제 Yabu 알고리즘을 정확히 구현한 코드가 아닙니다. 예시에서는 현재 함수가 다른 함수들의 타입에 맞는지만 검사합니다. 다른 함수들이 현재 함수에 맞는지는 검사하지 않으며 staging 시스템의 복잡성도 생략합니다. 실제 알고리즘은 Yabu의 Incremental Typesystem을 참고하라고 안내합니다.
Red-green walk와 메모이제이션
각 메모이제이션 항목에는 반환값, 마지막으로 유효성을 확인한 revision인 verified-at, 결과가 마지막으로 바뀐 revision인 changed-at, 의존성 목록이 들어갑니다. 의존성마다 해당 계산이 참조했을 당시의 changed-at도 기록합니다. 새 revision에서 계산을 요청하면 저장된 결과가 그 revision에서 이미 확인됐는지 살핍니다. 확인되지 않았다면 의존성을 따라가며 입력이 바뀌었는지 검증하고, 의존성 값이 그대로라면 계산 결과를 다시 쓰지 않습니다. 검증을 마친 항목의 verified-at은 현재 revision으로 갱신합니다. 같은 revision에서 다른 계산이 해당 항목을 요청하면 검증된 하위 그래프를 다시 훑지 않아도 됩니다.
예시에서는 R7에서 새 소스를 컴파일합니다. 아직 캐시가 없어 parse, typecheck 순으로 실행하고 결과를 저장합니다. 표준 라이브러리의 + 타입 시그니처는 R1에 만들어졌으므로 오래된 항목일 가능성이 있습니다. 의존하는 +의 소스도 R1에서 바뀐 뒤 그대로라면 타입 시그니처를 현재 revision에서 다시 확인한 것으로 표시합니다. 타입 검사가 통과하면 그 결과도 R7에 기록합니다. 이후 입력이 같을 때 다시 요청하면 의존성 검증만 거쳐 타입 검사와 컴파일을 건너뜁니다.
Lobsters 반응
- @polywolf — 더 길지만 알고리즘을 소개하는 흐름은 https://thunderseethe.dev/posts/lsp-base/ 가 낫다고 생각합니다. 자신이 구현한 알고리즘도 링크합니다. red-green의 핵심을 구현마다 조금씩 다르게 해석하는 점이 흥미롭다고 합니다. 의존성을 따라갈 때 각 의존성의 changed-at을 기록해야 하는 이유를 이 글에서 찾지 못했으며, 자신은 그 값 없이 구현했다고 합니다. 또 실제로 바뀐 의존성이 없는데도 비싼 계산을 다시 실행하지 않도록, 바뀌었을 가능성이 있는 의존성을 미리 다시 조회하는 방식을 추가했다고 설명합니다. 언젠가 Salsa의 구현도 살펴보고 싶다고 덧붙입니다.
- @marcecoll — 참고 자료를 알려줘서 고맙다고 합니다. 이 글은 알고리즘을 처음 이해하던 몇 달 전에 거칠게 썼고, 현재는 VCS와 CI 시스템을 만들면서 다시 사용하고 있다고 합니다. 계산을 캐시 가능한 그래프로 표현하면 최신 상태를 유지하려고 수동으로 조정하던 일이 줄어들어 데이터 모델을 다루기 좋다고 설명합니다. 자신의 구현에서는 changed-at이 마지막 계산 시점을 뜻하며, 쿼리를 T에 요청했을 때 마지막 검증이 T-1이면 오래됐을 가능성이 있다고 합니다. 의존성의 changed-at이 쿼리의 verified-at보다 앞서면 마지막 검증 이후 의존성이 바뀌지 않았으므로 결과가 유효하다고 판단한다고 설명합니다.
- @kchanqvq — GUI에서 더 관련이 있겠지만 glitch-free 전파 같은 문제도 처리하는지 묻고 lwcells 프로젝트를 소개합니다.
원문: dziban.net / 번역·요약: Trawling