성능 비교하기: 루프 vs. 반복자 | Rust

루프와 반복자 중 무엇을 사용할지 결정하기 위해서는 어떤 쪽에 더 빠른지 알 필요가 있습니다.

명시적으로 for 루프를 사용한 search 함수 버전과 반복자 버전 중 말이지요.

여기서는 아서 코난 도일이 쓴 셜록 홈스의 모험의 전체 내용을 로딩하고 내용 중에 the를 찾는 벤치마크를 돌렸습니다.

아래에 루프를 사용한 search 버전과 반복자를 사용한 버전에 대한 벤치마크 결과가 있습니다.

FLOWCHART · PERFORMANCE EVIDENCE

반복자 성능 주장을 검증하는 증거 사다리

루프와 반복자의 성능 비교는 한 번의 역사적 숫자로 끝나지 않는다. 먼저 같은 일을 하는지 확인하고, release 설정과 대표 입력에서 변동성을 측정한 뒤 필요할 때만 최적화 결과를 살펴 범위가 제한된 결론을 낸다.

같은 일 확인
반환값, 조기 종료, 할당, 오류 처리가 같은지 먼저 검증한다. 일이 다르면 시간 비교도 무효입니다.
release 벤치
debug가 아니라 release 또는 bench 프로필에서 dead-code elimination을 막고 대표적인 입력 크기와 형태를 측정합니다.
불확실성 보기
여러 번 측정한 분포와 오차가 겹치면 역사적 한 수치의 2% 차이로 승자를 선언하지 않습니다.
최적화 근거
인라이닝·루프 융합·언롤링·bounds-check 제거는 코드 형태, 설정, 타깃, 컴파일러에 따라 달라집니다.
범위 제한 결론
필요할 때 IR/assembly를 보조 근거로 쓰되 특정 버전의 동일 assembly를 CI 계약으로 만들지 않고 조건을 명시합니다.

zero-cost abstraction은 매 체인이 정확히 비용 0이거나 모든 루프보다 빠르다는 정리가 아니다. 같은 작업에서 추상화 경계가 최적화될 수 있다는 설계 목표와 관찰을 구분한다.

test bench_search_for  ... bench:  19,620,300 ns/iter (+/- 915,700)
test bench_search_iter ... bench:  19,234,900 ns/iter (+/- 657,200)

반복자 버전이 약간 더 빨랐군요!

여기서는 벤치마크 코드에 대해 설명하진 않을 것인데, 왜냐하면 여기에서의 핵심은 두 버전이 동등하다는 것을 증명하는 것이 아니고, 두 구현이 성능 측면에서 얼마나 비교되는지에 대한 일반적인 감을 얻는 것이기 때문입니다.

더 종합적인 벤치마크를 위해서는 다양한 크기의 다양한 텍스트를 contents로 사용하고, 서로 다른 길이의 다양한 단어들을 query로 사용하여 모든 종류의 다른 조합으로 확인해야 합니다.

요점은 이렇습니다.

반복자는 비록 고수준의 추상화지만, 컴파일되면 대략 직접 작성한 저수준의 코드와 같은 코드 수준으로 내려갑니다.

반복자는 러스트의 비용 없는 추상화(zero-cost abstraction) 중 하나이며, 그 추상을 사용하는 것은 추가적인 런타임 오버헤드가 없다는 것을 의미합니다.

최초의 C++ 디자이너이자 구현자인 비야네 스트롭스트룹(Bjarne Stroustrup)이 ‘C++ 기초(Foundations of C++, 2012)’에서 제로 오버헤드(zero-overhead) 를 정의한 것과 유사합니다.

일반적으로 C++ 구현은 제로 오버헤드 원칙을 준수합니다. 사용하지 않는 것에 대해서는 비용을 지불하지 않습니다. 그리고 더 나아가서, 사용한다면 이보다 더 나은 코드를 수작업으로 만들 수 없습니다.

또 다른 예로, 다음 코드는 오디오 디코더에서 가져왔습니다.

