[uv] uv의 성능 최적화: BTreeSet에서 Vec으로의 전환을 통한 site-packages 스캔 오버헤드 개선

PR 링크: astral-sh/uv#20087 상태: Merged | 변경: +61 / -25

들어가며

Python 패키지 관리자 uv는 압도적인 속도로 많은 개발자에게 사랑받고 있습니다. 하지만 성능 최적화는 끝이 없는 여정입니다. 이번에 살펴볼 PR은 SitePackages::from_interpreter 메서드에서 발생하는 불필요한 메모리 할당 오버헤드를 줄이는 최적화입니다. 기존에는 site-packages 디렉토리를 스캔할 때 BTreeSet을 사용하여 경로를 정렬하고 저장했으나, 이를 Vec으로 변경하여 성능을 개선했습니다.

코드 분석

crates/uv-installer/src/site_packages.rs 변경 사항

기존 코드에서는 read_dir을 통해 가져온 파일 경로들을 BTreeSet에 삽입하며 자동으로 정렬을 수행했습니다. 하지만 BTreeSet은 삽입할 때마다 트리 구조를 유지하기 위한 힙 할당과 포인터 조작이 발생합니다.

Before:

let dist_likes: BTreeSet<_> = read_dir
    .filter_map(|read_dir| { ... })
    .collect::<Result<_, std::io::Error>>()?;

After:

let mut paths = read_dir
    .filter_map(|read_dir| { ... })
    .collect::<Result<Vec<_>, std::io::Error>>()?;
paths.sort_unstable();
Ok(paths)

핵심 변경은 BTreeSet을 Vec으로 교체하고, collect 이후에 sort_unstable()을 호출하는 것입니다. BTreeSet은 요소를 삽입할 때마다 O(log N)의 비용이 발생하지만, Vec에 데이터를 모은 뒤 sort_unstable()을 사용하면 O(N log N)의 효율적인 정렬이 가능합니다. 특히 sort_unstable은 메모리 할당을 추가로 요구하지 않으며, 정렬 시 동일한 값의 순서가 보장될 필요가 없는 경우 가장 빠른 정렬 알고리즘 중 하나입니다.

왜 이게 좋은가

1. 메모리 할당 오버헤드 감소: BTreeSet은 노드 단위로 메모리를 할당하므로, 많은 패키지가 설치된 환경에서는 수많은 작은 할당이 발생합니다. Vec은 연속된 메모리 공간을 사용하므로 할당 횟수가 획기적으로 줄어듭니다.
2. 캐시 지역성(Cache Locality): Vec은 데이터를 메모리에 연속적으로 배치하므로, CPU 캐시 효율이 BTreeSet의 트리 구조보다 훨씬 높습니다.
3. 결정론적 동작 유지: read_dir은 플랫폼마다 순서가 보장되지 않지만, sort_unstable()을 명시적으로 호출함으로써 기존과 동일하게 결정론적인 결과를 보장합니다.

이러한 최적화는 대규모 프로젝트나 수많은 의존성을 가진 환경에서 uv가 파이썬 환경을 스캔하는 속도를 미세하게, 하지만 확실하게 향상시킵니다. 작은 최적화가 모여 uv의 빠른 속도를 지탱하는 것입니다.

결론

이번 PR은 자료구조 선택이 성능에 미치는 영향을 잘 보여줍니다. 단순히 '정렬된 집합'이 필요하다고 해서 무조건 BTreeSet을 사용하는 것이 정답은 아닙니다. 데이터의 양이 적거나, 한 번에 데이터를 수집한 뒤 정렬하는 패턴이라면 Vec과 sort_unstable의 조합이 훨씬 효율적일 수 있습니다.

참고 자료

• https://doc.rust-lang.org/std/collections/struct.BTreeSet.html
• https://doc.rust-lang.org/std/vec/struct.Vec.html
• https://doc.rust-lang.org/std/primitive.slice.html#method.sort_unstable

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