[uv] uv의 잠금 파일 의존성 그래프 순회 최적화: 해싱에서 정수 인덱싱으로

2026년 8월 31일수정: 2026년 8월 31일

PR 링크: astral-sh/uv#21373 상태: Merged | 변경: +217 / -95

들어가며

uv는 Python 패키지 관리의 새로운 시대를 열고 있는 Rust 기반의 빠르고 현대적인 도구입니다. pip보다 훨씬 빠른 속도를 자랑하며, 특히 대규모 프로젝트의 의존성 해결 및 설치에서 그 진가를 발휘합니다. 이러한 uv의 핵심 강점은 바로 '속도'에 있으며, 이는 끊임없는 성능 최적화 노력의 결과입니다.

오늘 분석할 GitHub PR, "Use integer indices when traversing locked dependencies"는 uv의 잠금 파일(lockfile)에서 의존성 그래프를 구성하고 순회하는 과정에서 발생하는 성능 병목을 해결하기 위한 중요한 최적화입니다. 기존에는 PackageId와 같은 복합 객체를 반복적으로 해싱하여 의존성 대상을 찾고 그래프 노드를 조회했습니다. 이 과정에서 발생하는 해싱 비용은 특히 대규모 잠금 파일에서 상당한 오버헤드를 유발했습니다. 이 PR은 이러한 해싱 비용을 제거하고, 대신 정수 인덱스를 활용하여 그래프 순회 및 조회를 훨씬 빠르게 만듭니다.

코드 분석

이 PR의 핵심 변경사항은 crates/uv-resolver/src/lock/installable.rs 파일에 집중되어 있습니다. 주요 변경점은 PackageId 객체 대신 PackageIndex라는 정수 인덱스를 사용하여 데이터 구조를 관리하고 조회하는 방식입니다.

1. `inverse` 맵의 자료구조 변경

의존성 그래프를 구성할 때, PackageId를 petgraph의 NodeIndex에 매핑하는 inverse 맵은 중요한 역할을 합니다. 기존에는 PackageId를 키로 사용하는 FxHashMap을 사용했습니다.

Before:

        let mut inverse = FxHashMap::with_capacity_and_hasher(size_guess, FxBuildHasher);

FxHashMap은 빠른 해싱을 제공하지만, 여전히 키를 해싱하는 비용이 발생합니다. 이 PR에서는 PackageId 대신 PackageIndex (내부적으로 usize 래핑)를 사용하기 때문에, PackageIndex를 직접 인덱스로 활용할 수 있는 Vec으로 변경했습니다. size_guess만큼 미리 할당된 None 값으로 초기화된 Vec은 PackageIndex의 usize 값을 직접 배열의 인덱스로 사용하여 O(1) 시간에 접근할 수 있게 합니다.

After:

        let mut inverse = vec![None; size_guess];

이 변경은 PackageId를 해싱하는 오버헤드를 제거하고, PackageIndex를 통해 직접 배열에 접근함으로써 조회 속도를 크게 향상시킵니다.

2. 큐(Queue) 요소의 변경

의존성 그래프를 너비 우선 탐색(BFS) 방식으로 순회하기 위해 사용되는 queue도 PackageId 대신 PackageIndex를 사용하도록 변경되었습니다.

Before:

        let mut queue: VecDeque<(&Package, Option<&ExtraName>)> = VecDeque::new();

queue에 (&Package, Option<&ExtraName>) 튜플을 저장할 때, Package 객체 내부의 PackageId를 사용하여 seen 셋에 삽입하거나 conflict_reachability 맵에 접근했습니다. 이 과정에서 PackageId의 해싱이 반복적으로 발생했습니다.

After:

        let mut queue: VecDeque<(PackageIndex, Option<&ExtraName>)> = VecDeque::new();

이제 queue는 PackageIndex를 직접 저장하므로, 큐에서 요소를 꺼내어 처리할 때 PackageId를 다시 찾거나 해싱할 필요 없이 PackageIndex를 바로 사용할 수 있습니다.

3. `reachability` 맵의 키 변경

