쓸모없는 if로 코드 성능 4배 높이기

 (purplesyringa.moe)
1P by GN⁺ | ★ favorite | 댓글 1개
  • 도메인 특화 압축기의 최적 인코딩 경로를 순회하는 루프에 조건문 하나를 추가해, 합성 벤치마크 실행 시간을 320µs에서 80µs로 줄임
  • 반복마다 메모리 주소가 직전 반복의 j에 의존하므로, 단일 mov 명령도 명령어 수준 병렬성을 활용하지 못한 채 메모리 접근 지연시간에 묶임
  • next_j[i][j]가 대부분 기존 j와 같다는 특성을 분기 예측에 반영하면, CPU가 반복 사이의 의존성을 우회해 여러 반복을 추측 실행할 수 있음
  • 컴파일러가 의미상 불필요한 if를 제거하지 못하도록 volatile 캐스트를 사용함. LLVM에서는 [[unlikely]]나 __builtin_expect(..., 0)도 작동하지만, volatile이 더 나은 코드를 생성하고 GCC도 지원함
  • 현실적인 실험에서는 LLVM의 최적이 아닌 코드 생성 때문일 수 있는 약 2배의 성능 향상을 얻었으며, j를 예측하기 어렵다면 지연시간이 1사이클인 pshufb를 대안으로 사용할 수 있음

압축기의 최적 경로 순회

  • 입력 문자열을 여러 청크로 나누고, 청크마다 가장 작은 인코딩을 선택해야 함
    • 인코딩마다 잘 압축하는 문자가 달라 청크 경계를 바로 결정하기 어려움
    • 이전 글의 알고리듬은 이 문제를 격자 위 최단 경로 탐색으로 변환함
  • 각 셀에는 다음으로 이동할 최적 셀을 기록함
    • 첫 셀부터 마지막 셀까지 참조를 따라가면 최적 인코딩 순서를 얻을 수 있음
  • next_j를 채우는 첫 번째 루프는 SIMD로 이미 최적화돼 있음
    • 실제 병목은 다음과 같은 단순한 경로 순회 루프임
uint8_t encoding[n_symbols];
uint8_t j = 0;

for (int i = 0; i < n_symbols; i++) {
    j = next_j[i][j];
    encoding[i] = j;
}
  • 쓰기를 제외한 핵심 연산 j = next_j[i][j]는 단일 mov 명령으로 컴파일됨

단일 명령도 느려지는 의존성

  • 현대 CPU는 명령어 수준 병렬성을 이용해 여러 명령과 서로 다른 반복의 작업을 동시에 실행함
    • 일반적인 루프에서 i < n_symbols 검사와 i++ 비용이 다른 작업을 막지 않는 이유임
  • 하지만 서로 의존하는 명령은 동시에 실행할 수 없음
    • 현재 반복의 메모리 주소 next_j[i][j]를 계산하려면 직전 반복에서 얻은 j가 필요함
    • 다음 반복은 이전 반복의 결과가 나올 때까지 시작할 수 없어, 데이터가 캐시에 있어도 메모리 접근 지연시간의 영향을 받음

분기 예측을 값 추측으로 활용하기

  • 이 압축기는 청크 수가 많지 않을 것으로 예상되므로 next_j[i][j]가 기존 j와 같은 경우가 대부분임
  • CPU에 j가 유지될 것이라고 직접 주소 예측을 지시할 수는 없지만, 분기 예측을 이용하면 같은 효과를 만들 수 있음
for (int i = 0; i < n_symbols; i++) {
    if (j != next_j[i][j]) {
        j = next_j[i][j];
    }
    encoding[i] = j;
}
  • CPU가 if 본문을 실행하지 않을 것으로 예측하면 j를 갱신하는 반복 간 의존성이 없다고 보고 여러 반복을 추측 실행함
  • 조건이 실제로 참이면 분기 예측 실패 복구가 일어남
    • 잘못 추측해 수행한 쓰기를 폐기함
    • 올바른 j를 사용해 실행을 다시 시작함
  • j가 거의 바뀌지 않는 동안 루프의 병목은 지연시간에서 처리량으로 전환됨

