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

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

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

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

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

for : 19,620,300 ns/iter ±915,700
iter: 19,234,900 ns/iter ±657,200

for : 19,620,300 ns/iter ±915,700
iter: 19,234,900 ns/iter ±657,200

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)은 루프 제어 코드의 오버헤드를 제거하고 대신 루프의 각 순회에 해당하는 반복되는 코드를 생성하는 최적화 방법입니다.

본문에서 설명하는 최적화 결과에서는 계수를 레지스터에 보관할 수 있습니다.

그 관찰에서는 일부 배열 접근의 경계 검사도 제거되었습니다.

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

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

반복자와 클로저는 코드를 좀 더 고수준으로 보이도록 하지만, 추상화에 따른 추가 비용이 최적화로 제거될 수 있습니다. 실제 성능은 같은 작업과 설정에서 확인합니다.

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

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

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

클로저와 반복자는 추상화 때문에 생기는 추가 비용을 최적화로 제거하려는 목표로 설계됩니다. 실제 총비용과 최적화 결과는 사용한 코드와 설정에서 확인해야 합니다.

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

예시

먼저 보고값의 차이를 계산합시다. 19,620,300 - 19,234,900 = 385,400 ns이고, 루프 보고값을 기준으로 하면 약 1.96%입니다. 단순히 표시된 +/-를 더하고 빼면 루프는 18,704,600..20,536,000 ns, 반복자는 18,577,700..19,892,100 ns입니다. 두 구간은 겹칩니다. 여기서 +/-가 어떤 통계량인지 설명하지 않았으므로 이를 특정 신뢰수준의 신뢰구간이나 모든 실행의 최솟값·최댓값이라고 부르지는 않습니다.

음성 디코더의 발췌도 먼저 한 단계만 손으로 계산하면 읽기 쉽습니다. 이전 샘플을 1부터 12, 현재 차분 값을 5로 두고, 계수 열두 개를 모두 1, 오른쪽 이동량을 1로 제한합니다. 이 작은 입력은 곱·합·정수 변환·덧셈의 범위를 넘지 않습니다. 다음 전체 프로그램은 이 한 회차의 상태 변화를 보여 줍니다.

fn main() {
    let mut buffer: [i32; 13] = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 5];
    let coefficients = [1_i64; 12];
    let qlp_shift = 1_u32;
    let i = 12;
    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;
    println!("prediction={prediction}, sample={}", buffer[i]);
}

곱의 합은 78, 오른쪽 한 비트 이동 결과는 39, 기존 차분 5를 더한 새 샘플은 44이므로 예상 출력은 prediction=39, sample=44입니다. 원래 루프에서는 이 결과를 같은 buffer에 저장하므로 다음 회차의 이전 샘플 구간에 갱신한 값이 들어갑니다. 임의의 큰 입력에도 같은 안전성을 보장하는 코드는 아니며, 실제 디코더의 범위 조건과 오류 정책은 별도로 확인해야 합니다.

스스로 결론 내리기

첫째, 위 두 보고값의 차이만 보고 “반복자는 언제나 더 빠르다” 또는 “완전히 같은 성능이다”라고 결론 낼 수 있는지 설명하세요. 비교를 새로 준비한다면 결과의 내용·순서·조기 종료·할당을 맞춘 뒤 어떤 입력과 컴파일 설정을 기록할지도 적으세요. 둘째, 작은 디코더 입력의 계수를 모두 1로 유지하고 오른쪽 이동량을 0으로 바꿨을 때 새 샘플은 얼마인가요? 같은 13개 샘플의 마지막 차분을 6으로 바꾸고 이동량을 다시 1로 했을 때도 계산하세요.

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