증분 컴파일

증분 컴파일 방식은 본질적으로 전체 쿼리 시스템을 놀라울 만큼 간단하게 확장한 것입니다. 먼저 실제 구현을 약간 단순화한 변형인 “기본 알고리즘“을 설명한 다음, 가능한 몇 가지 개선 사항을 설명하겠습니다.

기본 알고리즘

기본 알고리즘은 레드-그린 알고리즘¹이라고 부릅니다. 핵심 아이디어는 컴파일러를 실행할 때마다 수행한 모든 쿼리의 결과와 쿼리 DAG를 저장한다는 것입니다. 쿼리 DAG는 어떤 쿼리가 다른 어떤 쿼리를 실행했는지를 색인하는 DAG입니다. 예를 들어 Q1을 계산하는 데 Q2의 계산이 필요했다면 쿼리 Q1에서 다른 쿼리 Q2로 가는 간선이 존재합니다(쿼리는 자기 자신에 의존할 수 없으므로 그 결과는 일반 그래프가 아닌 DAG가 된다는 점에 유의하십시오).

참고: 쿼리를 단순히 쿼리의 정의로 생각할 수도 있습니다. 즉, 함수와 비슷하게 호출할 수 있고, 캐시된 결과를 반환하거나 실제로 코드를 실행하는 것입니다.

쿼리를 그렇게 생각하고 있다면, 이어지는 글에서 쿼리가 색을 가진다고 표현한다는 점을 알아 두는 것이 좋습니다. 다만 여기서 쿼리라는 단어는 특정 입력에 대한 쿼리의 특정 호출을 가리키기도 한다는 점을 명심하십시오. 뒤에서 읽게 되겠지만, 쿼리는 인자를 기반으로 핑거프린트(fingerprint)가 매겨집니다. 쿼리의 결과는 어떤 인자를 주었을 때는 바뀌어 빨간색이 될 수 있고, 다른 인자에 대해서는 그대로 유지되어 초록색이 될 수 있습니다.

요컨대 여기서 쿼리라는 단어는 쿼리의 정의만을 뜻하는 것이 아니라, 주어진 인자를 가진 해당 쿼리의 특정 인스턴스를 뜻하기도 합니다.

그러면 다음번 컴파일러 실행에서는 이 쿼리 결과를 재사용하여 쿼리를 다시 실행하지 않아도 되는 경우가 있습니다. 이를 위해 모든 쿼리에 색을 지정합니다:

쿼리가 빨간색이라면, 이번 컴파일에서의 결과가 이전 컴파일과 비교해 바뀌었다는 뜻입니다.
쿼리가 초록색이라면, 그 결과가 이전 컴파일과 같다는 뜻입니다.

여기에는 두 가지 핵심 통찰이 있습니다:

첫째, 쿼리 Q의 모든 입력이 초록색이라면 쿼리 Q는 지난번과 같은 값을 반드시 내야 하므로 다시 실행할 필요가 없습니다(그렇지 않다면 컴파일러가 결정적이지 않은 것입니다).
둘째, 쿼리의 일부 입력이 바뀌더라도 그 쿼리는 여전히 이전 컴파일과 같은 결과를 낼 수 있습니다. 특히 쿼리는 입력의 일부만 사용할 수도 있습니다.
- 따라서 쿼리를 실행한 후에는 항상 이전과 같은 결과를 냈는지 확인합니다. 같은 결과를 냈다면 여전히 그 쿼리를 초록색으로 표시할 수 있고, 따라서 의존하는 쿼리를 다시 실행하지 않아도 됩니다.

try-mark-green 알고리즘

증분 컴파일의 핵심에는 “try-mark-green“이라는 알고리즘이 있습니다. 이 알고리즘은 주어진 쿼리 Q(아직 실행되지 않았어야 함)의 색을 결정하는 역할을 합니다. Q에 빨간색 입력이 있는 경우 Q의 색을 결정하려면 출력을 비교하기 위해 Q를 다시 실행해야 할 수도 있지만, Q의 입력이 모두 초록색이라면 Q를 다시 실행하거나 그 값을 전혀 살펴보지 않고도 Q가 초록색일 수밖에 없다고 결론 내릴 수 있습니다. 컴파일러에서는 이 덕분에 필요하지 않을 때 디스크에서 결과를 역직렬화하지 않아도 되며, 실제로 때로는 결과를 직렬화하는 것도 생략할 수 있습니다(아래의 개선 사항 절을 참고하십시오).

try-mark-green은 다음과 같이 동작합니다:

먼저 쿼리 Q가 이전 컴파일 중에 실행되었는지 확인합니다.
- 실행되지 않았다면 평소처럼 쿼리를 다시 실행하고 빨간색을 지정하면 됩니다.
그렇다면 Q의 ’의존 쿼리’를 불러옵니다.
저장된 결과가 있으면 쿼리 DAG에서 reads(Q) 벡터를 불러옵니다. “reads“는 Q가 실행되는 동안 실행한 쿼리의 집합입니다.
- reads(Q)에 있는 각 쿼리 R에 대해 try-mark-green을 사용하여 R의 색을 재귀적으로 요청합니다.
  - 참고: reads(Q)의 각 노드는 원래 컴파일에서 발생한 순서와 같은 순서로 방문해야 합니다. 아래의 쿼리 DAG 절을 참조하십시오.
  - reads(Q)의 노드 중 어느 하나라도 최종적으로 빨간색으로 칠해지면 Q는 더티(dirty) 상태입니다.
    - Q를 다시 실행하고 그 결과의 해시를 이전 컴파일 결과의 해시와 비교합니다.
    - 해시가 바뀌지 않았다면 Q를 초록색으로 표시하고 반환할 수 있습니다.
  - 그렇지 않은 경우에는 reads(Q)의 노드가 모두 초록색이어야 합니다. 이 경우 Q를 초록색으로 칠하고 반환할 수 있습니다.

쿼리 DAG

쿼리 DAG 코드는 compiler/rustc_middle/src/dep_graph에 있습니다. DAG는 쿼리 실행을 계측하여 구성합니다.

핵심은 쿼리 DAG가 순서도 추적한다는 점입니다. 즉, 각 쿼리 Q에 대해 Q가 읽는 쿼리뿐만 아니라 그 쿼리들을 읽은 순서도 추적합니다. 덕분에 try-mark-green은 그 쿼리들을 같은 순서로 다시 따라갈 수 있습니다. 이것이 중요한 이유는 하위 쿼리가 빨간색으로 판정되는 순간부터는 Q가 이전과 같은 경로를 계속 따라갈 것이라고 더 이상 확신할 수 없기 때문입니다. 예를 들어 다음과 같은 쿼리를 생각해 보십시오.

fn main_query(tcx) {
    if tcx.subquery1() {
        tcx.subquery2()
    } else {
        tcx.subquery3()
    }
}

이제 첫 번째 컴파일에서 main_query가 subquery1을 실행하는 것으로 시작하고, 이것이 true를 반환한다고 가정해 보십시오. 이 경우 main_query가 다음으로 실행하는 쿼리는 subquery2가 되며, subquery3는 전혀 실행되지 않습니다.

그런데 이제 다음 컴파일에서 입력이 바뀌어 subquery1이 false를 반환한다고 가정해 보십시오. 이 경우 subquery2는 결코 실행되지 않습니다. 그러나 try-mark-green이 reads(main_query)를 순서와 다르게 방문한다면 subquery1보다 먼저 subquery2를 방문하여 그것을 실행해 버릴 수도 있습니다. 이는 컴파일러에서 ICE를 비롯한 여러 문제를 일으킬 수 있습니다.

기본 알고리즘의 개선

기본 알고리즘을 설명할 때 컴파일이 끝나면 수행된 모든 쿼리의 결과를 저장한다고 했습니다. 실제로는 이 방식이 상당히 낭비일 수 있습니다. 그 결과 중 상당수는 다시 계산하는 비용이 매우 적어서, 직렬화하고 역직렬화해도 별다른 이득이 없습니다. 실제로는 수행한 모든 하위 쿼리의 해시를 저장합니다. 그리고 일부 경우에는 결과도 저장합니다.

이 때문에 증분 알고리즘은 노드의 색을 계산하는 일과 노드의 결과를 계산하는 일을 분리하며, 색을 계산할 때는 노드의 값이 필요하지 않은 경우가 많습니다. 결과는 다음과 같은 간단한 알고리즘으로 계산합니다.

Q에 대해 저장된 결과가 있는지 확인합니다. 저장된 결과가 있으면 Q의 색을 계산합니다. Q가 초록색이면 저장된 결과를 역직렬화하여 반환합니다.
그렇지 않으면 Q를 실행합니다.
- 그런 다음 결과의 해시를 비교하여 결과가 바뀌지 않았으면 Q를 초록색으로 표시할 수 있습니다.

참고 자료

최초 설계 문서는 여기에서 볼 수 있습니다. 이 문서는 메모이제이션을 더 자세히 설명하고, 이 시스템의 전체적인 개요와 도입 동기도 제시합니다.

각주

오래전부터 이 알고리즘의 이름을 Salsa 알고리즘으로 바꾸고 싶었지만, 그 이름은 끝내 자리 잡지 못했습니다. -@nikomatsakis ↩

Keyboard shortcuts