컴파일러가 if를 제거하지 못하게 하기

  • 컴파일러 관점에서는 조건문을 추가한 코드와 원래 코드의 의미가 같음
    • j가 메모리에 있다면 불필요한 쓰기나 읽기 전용 메모리에 대한 쓰기를 피할 수 있지만, 여기서는 레지스터 값임
    • 공통 부분식 제거(CSE) 같은 최적화가 조건과 중복 접근을 제거할 수 있음
  • 일반적인 컴파일러 힌트는 분기를 없애는 데 쓰이지만, 여기서는 반대로 분기 없는 코드를 분기 코드로 유지해야 함
  • 조건 검사와 대입의 메모리 접근이 독립적인 것처럼 보이도록 대입 쪽에 volatile 캐스트를 적용함
for (int i = 0; i < n_symbols; i++) {
    if (j != next_j[i][j]) {
        j = *(uint8_t volatile *)&next_j[i][j];
    }
    encoding[i] = j;
}
  • 7월 13일 추가 확인에서 ibookstein이 발견한 방법처럼 [[unlikely]] 또는 __builtin_expect(..., 0)을 사용해도 LLVM에서 같은 효과를 얻을 수 있음
  • volatile 방식은 더 나은 코드를 생성하고 GCC에서도 동작함

벤치마크에서 확인한 성능 변화

  • 합성 벤치마크에서 루프 실행 시간이 320µs에서 80µs로 감소해 4배 빨라짐
    • 한 번의 실행 시간 차이는 작지만, 압축 과정에서 루프가 여러 번 실행되므로 전체 비용에 누적됨
  • 더 현실적인 실험에서는 약 2배의 성능 향상을 기록함
    • LLVM이 최적이 아닌 코드를 생성한 영향일 가능성이 있지만, 여전히 적용할 가치가 있는 수준이었음

비트마스크 기반 표현이라는 대안

  • 이 알고리듬에서 next_j[i][j]는 두 값 중 하나만 가질 수 있음
    • 대부분은 현재 j임
    • 나머지는 j와 무관하고 i에만 의존하는 값임
  • 8개 원소 배열인 next_j[i]를 대체 값과 비트마스크의 쌍으로 바꿀 수 있음
    • 이 표현에서는 if가 의미상 필요하므로 volatile 우회를 쓰지 않아도 됨
    • 다만 x86에서는 가변 위치의 비트를 검사하는 연산이 비교보다 느릴 수 있어 전체 성능이 오히려 낮아질 가능성이 있음

j를 예측할 수 없을 때

  • 값 추측으로 연결 리스트 순회를 가속하는 글에서도 같은 방식으로 성능을 높이는 방법을 다룸
  • j를 예측하기 어렵다면 벡터 인덱스 연산인 pshufb 를 사용할 수 있음
    • pshufb의 지연시간은 1사이클이므로 추측 실행 없이 더 줄이기 어려움
    • 벡터 연산으로 가능한 각 시작 j의 경로를 병렬 계산할 수 있음
    • 작업을 여러 스레드로 나누고 결과를 병합하는 방식도 가능함

함께 보면 좋은 글 β

GN⁺   [-]
Lobste.rs 의견들

  • C++20의 [[unlikely]] 속성을 if 문에 붙이면 clang이 해당 코드를 제거하지 못하게 하는 데 충분해 보임: https://clang.godbolt.org/z/r4xYWfPfe
    다른 컴파일러에서는 확인하지 못함

    • 다시 확인해 보니 LLVM에서는 실제로 작동했으며, 아마 처음에는 효과가 없는 GCC로 잘못 시험했던 듯함
      다만 [[unlikely]]는 코드를 빠른 경로 밖으로 이동시키므로 LLVM이 아래처럼 다소 비효율적인 코드를 생성함 
              cmp     r8b, dl  
        jne     not_equal  
