Rust에서 대소문자를 구분하지 않는 문자열 정렬 방식을 벤치마크하며 `sort_by_cached_key`, 반복자 기반 소문자화, 그리고 `unicase`의 성능을 비교한 글입니다.
2026년 3월 20일
최근에 텍스트를 정렬하기 위해 .to_lowercase()를 사용하는 코드 조각이 있었습니다. 이 방법은 메모리를 조금 사용합니다. 장점이라면, 그 코드는 .sort_by_cached_key를 사용하고 있었는데, 꽤 멋진 기능입니다. 하지만 많은 문자열에서는 처음 몇 글자만 봐도 이미 서로 다르다는 점을 생각하면, 각 항목마다 String을 할당하는 대신 .to_lowercase()를 n번이 아니라 log(n)번 수행하는 편이 더 느릴지 궁금해졌습니다.
먼저 Rust에서 두 &str를 대소문자 구분 없이 비교하는 일은 가능하긴 하지만, 약간은 우회적입니다. 여기서의 해법은 모든 char를 순회한 다음, 각각에 char::to_lowercase를 호출하는 것입니다. 그러면 다시 char에 대한 또 다른 반복자가 반환되는데, 이는 어떤 문자는 소문자로 바뀔 때 여러 문자에 대응할 수 있기 때문이며, 이를 flat_map할 수 있습니다. 퍼즐의 두 번째 조각은 Iterator에 cmp 메서드는 있지만 Ord를 구현하지는 않는다는 점입니다. 멱등적이지 않기 때문입니다. cmp를 호출하면 반복자가 소진되기 때문입니다. 그래도 sort_by를 사용하면 소문자 변환과 비교를 서로 엮어서 수행할 수 있습니다.
비교를 위해 unicase 크레이트도 벤치마크에 추가했습니다.
저는 원래 궁금한 건 직접 확인해보는 사람이라, 자연스럽게 벤치마크를 작성했습니다. 여기에 다시 실을 수 있을 정도로 짧으니 그대로 옮겨봅니다(관심 없으시면 결론으로 내려가세요):
use fake::faker::name::raw::Name;
use fake::{locales::EN, Fake};
fn setup(num: usize) -> Vec<String> {
(0..num).map(|_| Name(EN).fake()).collect::<Vec<String>>()
}
#[divan::bench(args = [1, 5, 10, 100, 1000, 10000])]
fn sort_by_cached_lowercase(bencher: divan::Bencher, size: usize) {
let names = setup(size);
bencher.counter(size).bench_local(|| {
let mut sorted = names.clone();
sorted.sort_by_cached_key(|name| name.to_lowercase());
sorted
})
}
#[divan::bench(args = [1, 5, 10, 100, 1000, 10000])]
fn sort_by_iter_lowercase(bencher: divan::Bencher, size: usize) {
let names = setup(size);
bencher.counter(size).bench_local(|| {
let mut sorted = names.clone();
fn caseless(s: &String) -> impl Iterator<Item = char> + '_ {
s.chars().flat_map(char::to_lowercase)
}
sorted.sort_by(|s1, s2| caseless(s1).cmp(caseless(s2)));
sorted
})
}
#[divan::bench(args = [1, 5, 10, 100, 1000, 10000])]
fn sort_by_unicase(bencher: divan::Bencher, size: usize) {
let names = setup(size);
bencher.counter(size).bench_local(|| {
let mut sorted = names.clone();
sorted.sort_by(|s1, s2| unicase::UniCase::new(s1).cmp(&unicase::UniCase::new(s2)));
sorted
})
}
fn main() {
// Run registered benchmarks.
divan::main();
}
제 M2-MAX MacBook Pro에서의 결과는 다음과 같습니다:
Timer precision: 41 ns
low fastest │ slowest │ median │ mean │ samples │ iters
├─ sort_by_cached_lowercase │ │ │ │ │
│ ├─ 1 16.68 ns │ 18.14 ns │ 17.49 ns │ 17.49 ns │ 100 │ 25600
│ │ 59.94 Mitem/s │ 55.1 Mitem/s │ 57.15 Mitem/s │ 57.15 Mitem/s │ │
│ ├─ 5 212.9 ns │ 265 ns │ 215.5 ns │ 219.2 ns │ 100 │ 3200
│ │ 23.47 Mitem/s │ 18.86 Mitem/s │ 23.19 Mitem/s │ 22.8 Mitem/s │ │
│ ├─ 10 452.5 ns │ 567.1 ns │ 457.7 ns │ 462.2 ns │ 100 │ 1600
│ │ 22.09 Mitem/s │ 17.63 Mitem/s │ 21.84 Mitem/s │ 21.63 Mitem/s │ │
│ ├─ 100 5.207 µs │ 11.33 µs │ 5.291 µs │ 5.455 µs │ 100 │ 100
│ │ 19.2 Mitem/s │ 8.824 Mitem/s │ 18.89 Mitem/s │ 18.32 Mitem/s │ │
│ ├─ 1000 73.62 µs │ 110.9 µs │ 75.99 µs │ 78.89 µs │ 100 │ 100
│ │ 13.58 Mitem/s │ 9.009 Mitem/s │ 13.15 Mitem/s │ 12.67 Mitem/s │ │
│ ╰─ 10000 853.7 µs │ 1.053 ms │ 864.8 µs │ 886.3 µs │ 100 │ 100
│ 11.71 Mitem/s │ 9.495 Mitem/s │ 11.56 Mitem/s │ 11.28 Mitem/s │ │
├─ sort_by_iter_lowercase │ │ │ │ │
│ ├─ 1 13.91 ns │ 23.35 ns │ 14.89 ns │ 15.68 ns │ 100 │ 25600
│ │ 71.87 Mitem/s │ 42.81 Mitem/s │ 67.15 Mitem/s │ 63.76 Mitem/s │ │
│ ├─ 5 134.8 ns │ 196 ns │ 137.4 ns │ 148.6 ns │ 100 │ 3200
│ │ 37.08 Mitem/s │ 25.5 Mitem/s │ 36.37 Mitem/s │ 33.64 Mitem/s │ │
│ ├─ 10 442.1 ns │ 1.03 µs │ 483.8 ns │ 519.1 ns │ 100 │ 800
│ │ 22.61 Mitem/s │ 9.702 Mitem/s │ 20.66 Mitem/s │ 19.26 Mitem/s │ │
│ ├─ 100 17.33 µs │ 34.12 µs │ 18.16 µs │ 19.66 µs │ 100 │ 100
│ │ 5.769 Mitem/s │ 2.93 Mitem/s │ 5.504 Mitem/s │ 5.086 Mitem/s │ │
│ ├─ 1000 337.6 µs │ 433 µs │ 352.1 µs │ 355.4 µs │ 100 │ 100
│ │ 2.961 Mitem/s │ 2.309 Mitem/s │ 2.839 Mitem/s │ 2.813 Mitem/s │ │
│ ╰─ 10000 5.543 ms │ 6.579 ms │ 5.572 ms │ 5.602 ms │ 100 │ 100
│ 1.803 Mitem/s │ 1.519 Mitem/s │ 1.794 Mitem/s │ 1.784 Mitem/s │ │
╰─ sort_by_unicase │ │ │ │ │
├─ 1 15.05 ns │ 22.05 ns │ 15.87 ns │ 16.78 ns │ 100 │ 25600
│ 66.42 Mitem/s │ 45.34 Mitem/s │ 63 Mitem/s │ 59.59 Mitem/s │ │
├─ 5 86.66 ns │ 125 ns │ 91.86 ns │ 97.79 ns │ 100 │ 6400
│ 57.69 Mitem/s │ 39.97 Mitem/s │ 54.42 Mitem/s │ 51.12 Mitem/s │ │
├─ 10 202.5 ns │ 470.8 ns │ 207.7 ns │ 230.9 ns │ 100 │ 1600
│ 49.36 Mitem/s │ 21.24 Mitem/s │ 48.13 Mitem/s │ 43.3 Mitem/s │ │
├─ 100 4.749 µs │ 18.33 µs │ 4.833 µs │ 5.201 µs │ 100 │ 100
│ 21.05 Mitem/s │ 5.454 Mitem/s │ 20.68 Mitem/s │ 19.22 Mitem/s │ │
├─ 1000 107.2 µs │ 158 µs │ 107.5 µs │ 111.4 µs │ 100 │ 100
│ 9.327 Mitem/s │ 6.325 Mitem/s │ 9.298 Mitem/s │ 8.973 Mitem/s │ │
╰─ 10000 1.753 ms │ 1.919 ms │ 1.757 ms │ 1.772 ms │ 100 │ 100
5.702 Mitem/s │ 5.208 Mitem/s │ 5.688 Mitem/s │ 5.641 Mitem/s │ │
그러니 원소가 하나뿐인 경우(자명한 경우)가 아니라면 sort_by_cached_key는 그만한 가치가 있습니다. 그리고 UTF-8 문자를 순회하면서 대소문자 변환을 수행하는 방식은 제가 생각했던 것보다 훨씬 느려서, 할당이 필요 없다는 이점을 완전히 묻어버립니다. 진짜 놀라운 점은 비교를 더 복잡하게 만들었는데도 Unicase가 종종 더 빠를 수 있다는 것입니다.