Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

증분 컴파일 상세

증분 컴파일 방식은 본질적으로 전체 쿼리 시스템을 놀라울 만큼 간단하게 확장한 것입니다. 이 방식은 다음 사실에 기반합니다:

  1. 쿼리는 순수 함수입니다 – 같은 입력이 주어지면 쿼리는 항상 같은 결과를 내놓습니다. 그리고
  2. 쿼리 모델은 컴파일을 비순환 그래프로 구조화하여 개별 계산 사이의 의존성을 명시적으로 드러냅니다.

이 장에서는 이러한 속성을 활용하여 작업을 증분 방식으로 만드는 방법을 설명한 다음, 버전 구현 문제를 논의합니다.

증분 쿼리 평가를 위한 기본 알고리즘

쿼리 평가 모델 입문에서 설명한 것처럼, 쿼리 호출은 방향성 비순환 그래프를 형성합니다. 앞 장의 예시를 다시 보겠습니다:

  list_of_all_hir_items <----------------------------- type_check_crate()
                                                               |
                                                               |
  Hir(foo) <--- type_of(foo) <--- type_check_item(foo) <-------+
                                      |                        |
                    +-----------------+                        |
                    |                                          |
                    v                                          |
  Hir(bar) <--- type_of(bar) <--- type_check_item(bar) <-------+

한 쿼리에서 다른 쿼리로의 모든 접근은 쿼리 컨텍스트를 거쳐야 하므로, 이러한 접근을 기록하여 이 의존성 그래프를 메모리에 실제로 빌드할 수 있습니다. 의존성 추적을 활성화하면, 컴파일이 끝났을 때 어떤 쿼리가 호출되었는지(그래프의 노드)와 각 호출에 대해 어떤 다른 쿼리나 입력이 해당 쿼리의 결과를 계산하는 데 사용되었는지(그래프의 간선)를 알 수 있습니다.

이제 bar의 HIR이 이전과 달라지도록 프로그램의 소스 코드를 변경한다고 가정해 봅시다. 우리의 목표는 변경의 영향을 실제로 받는 쿼리만 다시 계산하고, 나머지 모든 쿼리는 캐시된 결과를 재사용하는 것입니다. 의존성 그래프가 있으면 정확히 그렇게 할 수 있습니다. 주어진 쿼리 호출에 대해 그래프는 그 결과를 계산하는 데 어떤 데이터가 사용되었는지 정확히 알려 주므로, 변경된 무언가에 도달할 때까지 간선을 따라가기만 하면 됩니다. 변경된 것을 하나도 만나지 않는다면, 해당 쿼리가 여전히 캐시에 이미 있는 결과와 같은 결과로 평가된다는 것을 알 수 있습니다.

위의 type_of(foo) 호출을 예로 들면, 입력으로 향하는 간선을 따라가서 캐시된 결과가 여전히 유효한지 확인할 수 있습니다. 유일한 간선은 변경의 영향을 받지 않은 입력인 Hir(foo)로 이어집니다. 따라서 type_of(foo)에 대해 캐시된 결과가 여전히 유효하다는 것을 알 수 있습니다.

type_check_item(foo)의 경우는 조금 다릅니다: 다시 간선을 따라가면 type_of(foo)에는 문제가 없다는 것을 이미 알고 있습니다. 그다음 아직 확인하지 않은 type_of(bar)에 도달하므로 type_of(bar)의 간선을 따라가는데, 여기서 실제로 변경된 Hir(bar)를 만나게 됩니다. 그 결과 type_of(bar)는 캐시에 있는 것과 다른 결과를 낼 수 있으며, 이행적으로 type_check_item(foo)의 결과 역시 달라졌을 수 있습니다. 따라서 type_check_item(foo)를 다시 실행하고, 이는 다시 type_of(bar)를 재실행하며, type_of(bar)는 최신 버전의 Hir(bar)를 읽으므로 최신 결과를 내놓습니다. 또한 type_of(bar)의 결과가 달라졌을 수 있으므로 type_check_item(bar)도 다시 실행합니다.