continue:  
        ...  
not_equal:  
        mov     ecx, edx  
        jmp     continue
      다음 형태가 더 합리적으로 보임 
              cmp     r8b, dl  
        je      skip  
        mov     ecx, edx  
skip:  
        ...
      또한 메모리에서 값을 여러 번 읽지 않도록 최적화하면서 뜨거운 루프에 명령어 하나를 추가하기도 함. 그래서 volatile을 이용한 기법은 여전히 유용하지만, 원래 코드도 그대로 작동할 수 있다는 점은 반가움

  • 이 기법은 다른 곳에서 값 추측(value speculation) 이라고 부름: https://mazzo.li/posts/value-speculation.html

    • 이 방법을 다시 고안하고 나서 아레나에 저장된 연결 리스트에도 적용할 수 있겠다고 처음 생각했는데, 링크된 글이 정확히 그 내용을 다루고 있어 내 글에도 링크를 추가함

  • 앞으로 2~3년 뒤에는 개발자들이 LLM의 출력에 갈수록 무관심해질 텐데, 이런 종류의 블로그 글에도 여전히 관심을 가질지 궁금함

    • 지금도 관심을 두는 사람은 매우 적고, 전체 프로그래밍 분야에서 보면 틈새 지식임
      그래도 관심 있는 사람에게는 여전히 매우 유용하고 좋은 글임
    • Godbolt는 매우 인기 있음. 코드를 읽지 않는 습관을 비판받을 때 LLM에 취한 개발자들이 “어셈블리까지 보느냐?”를 대단한 반박처럼 내놓지만, 실제로 어셈블리를 확인하며 앞으로도 그럴 것임
      세부 사항이 중요하지 않다고 여기는 개발자는 좋은 개발자가 되기 어렵다. 훌륭한 토목 기술자가 대형 프로젝트의 볼트와 너트까지 신경 쓰듯, 훌륭한 개발자도 작은 세부 사항까지 파고들어야 함. 전체는 세부 사항으로 이루어져 있으므로 자신이 만드는 결과물을 중시한다면 이를 피할 수 없음
    • 지금과 근본적으로 다르지 않다고 봄. 현재도 대부분은 사람이 작성한 코드의 컴파일러 출력에 관심이 없음
      AI가 작성한 코드의 컴파일러 출력을 살펴보는 사람은 더 줄 수 있지만, 기본 구도가 달라지지는 않을 것 같음
    • 달라지는 것은 관심사의 유무보다 최적화 우선순위의 재배치에 가까움
      10년 전 Bash 스크립트가 조금 느리다고 해서 명령어 수준 병렬성이나 CPU 분기 예측부터 고민하지는 않았을 것임. 컴파일 및 최적화 가능한 언어로 작성된 성능 핵심부가 있고, 그 안에 세부적으로 살펴볼 뜨거운 경로가 있으며, 다시 그 안에서 벡터화나 최신 CPU의 동작 차이를 확인할 가치가 있는 뜨거운 루프 한두 개가 존재할 수 있음
      LLM을 사용하더라도 성능상 가장 뜨거운 지점은 예외적으로 직접 검토할 가치가 있음. 결과물의 낮은 품질을 의식적으로 감수하거나, LLM으로 70%를 만든 뒤 나머지 30%를 손으로 고치는 방식이 85:15까지 개선될 수는 있어도 이 글은 여전히 상위 1% 수준의 세부 영역을 다루는 셈임
    • C++을 작성하지 않으므로 그런 의미에서는 지금도 직접적인 관심 대상이 아니지만, 그래도 흥미롭게 읽었고 2~3년 뒤에도 이런 내용은 계속 재미있을 것 같음
답변달기
GeekNews BeeBS 게시판 오픈! 자유로운 이야기와 소소한 일상을 함께 나눠보세요.