arrays - 240 개 이상의 요소가있는 어레이를 반복 할 때 성능에 큰 영향을 미치는 이유는 무엇입니까?




performance rust (2)

Rust에서 어레이에 대해 합 루프를 실행할 때 CAPACITY > = 240 일 때 성능이 크게 저하되는 것을 발견했습니다. CAPACITY = 239가 약 80 배 빠릅니다.

Rust가 "짧은"배열에 대해 수행하는 특수 컴파일 최적화가 있습니까?

rustc -C opt-level=3 컴파일되었습니다.

use std::time::Instant;

const CAPACITY: usize = 240;
const IN_LOOPS: usize = 500000;

fn main() {
    let mut arr = [0; CAPACITY];
    for i in 0..CAPACITY {
        arr[i] = i;
    }
    let mut sum = 0;
    let now = Instant::now();
    for _ in 0..IN_LOOPS {
        let mut s = 0;
        for i in 0..arr.len() {
            s += arr[i];
        }
        sum += s;
    }
    println!("sum:{} time:{:?}", sum, now.elapsed());
}

Lukas의 답변 외에도 반복자를 사용하려면 다음을 시도하십시오.

const CAPACITY: usize = 240;
const IN_LOOPS: usize = 500000;

pub fn bar() -> usize {
    (0..CAPACITY).sum::<usize>() * IN_LOOPS
}

범위 패턴에 대한 제안에 대해 @Chris Morgan에게 감사드립니다.

최적화 된 어셈블리 는 매우 좋습니다 :

example::bar:
        movabs  rax, 14340000000
        ret

요약 : 240 이하에서 LLVM은 내부 루프를 완전히 풀고 반복 루프를 최적화하여 벤치 마크를 깨뜨릴 수 있음을 알 수 있습니다.


LLVM이 특정 최적화 수행을 중지하는 마법 임계 값을 찾았습니다 . 임계 값은 8 바이트 * 240 = 1920 바이트입니다 (배열은 사용 배열이므로 x86-64 CPU를 가정 할 때 길이에 8 바이트가 곱해집니다). 이 벤치 마크에서, 길이 239에 대해서만 수행되는 하나의 특정 최적화는 큰 속도 차이를 담당합니다. 그러나 천천히 시작합시다.

(이 답변의 모든 코드는 -C opt-level=3 컴파일됩니다)

pub fn foo() -> usize {
    let arr = [0; 240];
    let mut s = 0;
    for i in 0..arr.len() {
        s += arr[i];
    }
    s
}

이 간단한 코드는 대략적인 어셈블리, 즉 요소를 추가하는 루프를 생성합니다. 그러나 240239 변경하면 방출 된 어셈블리가 상당히 다릅니다. Godbolt 컴파일러 탐색기에서 참조하십시오 . 다음은 어셈블리의 작은 부분입니다.

movdqa  xmm1, xmmword ptr [rsp + 32]
movdqa  xmm0, xmmword ptr [rsp + 48]
paddq   xmm1, xmmword ptr [rsp]
paddq   xmm0, xmmword ptr [rsp + 16]
paddq   xmm1, xmmword ptr [rsp + 64]
; more stuff omitted here ...
paddq   xmm0, xmmword ptr [rsp + 1840]
paddq   xmm1, xmmword ptr [rsp + 1856]
paddq   xmm0, xmmword ptr [rsp + 1872]
paddq   xmm0, xmm1
pshufd  xmm1, xmm0, 78
paddq   xmm1, xmm0

이것을 루프 언 롤링 이라고 합니다 . LLVM은 루프 변수를 증가시키고 루프가 종료되었는지 확인하고 루프 시작으로 점프하는 등 모든 "루프 관리 명령"을 실행하지 않아도되도록 루프 바디를 여러 번 붙여 넣습니다. .

궁금한 paddq 경우 : paddq 및 유사한 명령어는 여러 값을 병렬로 paddq 수있는 SIMD 명령어입니다. 또한 2 개의 16 바이트 SIMD 레지스터 ( xmm0xmm1 )가 병렬로 사용되므로 CPU의 명령 수준 병렬 처리는 기본적으로 이러한 두 명령을 동시에 실행할 수 있습니다. 결국, 그들은 서로 독립적입니다. 결국 두 레지스터가 함께 추가 된 다음 스칼라 결과에 수평으로 합산됩니다.

최신 메인 스트림 x86 CPU (저전력 Atom 아님)는 L1d 캐시에 도달 할 때 클럭 당 2 개의 벡터로드를 실제로 수행 할 수 있으며, paddq 처리량은 클럭 당 최소 2 개이며 대부분의 CPU에서 1주기 대기 시간이 있습니다. 지연 시간 (도트 제품의 경우 FP FMA)을 숨기고 처리량의 병목 현상을 숨기는 여러 누산기에 대한 https://agner.org/optimize/ 이 Q & A를 참조 https://agner.org/optimize/ .