conflict_reachability 맵은 특정 패키지 및 엑스트라의 도달 가능성(reachability)을 추적합니다. 이 맵의 키도 PackageId에서 PackageIndex로 변경되었습니다.

Before:

fn add_reachability<'lock>(
    reachability: &mut FxHashMap<(&'lock PackageId, Option<&'lock ExtraName>), UniversalMarker>,
    key: (&'lock PackageId, Option<&'lock ExtraName>),
    marker: UniversalMarker,
) -> bool {

After:

fn add_reachability<'lock>(
    reachability: &mut FxHashMap<(PackageIndex, Option<&'lock ExtraName>), UniversalMarker>,
    key: (PackageIndex, Option<&'lock ExtraName>),
    marker: UniversalMarker,
) -> bool {

이 변화는 add_reachability 함수 내부에서 reachability 맵에 접근할 때 PackageId 해싱 대신 PackageIndex를 사용하여 더 효율적인 조회를 가능하게 합니다.

4. 그래프 노드 삽입 및 조회 로직 변경

가장 중요한 변경점 중 하나는 그래프에 노드를 추가하고 기존 노드를 조회하는 방식입니다. inverse 맵을 Vec으로 변경함에 따라, PackageId를 키로 사용하는 entry API 호출 대신 PackageIndex를 직접 인덱스로 사용하게 됩니다.

Before (노드 삽입):

            inverse.insert(&dist.id, index);

After (노드 삽입):

            let package_index = self.lock().by_id[&dist.id];
            inverse[package_index.0] = Some(index);

Before (노드 조회):

                let dep_index = match inverse.entry(&dep.package_id) {
                    Entry::Vacant(entry) => {
                        // ... 노드 추가 ...
                        entry.insert(index);
                        index
                    }
                    Entry::Occupied(entry) => {
                        let index = *entry.get();
                        // ... 기존 노드 처리 ...
                        index
                    }
                };

After (노드 조회):

                let dep_dist = &self.lock().packages[dep.index.0];
                let dep_index = match inverse[dep.index.0] {
                    None => {
                        // ... 노드 추가 ...
                        inverse[dep.index.0] = Some(index);
                        index
                    }
                    Some(index) => {
                        // ... 기존 노드 처리 ...
                        index
                    }
                };

self.lock().by_id[&dist.id]를 통해 PackageId로부터 PackageIndex를 한 번만 얻은 후, 이후 모든 작업에서 이 PackageIndex의 usize 값을 직접 배열 인덱스로 사용합니다. 이는 FxHashMap의 entry API를 사용하는 것보다 훨씬 빠릅니다. PackageIndex는 uv-resolver 내부에서 pub(crate) struct PackageIndex(pub(crate) usize);와 같이 정의되어 usize를 래핑하는 타입으로, 배열 인덱스로 사용하기에 적합합니다.

왜 이게 좋은가

이 최적화는 uv의 핵심 가치인 '속도'를 직접적으로 향상시키는 매우 효과적인 변경입니다.

1. 성능 개선

PR 설명에 따르면, 이 변경으로 인해 의존성 그래프 변환 시간이 크게 단축되었습니다.

Lock	Baseline	This PR	Time reduction
Jupyter	0.316 ms	0.272 ms	13.9%
Synthetic 1,000-package DAG	3.381 ms	2.452 ms	27.5%
Synthetic 5,000-package DAG	41.601 ms	36.624 ms	12.0%

대규모 프로젝트에서도 유사한 개선이 관찰되었습니다.

Project	Lock entries	Baseline	This PR	Time reduction
Airflow 2.9.3, all extras	585	1.741 ms	1.374 ms	21.1%
Home Assistant 2025.1.4, all integrations	1,456	5.017 ms	4.149 ms	17.3%

이러한 수치는 PackageId 해싱 비용이 상당한 병목이었음을 명확히 보여줍니다. 해싱 기반 조회(평균 O(1)이지만 상수 인자가 큼)를 직접적인 배열 인덱싱(O(1)이며 상수 인자가 매우 작음)으로 대체함으로써, 특히 의존성 그래프가 커질수록 그 효과가 증폭됩니다.

2. 메모리 효율성

PR 설명에 따르면, 이 변경은 각 의존성마다 하나의 캐시된 usize를 추가하지만, 전체 프로세스의 RSS(Resident Set Size)는 거의 변동이 없었습니다. 이는 성능 개선을 달성하면서도 메모리 오버헤드를 최소화했음을 의미합니다.

3. 일반적 교훈

이 최적화는 소프트웨어 엔지니어링에서 중요한 일반적 교훈을 제공합니다.

해싱 비용의 재평가: 해시 테이블은 평균적으로 O(1)의 빠른 조회를 제공하지만, 키의 해싱 비용 자체가 무시할 수 없는 경우, 특히 반복적인 작업에서는 상당한 오버헤드가 될 수 있습니다.
정수 인덱싱의 힘: 고유한 정수 ID를 할당할 수 있는 객체 집합이 있고, 이 ID가 비교적 조밀하게 분포되어 있다면, Vec이나 배열을 사용하여 직접 인덱싱하는 것이 해시 테이블보다 훨씬 빠르고 효율적입니다. 이는 캐시 효율성 측면에서도 유리합니다.
데이터 구조 선택의 중요성: 특정 사용 패턴에 가장 적합한 데이터 구조를 선택하는 것이 성능 최적화의 핵심입니다. 이 경우, PackageId를 PackageIndex로 매핑하는 사전 처리 단계를 통해 이후의 모든 그래프 순회 작업에서 최적의 성능을 얻을 수 있었습니다.

4. 리뷰 피드백 반영

초기 PR에서는 Jupyter와 Synthetic DAG에 대한 벤치마크만 포함되어 있었습니다. 리뷰어 konstin은 Airflow와 Home Assistant와 같은 더 큰 실제 프로젝트에 대한 벤치마크를 요청했습니다. 이러한 피드백은 PR에 반영되어, 더 광범위한 시나리오에서 이 최적화의 효과를 입증하는 데 기여했습니다. 이는 실제 환경에서의 성능 검증이 얼마나 중요한지를 보여주는 좋은 예시입니다.

마치며

uv의 "Use integer indices when traversing locked dependencies" PR은 마이크로 최적화가 전체 시스템 성능에 얼마나 큰 영향을 미칠 수 있는지 보여주는 훌륭한 사례입니다. PackageId의 반복적인 해싱 비용을 PackageIndex를 활용한 직접적인 배열 인덱싱으로 대체함으로써, uv는 잠금 파일 처리 속도를 더욱 향상시켰습니다. 이러한 세심한 최적화 노력 덕분에 uv는 Python 생태계에서 가장 빠른 패키지 관리 도구 중 하나로 자리매김하고 있습니다. 우리도 개발 과정에서 반복되는 작업의 성능 병목을 식별하고, 적절한 데이터 구조와 알고리즘 선택을 통해 유사한 최적화 기회를 찾아볼 수 있을 것입니다.

참고 자료

⚠️ 알림: 이 분석은 AI가 실제 코드 diff를 기반으로 작성했습니다.

PR Analysis 의 다른글

이전글 [uv] macOS에서 uv 캐시 정리가 3.8배 빨라진 비결: getattrlistbulk를 활용한 일괄 메타데이터 조회
현재글 : [uv] uv의 잠금 파일 의존성 그래프 순회 최적화: 해싱에서 정수 인덱싱으로
다음글 [flashinfer] FlashInfer SM12x MoE 최적화: 정적 MoE 경로 통합 및 성능 향상

[uv] uv의 잠금 파일 의존성 그래프 순회 최적화: 해싱에서 정수 인덱싱으로

들어가며

코드 분석

1. `inverse` 맵의 자료구조 변경

2. 큐(Queue) 요소의 변경

3. `reachability` 맵의 키 변경

4. 그래프 노드 삽입 및 조회 로직 변경

왜 이게 좋은가

1. 성능 개선

2. 메모리 효율성

3. 일반적 교훈

4. 리뷰 피드백 반영

마치며

참고 자료

댓글

관련 포스트

PR Analysis 의 다른글