디코딩 알고리즘은 선형 예측이라는 수학적 연산을 사용하여 이전 샘플의 선형 함수에 기반해서 미래의 값을 추정합니다.

이 코드는 반복자 체인을 사용해서 스코프에 있는 세 개의 변수로 수학 연산을 합니다.

데이터의 buffer 슬라이스, 12개의 coefficients 배열, 그리고 데이터를 쉬프트 하기 위한 qlp_shift 값으로 말이죠.

이 예제에서는 변수를 선언했지만 값을 주지는 않았습니다; 비록 이 코드가 컨텍스트 밖에서는 큰 의미 없지만, 러스트가 어떻게 고수준의 개념을 저수준의 코드로 변환하는지에 대한 간결하고 실질적인 예제입니다.

let buffer: &mut [i32];
let coefficients: [i64; 12];
let qlp_shift: i16;

for i in 12..buffer.len() {
    let prediction = coefficients.iter()
                                 .zip(&buffer[i - 12..i])
                                 .map(|(&c, &s)| c * s as i64)
                                 .sum::<i64>() >> qlp_shift;
    let delta = buffer[i];
    buffer[i] = prediction as i32 + delta;
}

prediction의 값을 계산하기 위해서, 이 코드는 coefficients에 있는 12개의 값을 순회하면서 zip 메서드를 사용하여 각 계수와 buffer의 이전 12개의 값 간의 쌍을 만듭니다.

그런 다음, 각 쌍의 값을 서로 곱하고, 모든 결과를 더한 다음, 더한 값의 비트를 qlp_shift 비트만큼 우측으로 쉬프트합니다.

오디오 디코더와 같은 애플리케이션에서의 계산은 종종 성능에 가장 높은 우선순위를 둡니다.

여기서는 반복자를 만들고, 두 개의 어댑터를 사용하고, 값을 소비하고 있습니다.

이 러스트 코드가 컴파일되면 어떤 어셈블리 코드가 될까요?

글쎄요, 이 글을 쓰는 시점에서는 직접 손으로 작성한 것과 같은 어셈블리 코드로 컴파일됩니다.

coefficients의 값들을 순회하기 위해 동반되는 어떠한 루프도 없습니다.

러스트는 12번의 반복이 있다는 것을 알고 있으므로, 루프를 ‘풀어(unrolls)’ 놓습니다.

언롤링(unrolling) 은 루프 제어 코드의 오버헤드를 제거하고 대신 루프의 각 순회에 해당하는 반복되는 코드를 생성하는 최적화 방법입니다.

모든 계수는 레지스터에 저장되어 값에 대한 접근 속도가 매우 빠릅니다.

런타임에 배열 접근에 대한 경계 검사가 없습니다.

러스트가 적용할 수 있는 이러한 모든 최적화들은 결과적으로 코드를 매우 효율적으로 만듭니다.

이제 이 사실을 알게 되었으니, 반복자와 클로저를 무서워하지 않고 사용할 수 있습니다!

반복자와 클로저는 코드를 좀 더 고수준으로 보이도록 하지만, 런타임 성능에 불이익을 주지 않습니다.

비용 없는 추상화라는 말은 믿음이 아니라 확인 가능한 최적화 흐름입니다.

클로저와 반복자는 함수형 프로그래밍 아이디어에서 영감을 받은 러스트의 기능들입니다.

이들은 고수준의 개념을 저수준의 성능으로 명확하게 표현해 주는 러스트의 능력에 기여하고 있습니다.

클로저와 반복자의 구현은 런타임 성능에 영향을 미치지 않도록 설계 되었습니다.

이는 비용 없는 추상화를 제공하기 위해 노력하는 러스트의 목표 중 하나입니다.

이제 I/O 프로젝트의 표현력을 개선했으니, 이런 프로젝트를 세상과 공유하는 데 도움을 줄 cargo의 기능들을 몇 가지 살펴봅시다.