LLVM은 완전히 풀리지 않을 때 작은 루프를 언 롤링하지만 여전히 여러 누산기를 사용합니다. 따라서 일반적으로 프런트 엔드 대역폭 및 백엔드 대기 시간 병목 현상은 전체 풀림없이 LLVM 생성 루프에 큰 문제가되지 않습니다.

그러나 루프 언 롤링은 요소 80의 성능 차이에 대해 책임을지지 않습니다! 적어도 언 롤링 만 반복해서는 안됩니다. 하나의 루프를 다른 하나의 루프 안에 넣는 실제 벤치마킹 코드를 살펴 보겠습니다.

const CAPACITY: usize = 239;
const IN_LOOPS: usize = 500000;

pub fn foo() -> usize {
    let mut arr = [0; CAPACITY];
    for i in 0..CAPACITY {
        arr[i] = i;
    }

    let mut sum = 0;
    for _ in 0..IN_LOOPS {
        let mut s = 0;
        for i in 0..arr.len() {
            s += arr[i];
        }
        sum += s;
    }

    sum
}

( Godbolt 컴파일러 탐색기에서 )

CAPACITY = 240 의 어셈블리는 정상적으로 보입니다 : 두 개의 중첩 루프. (함수의 시작 부분에는 초기화를위한 코드가 많이 있습니다. 무시할 것입니다.) 그러나 239의 경우는 매우 다르게 보입니다! 우리는 초기화 루프와 내부 루프가 풀렸다는 것을 알았습니다.

중요한 차이점은 239의 경우 LLVM은 내부 루프의 결과가 외부 루프에 의존하지 않는다는 것을 알 수있었습니다! 결과적으로, LLVM은 기본적으로 내부 루프 만 실행하고 (계산 계산) sum 를 여러 번 더하여 외부 루프를 시뮬레이션하는 코드를 생성합니다!

먼저 위와 거의 동일한 어셈블리 (내부 루프를 나타내는 어셈블리)를 볼 수 있습니다. 그 후 우리는 이것을 봅니다 (나는 어셈블리를 설명하기 위해 주석을 달았습니다; * 로 주석은 특히 중요합니다).

        ; at the start of the function, `rbx` was set to 0

        movq    rax, xmm1     ; result of SIMD summing up stored in `rax`
        add     rax, 711      ; add up missing terms from loop unrolling
        mov     ecx, 500000   ; * init loop variable outer loop
.LBB0_1:
        add     rbx, rax      ; * rbx += rax
        add     rcx, -1       ; * decrement loop variable
        jne     .LBB0_1       ; * if loop variable != 0 jump to LBB0_1
        mov     rax, rbx      ; move rbx (the sum) back to rax
        ; two unimportant instructions omitted
        ret                   ; the return value is stored in `rax`

여기에서 볼 수 있듯이 내부 루프의 결과는 외부 루프가 실행 된 후 자주 추가 된 다음 반환됩니다. LLVM은 내부 루프가 외부 루프와 무관하다는 것을 이해했기 때문에이 최적화 만 수행 할 수 있습니다.

이는 런타임이 CAPACITY * IN_LOOPS 에서 CAPACITY + IN_LOOPS CAPACITY * IN_LOOPS 을 의미합니다 . 그리고 이것은 큰 성능 차이를 담당합니다.

추가 참고 사항 : 이것에 대해 무엇을 할 수 있습니까? 실제로는 아닙니다. LLVM에는 마법 임계 값이 없어야합니다. LLVM 최적화는 특정 코드에서 완료하는 데 영원히 걸릴 수 있습니다. 그러나이 코드가 매우 인공적이라는 데 동의 할 수도 있습니다. 실제로, 나는 그러한 큰 차이가 발생할 것이라고 의심합니다. 풀 루프 언 롤링으로 인한 차이는이 경우 일반적으로 2의 요소가 아닙니다. 따라서 실제 사용 사례에 대해 걱정할 필요가 없습니다.

관용적 녹 코드에 대한 마지막 메모 : arr.iter().sum() 은 배열의 모든 요소를 ​​요약하는 더 좋은 방법입니다. 그리고 두 번째 예에서이를 변경해도 방출 된 어셈블리에서 눈에 띄는 차이가 발생하지 않습니다. 성능이 저하된다고 측정하지 않는 한 짧고 관용적 인 버전을 사용해야합니다.





llvm-codegen