▲

GN⁺: 행복한 재미있는 분기 예측기 조롱 금지 (2023)

 (mattkeeter.com)
1P by neo 5달전 | favorite | 댓글 1개

행복한 분기 예측기를 조롱하지 마세요

  • 최근 AArch64 어셈블리를 많이 작성하고 있음
  • 루프에서 점프를 하나 제거하려는 "똑똑한" 아이디어가 성능을 저하시킴
  • 이 실수를 설명하여 다른 사람들이 같은 실수를 하지 않도록 함

코드 예제

float run(const float* data, size_t n) {
  float g = 0.0;
  while (n) {
    n--;
    const float f = *data++;
    foo(f, &g);
  }
  return g;
}

static void foo(float f, float* g) {
  // g를 수정하는 작업
}

AArch64 어셈블리로 번역

// x0: const float* data
// x1: size_t n
// s0: 반환할 float
stp  x29, x30, [sp, #-16]!
mov s0, #0.0
loop:
  cmp x1, #0
  b.eq exit
  sub x1, x1, #1
  ldr s1, [x0], #4
  bl foo
  b loop
foo:
  // s1에서 읽고 s0에 누적
  // ...
  ret
exit:
  ldp  x29, x30, [sp], #16
  ret

최적화 시도

  • bl 명령어를 줄여 성능을 향상시키려 함
  • 그러나 성능이 오히려 저하됨

성능 비교

  • 원본 코드: 969 ns
  • 최적화 코드: 3.85 µs

원인 분석

  • 분기 예측기가 bl과 ret 쌍이 맞지 않아 혼란스러워함
  • ARM 문서에 따르면, ret 명령어는 함수 반환을 예측하는 데 도움을 줌

해결 방법

  • ret 대신 br x30 사용
  • 성능 회복: 913 ns

추가 최적화

  • foo를 인라인하여 성능 향상
  • 루프 언롤링 및 SIMD 명령어 사용

최종 성능

  • SIMD + 수동 루프 언롤링: 94 ns

결론

  • 분기 예측기를 혼란스럽게 하지 말 것
  • SIMD 코드가 더 빠르지만, 부동 소수점 덧셈이 결합 법칙을 따르지 않으므로 결과가 다를 수 있음

GN⁺의 의견

  • 이 글은 AArch64 어셈블리 최적화의 중요성을 잘 보여줌
  • 분기 예측기의 작동 원리를 이해하는 것이 성능 최적화에 필수적임
  • SIMD 명령어를 사용한 최적화는 매우 효과적이지만, 정확도 문제를 고려해야 함
  • Rust와 같은 고수준 언어를 사용하면 컴파일러 최적화를 통해 성능을 쉽게 향상시킬 수 있음
  • 유사한 기능을 가진 프로젝트로는 Agner Fog의 어셈블리 최적화 가이드가 있음
▲
neo 5달전  [-]
Hacker News 의견

  • Apple II 시절의 친구들과 함께 기사를 요약했음

    • 최적화된 코드가 1024개의 32비트 부동 소수점 숫자를 합산하는 데 94 나노초가 걸림
    • 1 MHz 6502는 94 나노초 동안 첫 번째 명령어의 첫 번째 바이트를 메모리에서 가져오려고 할 것임
    • 이 코드는 캐시에서 실행될 때만 최적화된 성능을 발휘함. DRAM은 느림

  • Raymond Chen이 거의 20년 전에 동일한 주제를 다뤘음

    • 루프 종료를 확인한 후 분기 없이 foo 함수로 넘어감
    • 기본적인 예측 휴리스틱을 위반한 것임
    • 분기 예측기가 반환 주소의 그림자 스택을 유지하는 것은 수십 년 동안 존재해 왔음

  • SIMD 코드에는 부동 소수점 덧셈이 결합법칙을 따르지 않기 때문에 다른 순서로 합산을 수행할 수 있음

    • 이는 컴파일러가 SIMD 명령어를 생성하지 않는 이유일 수 있음
    • 부동 소수점 합산은 기본적으로 오류 범위를 가지며, 그 범위 내의 모든 답변은 유효함
    • 특수한 부동 소수점 입력이 있는 경우 언어는 이를 명시적으로 인코딩할 수 있는 수단을 제공해야 함

  • Rust 1.78 이후 컴파일러는 더 공격적인 루프 언롤링과 약간의 SIMD를 사용함

    • 루프 언롤링은 Rust 1.59에서 시작됨
    • Github 코드에서는 Rust 1.67.0-nightly 버전을 사용하고 있었음

  • ARM/ARM64 어셈블리에서 x0가 어떻게 증가하는지 혼란스러웠음

    • ldr s1, [x0], #4 명령어가 x0를 4만큼 증가시키면서 로드함
    • x86_64에는 한 번에 로드하고 증가시키는 단일 명령어가 없음

  • 어셈블리 코드를 최적화하기 위해 덜 복잡한 방법을 시도하지 않은 것이 놀라움

    • 루프의 맨 아래에서 하나의 분기만 필요하도록 어셈블리 코드를 재작성할 수 있음
    • foo를 인라인하고 RET 명령어를 생략할 수 있음

  • 작성자가 단위를 계속 바꾸지 않았으면 좋겠다는 의견이 있었음

답변달기