기본 알고리즘의 문제점: 거짓 양성

앞 단락을 주의 깊게 읽었다면, 입력 중 하나가 변경되었기 때문에 type_of(bar)가 변경되었을 수도 있다고 적혀 있다는 점을 알아차렸을 것입니다. 입력이 변경되었음에도 여전히 정확히 같은 결과를 낼 가능성도 있습니다. 정수의 부호만 계산하는 간단한 쿼리를 예로 들어 보겠습니다:

  IntValue(x) <---- sign_of(x) <--- some_other_query(x)

IntValue(x)가 처음에 1000이었다가 이후 2000으로 설정된다고 합시다. 두 경우에 IntValue(x)는 서로 다르지만, sign_of(x)는 두 경우 모두 +라는 결과를 내놓습니다.

그러나 기본 알고리즘을 따르면, some_other_query(x)는 변경된 입력에 이행적으로 의존하므로 (불필요하게) 다시 평가되어야 합니다. 이 경우 변경 감지는 some_other_query(x)가 변경된 입력의 영향을 받을 수 있다고 보수적으로 가정해야 하므로 “거짓 양성“을 내놓습니다.

안타깝게도 실제 컴파일러의 쿼리에는 이와 같은 예가 가득하며, 입력의 작은 변경이 출력 바이너리의 매우 큰 부분에 영향을 줄 가능성이 있는 경우가 많습니다. 그 결과 변경 감지 시스템을 더 똑똑하고 정확하게 만들어야 했습니다.

정확도 개선: 레드-그린 알고리즘

“거짓 양성(false positive)” 문제는 변경 감지와 쿼리 재평가를 교차로 수행하여 해결할 수 있습니다. 어떤 캐시된 결과가 여전히 유효한지 알아내려 할 때 그래프를 입력까지 끝까지 따라가는 대신, 결과를 어쩔 수 없이 재평가한 뒤에 그 결과가 실제로 변경되었는지 확인할 수 있습니다.

이 알고리즘을 레드-그린 알고리즘이라고 부르는 이유는, 의존성 그래프의 노드에 대해 캐시된 결과가 여전히 유효함을 증명할 수 있으면 녹색을, 재평가한 뒤 결과가 달라진 것으로 판명되면 빨간색을 지정하기 때문입니다.

레드-그린 변경 추적의 핵심은 try-mark-green 알고리즘에 구현되어 있으며, 짐작하셨겠지만 이 알고리즘은 주어진 노드를 녹색으로 표시하려고 시도합니다:

fn try_mark_green(tcx, current_node) -> bool {

    // Fetch the inputs to `current_node`, i.e. get the nodes that the direct
    // edges from `node` lead to.
    let dependencies = tcx.dep_graph.get_dependencies_of(current_node);

    // Now check all the inputs for changes
    for dependency in dependencies {

        match tcx.dep_graph.get_node_color(dependency) {
            Green => {
                // This input has already been checked before and it has not
                // changed; so we can go on to check the next one
            }
            Red => {
                // We found an input that has changed. We cannot mark
                // `current_node` as green without re-running the
                // corresponding query.
                return false
            }
            Unknown => {
                // This is the first time we look at this node. Let's try
                // to mark it green by calling try_mark_green() recursively.
                if try_mark_green(tcx, dependency) {
                    // We successfully marked the input as green, on to the
                    // next.
                } else {
                    // We could *not* mark the input as green. This means we
                    // don't know if its value has changed. In order to find
                    // out, we re-run the corresponding query now!
                    tcx.run_query_for(dependency);

                    // Fetch and check the node color again. Running the query
                    // has forced it to either red (if it yielded a different
                    // result than we have in the cache) or green (if it
                    // yielded the same result).
                    match tcx.dep_graph.get_node_color(dependency) {
                        Red => {
                            // The input turned out to be red, so we cannot
                            // mark `current_node` as green.
                            return false
                        }
                        Green => {
                            // Re-running the query paid off! The result is the
                            // same as before, so this particular input does
                            // not invalidate `current_node`.
                        }
                        Unknown => {
                            // There is no way a node has no color after
                            // re-running the query.
                            panic!("unreachable")
                        }
                    }
                }
            }
        }
    }

    // If we have gotten through the entire loop, it means that all inputs
    // have turned out to be green. If all inputs are unchanged, it means
    // that the query result corresponding to `current_node` cannot have
    // changed either.
    tcx.dep_graph.mark_green(current_node);

    true
}

