240개 이상의 요소로 구성된 어레이를 루프할 때 성능에 큰 영향을 미치는 이유는 무엇입니까?

240개 이상의 요소로 구성된 어레이를 루프할 때 성능에 큰 영향을 미치는 이유는 무엇입니까?

Rust에서 어레이에 대해 sum 루프를 실행할 때 다음과 같은 경우 성능이 크게 저하된다는 것을 알게 되었습니다.CAPACITY>= 240. CAPACITY239는 약 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());
}

요약: 240 미만에서는 LLVM이 내부 루프를 완전히 해제하므로 반복 루프를 최적화하여 벤치마크를 위반할 수 있습니다.

---

마법 임계값을 발견했습니다. 이 임계값을 초과하면 LLVM이 특정 최적화를 수행하지 않습니다.임계값은 8바이트 * 240 = 1920바이트입니다(어레이는usizes, 따라서 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
}

이 간단한 코드는 대략적으로 예상되는 어셈블리, 즉 요소를 추가하는 루프를 생성합니다.하지만, 만약 당신이 바꾼다면,240로.239방출된 어셈블리는 상당히 다릅니다.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및 유사한 명령어는 여러 값을 병렬로 합계할 수 있는 SIMD 명령어입니다.게다가, 두 개의 16바이트 SIMD 레지스터 (xmm0그리고.xmm1)는 CPU의 명령어 수준 병렬화가 기본적으로 두 개의 명령어를 동시에 실행할 수 있도록 병렬로 사용됩니다.결국, 그들은 서로 독립적입니다.마지막으로, 두 레지스터가 함께 추가된 다음 스칼라 결과로 수평으로 요약됩니다.

최신 메인스트림 x86 CPU(저전력 Atom이 아님)는 L1d 캐시에서 작동할 때 클럭당 2개의 벡터 로드를 수행할 수 있습니다.paddq또한 처리량은 클럭당 최소 2개이며 대부분의 CPU에서 1사이클 지연 시간이 발생합니다.대신 지연 시간(도트 제품에 대한 FP FMA의 경우)과 처리량의 병목 현상을 숨기려면 https://agner.org/optimize/ 및 여러 축전지에 대한 이 Q&A를 참조하십시오.

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두개중루정보로다니입상으 (의 시작 위한 가 꽤 , 입니다.) (이함시다부초위기꽤코있무니를습는겠시하한만지화분드가에작의수의첩프가)▁just)()하지만 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은 내부 루프가 외부 루프와 독립적이라고 이해했기 때문에 이 최적화만 수행할 수 있습니다.

이는 런타임이 에서 로 변경된다는 것을 의미합니다. 그리고 이것은 엄청난 성능 차이를 야기합니다.

---

추가적인 참고 사항: 이것에 대해 무엇이든 할 수 있습니까?사실 그렇지 않아요.LLVM에는 마법의 임계값이 있어야 하므로 이러한 임계값이 없으면 특정 코드에서 LLVM 최적화를 완료하는 데 오랜 시간이 걸릴 수 있습니다.하지만 우리는 또한 이 코드가 매우 인위적이었다는 것에 동의할 수 있습니다.실제로, 저는 그렇게 큰 차이가 발생할지 의심스럽습니다.이러한 경우 전체 루프 전개로 인한 차이는 일반적으로 요인 2도 아닙니다.따라서 실제 사용 사례에 대해 걱정할 필요가 없습니다.

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

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

언급URL : https://stackoverflow.com/questions/57458460/why-is-there-a-large-performance-impact-when-looping-over-an-array-with-240-or-m