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

> Clean Markdown view of GeekNews topic #15687. Use the original source for factual precision when an external source URL is present.

## Metadata

- GeekNews HTML: [https://news.hada.io/topic?id=15687](https://news.hada.io/topic?id=15687)
- GeekNews Markdown: [https://news.hada.io/topic/15687.md](https://news.hada.io/topic/15687.md)
- Type: GN+
- Author: [neo](https://news.hada.io/@neo)
- Published: 2024-07-05T09:48:03+09:00
- Updated: 2024-07-05T09:48:03+09:00
- Original source: [mattkeeter.com](https://www.mattkeeter.com/blog/2023-01-25-branch/)
- Points: 1
- Comments: 1

## Topic Body

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

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

##### 코드 예제

```c
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 어셈블리로 번역

```assembly
// 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의 어셈블리 최적화 가이드가 있음

## Comments



### Comment 26972

- Author: neo
- Created: 2024-07-05T09:48:04+09:00
- Points: 1

###### [Hacker News 의견](https://news.ycombinator.com/item?id=40866374) 
- 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 명령어를 생략할 수 있음

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