참고: 실제 구현은 compiler/rustc_middle/src/dep_graph/graph.rs에서 찾을 수 있습니다.

레드-그린 표시를 사용하면 변경 감지 중 거짓 양성이 누적되어 생기는 치명적인 효과를 피할 수 있습니다. 증분 모드에서 쿼리가 실행될 때마다, 먼저 그 쿼리가 이미 녹색인지 확인합니다. 녹색이 아니라면 그 쿼리에 대해 try_mark_green()을 실행합니다. 그 후에도 여전히 green이 아니라면, 실제로 쿼리 프로바이더를 호출하여 결과를 다시 계산합니다. 쿼리를 다시 계산하는 과정에서 더 많은 쿼리를 재귀적으로 호출하게 될 수 있으며, 이는 의존성에 대해 재귀적으로 try_mark_green() 알고리즘으로 돌아올 수 있음을 의미합니다.

현실 세계: 영속화가 모든 것을 복잡하게 만드는 방식

위 절들에서는 증분 컴파일의 기반 알고리즘을 설명했지만, 컴파일러 프로세스는 작업을 마치면 종료되며 결과 캐시를 포함한 쿼리 컨텍스트도 함께 사라지므로, 다음 컴파일 세션이 이를 활용할 수 있도록 데이터를 디스크에 영속화해야 합니다. 이로 인해 완전히 새로운 구현상의 과제들이 생깁니다:

  • 쿼리 결과 캐시는 디스크에 저장되므로, 변경 비교에 곧바로 사용할 수 없습니다.
  • 이후의 컴파일 세션은 임의의 변경이 적용된 새 버전의 코드로 시작합니다. 전역적이고 순차적인 카운터로부터 생성되는 모든 종류의 ID와 인덱스(예: NodeId, DefId 등)가 밀려났을 수 있으며, 같은 숫자 ID와 인덱스가 새 컴파일 세션에서는 완전히 새로운 것을 가리킬 수 있으므로 디스크에 영속화된 결과를 더 이상 바로 사용할 수 없게 됩니다.
  • 디스크에 영속화하는 데에는 비용이 따르므로, 모든 사소한 정보를 컴파일 세션 사이에 실제로 캐시해서는 안 됩니다. 비용이 큰 (역)직렬화 단계를 거쳐야 하는 복잡한 것보다는 고정 크기의 단순한 데이터(plain-old-data)가 선호됩니다.

다음 절들에서는 컴파일러가 이러한 문제를 어떻게 해결하는지 설명합니다.

안정성의 문제: 컴파일 세션 사이의 간극 메우기

앞서 언급했듯이, 다양한 ID(DefId 등)는 컴파일되는 소스 코드의 내용에 따라 달라지는 방식으로 컴파일러에 의해 생성됩니다. ID 할당은 보통 결정적입니다. 즉, 완전히 같은 코드를 두 번 컴파일하면 같은 대상은 같은 ID를 갖게 됩니다. 하지만 무언가가 변경되면(예: 파일 중간에 함수가 추가되면) 어떤 것이든 이전과 같은 ID를 가진다는 보장이 없습니다.

그 결과 디스크 캐시의 데이터를 메모리에서 표현하는 것과 같은 방식으로 표현할 수 없습니다. 예를 들어 TyKind::FnDef(DefId, GenericArgsRef<'tcx>)와 같은 타입 정보를 (메모리에서처럼) 그대로 저장했는데, 새 컴파일 세션에서 그 안에 포함된 DefId가 다른 함수를 가리킨다면 문제가 생깁니다.

이 문제의 해결책은 컴파일 세션 사이에서도 유효하게 유지되는 ID의 “안정적인” 형태를 찾는 것입니다. 가장 중요한 경우인 DefId의 경우, 이것이 바로 이른바 DefPath입니다. 각 DefId에는 대응하는 DefPath가 있지만, DefPath는 숫자 ID 대신 식별된 항목까지의 경로(예: std::collections::HashMap)를 기반으로 합니다. 이러한 ID의 장점은 관련 없는 변경의 영향을 받지 않는다는 것입니다. 예를 들어, std::collections에 새 함수를 추가하더라도 std::collections::HashMap은 여전히 std::collections::HashMap입니다. DefPath는 소스 코드가 변경되어도 “안정적“이지만 DefId는 그렇지 않습니다.

또한 DefPath의 128비트 해시 값일 뿐인 DefPathHash도 있습니다. 두 가지는 동일한 정보를 담고 있으며, DefPathHash는 Copy이고 자기 완결적이어서 다루기가 더 간단하기 때문에 주로 DefPathHash를 사용합니다.

이러한 안정적인 식별자의 원칙은 디스크 캐시의 데이터가 소스 코드 변경에도 견고하도록 만드는 데 사용됩니다. DefId를 저장하는 대신 DefPathHash를 저장하며, 캐시에서 무언가를 역직렬화할 때 DefPathHash를 현재 컴파일 세션의 대응하는 DefId에 매핑합니다(이는 단순한 해시 테이블 조회일 뿐입니다).

자체 DefId를 가지지 않는 HIR 구성 요소를 식별하는 데 사용되는 HirId도 이러한 안정적인 ID 중 하나입니다. 이는 (개념적으로) DefPath와 LocalId의 쌍이며, 여기서 LocalId는 자신의 “소유자”(예: hir::Item) 내에서 무언가(예: hir::Expr)를 지역적으로 식별합니다. 소유자가 이리저리 옮겨지더라도 그 안의 LocalId는 여전히 동일합니다.

쿼리 결과의 변경 여부 확인: StableHash와 Fingerprint

빨강-초록 표시를 하려면 쿼리 결과가 이전 컴파일 세션에서의 결과와 비교하여 변경되었는지 확인해야 하는 경우가 많습니다. 하지만 여기에는 두 가지 성능 문제가 있습니다:

  • 단지 비교를 하기 위해 디스크에서 이전 결과를 불러와야 하는 일은 피하고 싶습니다. 새 결과는 이미 계산했으며 그것을 사용할 것입니다. 또한 디스크에서 결과를 불러오면 사용될 가능성이 거의 없는 데이터로 인터너가 “오염“됩니다.
  • 모든 결과를 하나하나 디스크 캐시에 저장하고 싶지는 않습니다. 예를 들어, 업스트림 크레이트에서 이미 사용할 수 있는 것을 디스크에 영속화하는 것은 헛된 노력입니다.

컴파일러는 이른바 Fingerprint를 사용하여 이러한 문제를 피합니다. 새 쿼리 결과가 계산될 때마다 쿼리 엔진은 그 결과의 128비트 해시 값을 계산합니다. 이 해시 값을 “쿼리 결과의 Fingerprint“라고 부릅니다. 해싱은 “안정적인 방식으로” 수행되며, 또 그렇게 수행되어야 합니다. 이는 컴파일 세션 사이에 변경될 수 있는 것(예: DefId)을 해싱할 때마다 그 대신 그것의 안정적인 대응물(예: 대응하는 DefPath)을 해싱한다는 뜻입니다. 이것이 바로 StableHash 인프라 전체가 존재하는 이유입니다. 이렇게 하면 서로 다른 두 컴파일 세션에서 계산된 Fingerprint도 여전히 비교할 수 있습니다.

다음 단계는 이러한 핑거프린트를 의존성 그래프와 함께 저장하는 것입니다. 핑거프린트는 복사할 바이트일 뿐이므로 이 작업은 비용이 적게 듭니다. 핑거프린트 전체 집합을 의존성 그래프와 함께 불러오는 것도 비용이 적게 듭니다.

이제 빨강-초록 표시 과정에서 결과가 변경되었는지 확인해야 하는 시점에 이르면, (이미 불러온) 이전 핑거프린트를 새 결과의 핑거프린트와 비교하기만 하면 됩니다.

이 접근 방식은 꽤 잘 작동하지만 결점이 없는 것은 아닙니다.

  • 해시 충돌이 일어날 가능성이 조금 있습니다. 즉, 서로 다른 두 결과가 같은 핑거프린트를 가질 수 있으며, 이 경우 시스템은 결과가 바뀌지 않았다고 잘못 판단하여 갱신을 놓치게 됩니다.

    저희는 품질 좋은 해시 함수와 128비트 폭의 해시 값을 사용하여 이 위험을 줄입니다. 이러한 조치 덕분에 해시 충돌의 실질적인 위험은 무시할 수 있는 수준입니다.

  • 핑거프린트 계산은 비용이 상당히 큽니다. 이것이 증분 컴파일이 비증분 컴파일보다 느릴 수 있는 주된 이유입니다. 저희는 좋은, 따라서 비용이 큰 해시 함수를 쓸 수밖에 없으며, 해싱하는 동안 대상을 안정적인 등가물로 매핑해야 합니다.

두 DepGraph 이야기: 이전 그래프와 새 그래프

앞서 의존성 추적을 처음 설명할 때는 몇 가지 세부 사항을 대충 넘어갔는데, 실제로 구현하려고 하면 이 부분들이 금세 골칫거리가 됩니다. 특히 실제로는 두 개의 의존성 그래프를 다루고 있다는 사실을 놓치기 쉽습니다. 하나는 이전 컴파일 세션에서 만든 그래프이고, 다른 하나는 현재 컴파일 세션을 위해 만들고 있는 그래프입니다.

컴파일 세션이 시작되면 컴파일러는 이전 의존성 그래프를 변경할 수 없는 데이터로 메모리에 로드합니다. 그런 다음 쿼리가 호출되면, 먼저 그래프에서 해당 노드를 초록색으로 표시하려고 시도합니다. 이는 실제로는 현재 세션의 쿼리 키에 대응하는 이전 의존성 그래프의 노드를 초록색으로 표시하려 한다는 뜻입니다. 현재 쿼리 키와 이전 DepNode 사이의 이 매핑은 어떻게 할까요? 답은 이번에도 Fingerprint입니다. 의존성 그래프의 노드는 쿼리 키의 핑거프린트로 식별됩니다. 핑거프린트는 컴파일 세션이 바뀌어도 안정적이므로, 현재 세션에서 핑거프린트를 계산하면 이전 세션의 의존성 그래프에서 노드를 찾을 수 있습니다. 주어진 핑거프린트를 가진 노드를 찾지 못했다면, 그 쿼리 키가 이전 세션에는 아직 존재하지 않았던 무언가를 가리킨다는 뜻입니다.

이렇게 이전 의존성 그래프에서 dep-node를 찾았으면, 그 의존성(즉, 역시 이전 그래프에 있는 dep-node)을 조회하고 try-mark-green 알고리즘의 나머지를 계속 진행할 수 있습니다. 다음으로 흥미로운 일은 노드를 초록색으로 표시하는 데 성공했을 때 일어납니다. 이 시점에서 노드와 그 노드의 의존성으로 이어지는 간선을 이전 그래프에서 새 그래프로 복사합니다. 새 의존성 그래프는 일반적인 의존성 추적으로는 이 노드와 간선을 얻을 수 없기 때문에 이렇게 해야 합니다. 추적 시스템은 실제로 쿼리를 실행하는 동안에만 간선을 기록할 수 있습니다. 하지만 결과가 이미 캐시되어 있는데도 쿼리를 실행하는 것이야말로 저희가 피하고 싶은 일입니다.

컴파일 세션이 끝나면, 변경되지 않은 부분은 모두 이전 의존성 그래프에서 새 그래프로 복사되어 있고, 변경된 부분은 추적 시스템에 의해 새 그래프에 추가되어 있습니다. 이 시점에서 새 그래프는 쿼리 결과 캐시와 함께 디스크에 직렬화되며, 이후 컴파일 세션에서 이전 의존성 그래프 역할을 할 수 있습니다.

뭔가 잊지 않으셨습니까?: 캐시 승격

지금까지 설명한 시스템에는 다소 미묘한 속성이 있습니다. dep-node의 모든 입력이 green이면, 해당 쿼리 결과를 계산하거나 로드하지 않고도 dep-node 자체를 green으로 표시할 수 있다는 것입니다. 이 속성을 추이적으로 적용하다 보면, 다음 예와 같이 일부 중간 결과가 실제로는 디스크에서 한 번도 로드되지 않는 상황이 자주 생깁니다.

   input(A) <-- intermediate_query(B) <-- leaf_query(C)

컴파일러는 어떤 출력 산출물을 생성하기 위해 leaf_query(C)의 값이 필요할 수 있습니다. leaf_query(C)를 초록색으로 표시할 수 있다면, 컴파일러는 디스크 캐시에서 그 결과를 로드합니다. 하지만 intermediate_query(B)의 결과는 한 번도 로드되지 않습니다. 그 결과, 컴파일러가 메모리에 있는 모든 쿼리 결과를 디스크에 기록하여 새 결과 캐시를 저장할 때 intermediate_query(B)는 메모리에 없으므로 새 결과 캐시에서 빠지게 됩니다.

이후에 intermediate_query(B)의 결과가 실제로 필요한 컴파일 세션이 또 있다면, 바로 직전까지 캐시에 완전히 유효한 결과가 있었는데도 그 결과를 다시 계산해야 합니다.

이런 일을 막기 위해 컴파일러는 “캐시 승격(cache promotion)“이라는 작업을 수행합니다. 새 결과 캐시를 내보내기 전에 모든 초록색 dep-node를 순회하면서 각 노드의 쿼리 결과가 메모리에 로드되어 있는지 확인합니다. 이렇게 하면 결과 캐시가 불필요하게 다시 줄어들지 않습니다.

증분 컴파일과 컴파일러 백엔드

LLVM이 관여하는 부분인 컴파일러 백엔드는 쿼리 시스템을 사용하지만, 백엔드 자체는 쿼리로 구현되어 있지 않습니다. 따라서 백엔드는 의존성 추적에 자동으로 참여하지 않습니다. 하지만 추적 시스템과 수동으로 통합하는 방법은 꽤 간단합니다. 컴파일러는 각 코드 생성 단위(CGU)의 초기 LLVM 버전을 생성할 때 어떤 쿼리가 호출되는지 추적하기만 하며, 그 결과 CGU마다 dep-node가 하나씩 생깁니다. 그런 다음 이후의 컴파일 세션에서 CGU의 dep-node를 초록색으로 표시하려고 시도합니다. 성공하면 디스크에 있는 해당 오브젝트 파일과 비트코드 파일이 여전히 유효하다는 것을 알 수 있습니다. 성공하지 못하면 CGU 전체를 다시 컴파일해야 합니다.

이는 일반 쿼리에 사용되는 것과 같은 접근 방식입니다. 주요 차이점은 다음과 같습니다.

  • LLVM 모듈은 불투명한 C++ 객체이기 때문에 핑거프린트를 쉽게 계산할 수 없다는 점,

  • 여기서는 공통 결과 캐시 파일에 든 직렬화된 Rust 값 대신 비트코드 파일과 오브젝트 파일을 다루므로, 캐시된 값을 처리하는 로직이 일반 쿼리와 상당히 다르다는 점,

  • LLVM 관련 작업은 계산 시간과 메모리 소비 측면에서 비용이 매우 크기 때문에, 무엇을 언제 실행하고 무엇을 얼마나 오래 메모리에 유지할지를 엄격하게 제어해야 한다는 점입니다.

위의 모든 사항을 처리할 수 있는 범용 메커니즘으로 쿼리 시스템을 확장할 수도 있겠지만, 지금까지는 그로 인해 얻는 것보다 드는 수고가 더 클 것으로 보였습니다.

쿼리 수정자

FIXME: rustc_middle::query::modifiers를 쿼리 수정자 문서의 본거지로 삼고, 다른 유용한 수정자 문서가 여전히 정확한지 확인한 뒤 모두 그곳으로 옮기십시오.

쿼리 시스템에서는 쿼리에 수정자를 적용할 수 있습니다. 이러한 수정자는 증분 컴파일과 관련하여 시스템이 쿼리를 다루는 방식의 특정 측면에 영향을 줍니다.

  • eval_always - eval_always 속성이 있는 쿼리는 증분 컴파일 중에 무조건 다시 실행됩니다. 즉, 시스템은 그 쿼리의 dep-node를 초록색으로 표시하려고 시도조차 하지 않습니다. 이 속성의 용도는 두 가지입니다.

    • eval_always 쿼리는 파일, 전역 상태 등에서 입력을 읽을 수 있습니다. 또한 파일에 쓰기, 전역 상태 변경 같은 부수 효과를 일으킬 수도 있습니다.

    • 어떤 쿼리는 결과가 소스 코드 전체에 의존하기 때문에 다시 평가될 가능성이 매우 높습니다. 이 경우 시스템이 애초에 의존성 기록을 건너뛸 수 있으므로 eval_always를 최적화 수단으로 사용할 수 있습니다.

  • no_force - 쿼리의 키 타입이 복원 가능하더라도 이 쿼리의 dep 노드를 절대 “강제(force)“하지 않습니다.

  • no_hash - 쿼리에 no_hash를 적용하면 시스템이 쿼리 결과의 핑거프린트를 계산하지 않습니다. 이로 인해 두 가지 결과가 생깁니다.

    • 핑거프린트 계산은 특히 크고 복잡한 값에서 비용이 크기 때문에, 이를 계산하지 않으면 시간을 상당히 절약할 수 있습니다.

    • 핑거프린트가 없으면 시스템은 쿼리 결과가 변경되었다고 무조건 가정해야 합니다. 따라서 no_hash 쿼리에 의존하는 것은 모두 항상 다시 실행됩니다.

    쿼리에 no_hash를 사용하는 것은 두 가지 경우에 의미가 있습니다.

    • 첫째, 쿼리의 입력 중 하나가 변경될 때마다 결과도 변경될 가능성이 매우 높은 경우입니다. 예를 들어 |a, b, c| -> (a * b * c)와 같은 함수가 이에 해당합니다. 이런 경우 입력 중 하나가 빨간색이면 쿼리를 다시 계산해도 항상 빨간색 노드가 나오므로, 그 수고를 덜고 곧바로 빨간색으로 간주해도 됩니다. 반례로는 |a| -> (a == 42)와 같은 함수를 들 수 있습니다. 이 함수는 a가 변경되더라도 대부분의 경우 결과가 변하지 않습니다.

    • 둘째, 쿼리 결과가 크고 단일한(monolithic) 컬렉션(예: index_hir)이고, 그 컬렉션에서 값을 읽어 오는 “프로젝션 쿼리”(예: hir_owner)가 있는 경우입니다. 이런 경우 큰 컬렉션은 위의 조건을 충족할 가능성이 높으며(입력이 하나라도 변경되면 컬렉션 전체를 다시 계산해야 함), 프로젝션 쿼리의 결과는 어차피 해시됩니다. 컬렉션 쿼리까지 해시한다면 사실상 같은 데이터를 두 번 해시하는 셈입니다. 한 번은 컬렉션을 해시할 때, 또 한 번은 모든 프로젝션 쿼리 결과를 해시할 때입니다. no_hash를 사용하면 이러한 중복을 피할 수 있으며, 프로젝션 쿼리는 “방화벽” 역할을 하여 자신에게 의존하는 것들을 무조건 빨간색인 no_hash 노드로부터 보호합니다.

  • cache_on_disk - 쿼리의 반환 값이 디스크에 캐시되며, 해당 의존성 노드가 초록색이면 이후 세션에서 불러올 수 있습니다. separate_provide_extern 수식자도 함께 지정되어 있으면 값은 “로컬” 키에 대해서만 디스크에 캐시됩니다. 외부 크레이트의 값은 대신 크레이트 메타데이터에서 불러올 수 있어야 하기 때문입니다.

  • feedable - 이 쿼리는 실제로는 함수가 아니라 자체 아레나(arena) 타입입니다. 이는 아레나를 선언하고, 저장할 정보를 컴파일의 나중 시점(예를 들어 실제로 Crate 객체를 사용할 수 있게 되었을 때)에 “공급(feed)“한 다음, 다른 크레이트와 마찬가지로 가져오기 위한 것입니다. 따라서 이러한 쿼리에 대한 함수 정의는 존재하지 않습니다.

프로젝션 쿼리 패턴

흥미롭게도 eval_always와 no_hash는 이른바 “프로젝션 쿼리” 패턴에서 함께 사용될 수 있습니다. 컴파일러 입력 전체에 의존하는 쿼리 하나(예: 인덱싱된 HIR)와, 이 단일한 값에서 개별 값을 추출하는 또 다른 쿼리(예: 특정 DefId를 가진 HIR 항목)가 있는 경우가 많습니다. 이러한 프로젝션 쿼리를 사용하면 변경 전파를 막는 “방화벽“을 구축할 수 있습니다. 단일 쿼리의 결과가 변경되더라도(그럴 가능성은 매우 높습니다) 작은 프로젝션들은 대부분 여전히 초록색으로 표시될 수 있기 때문입니다.

  +------------+
  |            |           +---------------+           +--------+
  |            | <---------| projection(x) | <---------| foo(a) |
  |            |           +---------------+           +--------+
  |            |
  | monolithic |           +---------------+           +--------+
  |   query    | <---------| projection(y) | <---------| bar(b) |
  |            |           +---------------+           +--------+
  |            |
  |            |           +---------------+           +--------+
  |            | <---------| projection(z) | <---------| baz(c) |
  |            |           +---------------+           +--------+
  +------------+

monolithic_query의 결과가 변경되어 projection(x)의 결과도 변경되었다고, 즉 두 dep-node가 모두 red로 표시된다고 가정해 봅시다. 그러면 foo(a)는 다시 실행되어야 하지만, bar(b)와 baz(c)는 초록색으로 표시될 수 있습니다. 그러나 foo, bar, baz가 monolithic_query에 직접 의존했다면 이들 모두를 다시 평가해야 했을 것입니다.

이 패턴은 eval_always와 no_hash 없이도 작동하지만, 이 두 수식자를 사용하면 불필요한 오버헤드를 피할 수 있습니다. 단일 쿼리가 컴파일러 입력의 사소한 수정에도 변경될 가능성이 높다면, 이를 eval_always로 표시하여 의존성 추적 비용을 없애는 것이 합리적입니다. 또한 단일 쿼리를 no_hash로 표시하는 것은 언제나 합리적입니다. 가능한 한 많은 것을 초록색으로 유지하는 일은 프로젝션이 맡아 주기 때문입니다.

현재 시스템의 한계

아직 개선할 수 있는 점이 많습니다.

디스크 내 자료 구조의 증분성

현재 시스템은 디스크상 캐시와 의존성 그래프를 제자리에서(in-place) 갱신할 수 없습니다. 대신 컴파일 세션마다 각 파일을 통째로 다시 써야 합니다. 이로 인한 오버헤드는 전체 컴파일 시간의 몇 퍼센트 정도입니다.

불필요한 데이터 의존성

쿼리 결과로 사용되는 자료 구조는 의존성 그래프에서 엣지를 제거하는 방식으로 분해될 수 있습니다. 특히 “span” 정보는 매우 자주 바뀌므로 이를 쿼리 결과에 포함하면 그 결과를 재사용하지 못할 가능성이 높아집니다. 자세한 내용은 https://github.com/rust-lang/rust/issues/47389를 참고하십시오.