GCC의 switch 문 로어링

요약

GCC는 switch 문을 비트셋, 점프 테이블, 이진 결정 트리 순서로 나눠 처리합니다.

이 글은 GCC가 switch 문을 더 낮은 수준의 코드로 바꾸는 과정(로어링)을 예제와 컴파일러 소스로 따라갑니다. 저자는 switch가 단순해 보여도 컴파일러는 세 가지 기법을 상황에 맞게 섞어 쓴다고 설명합니다.

왜 중요한가

같은 switch라도 case 값의 간격과 묶임에 따라 전혀 다른 기계어가 나온다는 점을 보여 줍니다.
저자에 따르면 비트셋을 뺀 나머지 최적화는 clang에도 있어서 GCC 밖에서도 참고할 수 있습니다.

핵심 내용

pass_lower_switch 패스는 비트셋을 먼저 찾고, 남은 case를 점프 테이블로 묶은 뒤, 나머지를 결정 트리로 만듭니다.
점프 테이블은 x64와 Arm64에서 case가 5개 이상이어야 하고, 항목 수는 비교 횟수의 8배를 넘지 못합니다.
크기 최적화(-Os)에서는 점프 테이블 항목 수의 한도가 비교 횟수의 2배로 줄어듭니다.
비트셋(값 집합을 정수의 비트로 표시해 검사하는 방식)은 값 범위가 레지스터 폭 안이고 분기 대상이 3개 이하일 때만 씁니다.
연속된 레이블은 범위 하나로 합쳐 비교 횟수를 세므로, 레이블이 20개여도 점프 테이블 대신 비교 트리가 나올 수 있습니다.

HN 반응

글이 GCC가 놓쳤다고 본 8로 나누기를 두고, 8의 배수인지 먼저 검사하면 가능하며 예측하기 어려운 입력에서 더 빨랐다는 실측이 나왔습니다.
크고 희소한 switch에 완전 해시(충돌 없는 해시)를 쓰지 않는다는 비판에, 그런 코드가 자주 실행되는 경우는 드물다는 반론이 맞섰습니다.

30개 표시 · 전체 49개

LarsKrimi1일 전 HN

sparse_8의 switch는 점프 전에 x를 8로 나누면 단순해질 수 있다. 흥미롭게도 gcc는 이런 단순화를 찾아내지 못한다.

그럴 수 없습니다. 그러면 각 case마다 값 7개가 기본 case 대신 함수 호출로 넘어가게 되거든요. 0/8은 0이지만 3/8도 0이니까요.

rep_lodsb1일 전 HN

값이 전부 8로 나누어떨어지니까 이렇게 할 수 있습니다.

    cmp  eax,40
    ja   <return 0>
    test eax,7
    jnz  <return 0>
    jmp  JumpTable[rax]

LarsKrimi1일 전 HN

맞습니다. 좋은 지적이에요. 제가 처음 생각했던 것보다 훨씬 짧네요.

이걸 바탕으로 만든 버전을 원본과 비교해 간단히 벤치마크해 봤습니다. 제 오래된 컴퓨터에서 GCC로 예측할 수 없는 입력을 넣으면 거의 두 배 빨랐습니다(4.5ns 대 2.72ns). x 값이 자주 같은 예측 가능한 입력에서는 원본 버전이 더 빠릅니다.

    int sparse_8_jump(int x, int val) {
        unsigned int idx = (unsigned int)x >> 3;
        if (idx > 5)
            return 0;
        if (x & 7)
            return 0;

switch (idx) {
            case 0:
                return f0(val);
            case 1:
                return f1(val);
            case 2:
                return f2(val);
            case 3:
                return f3(val);
            case 5:
                return f4(val);
            default:
                return 0;
        }
    }

ack_complete1일 전 HN
로테이트로도 할 수 있을 것 같은데, 더 빠른지는 모르겠습니다.
```
  mov ecx, eax
  ror eax, 3
  cmp eax, 5
  ja  <return 0>
  jmp JumpTable[rcx]
```
Findecanor1일 전 HN

점프 테이블이라면 범위를 줄이는 게 크기를 줄이는 데 도움이 되겠지만, 결정 트리라면 상관없습니다.

... 즉시값(immediate) 인자의 크기가 코드 크기에 영향을 주는 경우는 예외입니다. 다만 이 예제 코드에서는 상수가 전부 cmp의 imm8 인자에 들어갑니다.
rurban1일 전 HN

clang과 gcc는 참 부끄럽네요! 크고 듬성한 switch 테이블에 완전 해시(perfect hash)를 아직도 구현하지 않았잖아요. 저는 최근 제 C 컴파일러 rcc에 그걸 넣었는데, 하루밖에 안 걸렸어요. 특히 유니코드 작업에 이점이 큽니다. LLVM 패치는 10년 전에 거절당했고요. gcc에는 유니코드 패치가 브랜치에 여럿 잠들어 있는데, 그것들도 이게 필요할 거예요.
jcranmer1일 전 HN

컴파일러 최적화는 컴파일 시간, 실행 시간, 코드 크기 사이의 트레이드오프이고, 거기에 개발자가 쓸 수 있는 시간이라는 제약이 얹힙니다.

switch 테이블에 완전 해시를 쓰면 주로 크고 듬성한 switch에서 유용한데, 핫 경로에 있는 크고 듬성한 switch는 드뭅니다. 제가 떠올릴 수 있는 가장 비슷한 예(예: 파싱 테이블)도 다른 도구가 생성했을 가능성이 높으니, 컴파일러 대신 그 도구를 바꾸면 됩니다. 컴파일러에 구현해 볼 만한 쓸모 있는 최적화로는 전혀 보이지 않습니다.
bobmcnamara1일 전 HN

에뮬레이터나 VM에서는 자주 나오고, 실제로 그런 코드도 도구가 생성하는 경우가 많습니다.
flohofwoe1일 전 HN

글쎄요, 제 경험상 적어도 에뮬레이터에서는 switch 테이블에 '구조'가 충분히 있어서 GCC나 Clang이 점프 테이블로 바꾸는 데 별 어려움이 없던데요.
bobmcnamara7시간 전 HN

RISC 코드라면 대개 그걸로 충분합니다.

그런데 저는 분기 대상의 최소 크기를 지정하는 플래그가 있었으면 좋겠어요. switch의 분기 대상이 전부 같은 크기면 점프 테이블을 곱셈-누산으로 바꿀 수 있는 경우가 많고, 심지어 시프트와 덧셈만으로 되는 경우도 있거든요.
nh21일 전 HN
LLVM이 성능 개선에 쓸 시간이 없는 건 아직도 열린 이슈 3만 개를 읽고 있어서 아닐까요? 그중에는 런타임에 잘못된 결과를 내는 잘못된 컴파일(miscompilation)도 있고요.

예를 들어 제가 올린 += 2가 고장 났다는 버그 리포트는 3년째 아무도 확인(읽기나 했는지)하지 않았습니다.
```
    const size_t n = 13; // triggers the issue
    #pragma omp parallel for
      for (uint32_t i = 0; i < n; i += 2) {  // counts PAST 13!
```
https://github.com/llvm/llvm-project/issues/70687
rurban1일 전 HN

맞아요. restrict도 거기선 여전히 고장 나 있어요. 열린 이슈 3만 개는 gcc보다 더 심각하고요.
SubjectToChange1일 전 HN

llvm-project의 열린 이슈 전체를 GCC와 비교하는 건 분명 불공정합니다. 예를 들어 MLIR 관련이 500개 넘고, BOLT/lld/lldb 관련이 1700개, GCC에는 없는 여러 clang 도구(clang-tidy, clang-format, clang-doc 등) 관련이 거의 3000개, HLSL 지원 관련이 442개, LLVM libc 쪽이 281개, 각종 새니타이저에 열린 이슈가 또 200개 있는 식이니까요. clang-cl처럼 clang이 추가로 제공하는 호환성도 있고, clang이 (문서화되지 않은) GCC의 특이한 동작과도 호환되려고 한다는 점은 말할 것도 없고요.

llvm-project 저장소의 열린 이슈를 비교하는 건 사실상 GCC, binutils-gdb, glibc, 그리고 여러 유틸리티의 열린 이슈를 합쳐서 비교하는 것과 같습니다. 게다가 LLVM 프로젝트는 컴파일러 인프라/라이브러리 프레임워크를 지향하니, GCC보다 버그나 이슈가 생길 표면적이 당연히 더 넓습니다. GCC가 GIMPLE이나 다른 수많은 내부 표현과 상호작용하는 범용 API를 제공하는 것도 아니잖아요.
rurban20시간 전 HN
제 C 전용 테스트 스위트에서 나온 숫자가 있습니다. https://github.com/rurban/rcc#test-results
```
    gcc:   244 fails
    clang: 826 fails
```
둘 다 0이어야 합니다. 저는 제 모든 컴파일러에서 0을 목표로 하고 있어요.
aw16211071일 전 HN

restrict도 거기선 여전히 고장 나 있어요.

Rust가 그 밑바탕 메커니즘을 많이 쓴다는 점을 생각하면 좀 의외네요. Clang에서 restrict를 쓰는 방식만 말씀하시는 건가요, 아니면 LLVM에 아직 고장 난 부분이 있다는 건가요?
rurban1일 전 HN

짧은 루프에서는 아직 고장 나 있고, Rust도 그걸 우회해야 했어요. 그래서 이를 확인하는 autoconf 프로브를 추가했습니다. https://github.com/rurban/autoconf-archive/blob/master/m4/ax_c_restrict.m4
aw16211071일 전 HN

흠, 흥미롭네요. 그런 얘기는 처음 들어요. 여전히 잘못된 컴파일을 일으킨다면 Rust 개발자들이 noalias 출력을 되돌렸을 거라고 생각했거든요. 버그 트래커를 잠깐 훑어봤는데 눈에 띄는 건 없었어요. 제가 놓쳤을 수도 있지만요.

참고로 Godbolt로 보면 그 프로브의 테스트 프로그램은 Clang 12.0.0 이상에서 제대로 동작하는 것 같습니다. 제 기억이 맞다면 Rust가 noalias 출력을 (다시(또 다시?)) 켠 시점이 그 무렵입니다.
stefan_1일 전 HN

#pragma omp

아하, 거기 있었네요! 이 이슈를 안 돌보는 건 OpenMP가 곧 죽으면 저절로 해결될 일이기 때문이죠.
SubjectToChange1일 전 HN

OpenMP는 10년 전보다 지금이 더 나은 자리에 있다고 볼 수 있습니다. 예를 들어 MSVC가 더 새로운 OpenMP 표준을 지원하기 시작했고, 구현체들은 이제 진짜 디바이스 오프로딩을 지원합니다. 사실 OpenMP는 지금 쓰이는 C/C++/Fortran용 병렬 프로그래밍 인터페이스 중 가장 인기 있을 겁니다.

물론 OpenMP는 예쁜 API도 아니고, 최고 수준의 성능을 낼 가능성도 낮습니다. 하지만 이식성이 매우 높고, GCC와 LLVM/clang에서 일급 지원을 받으며, 코드를 거의 바꾸지 않고도 "충분히 좋은" 성능을 내기가 아주 쉽습니다. 저는 개인적으로 훌륭하다고 생각합니다.
jamiejquinn1일 전 HN

아주 과감한 주장이네요! OpenMP가 사라지는 중이라고 생각하시는 이유가 뭔가요?
RossBencina1일 전 HN

성능 특성에 대해 더 듣고 싶습니다. 완전 해시로 연속된 범위에 대응시킨 다음 점프 테이블을 쓰나요, 아니면 완전 해시로 기본 블록까지의 상대 오프셋을 바로 구하나요?
rurban1일 전 HN

제 문서를 보세요. 경우가 몇 가지 있습니다. https://github.com/rurban/rcc/blob/main/docs/rcc.md#-o1-and-up-the-peephole-optimizer-srcoptc
Sopel1일 전 HN

왜 이렇게 느린 거죠? 숫자 기준으로는 제가 예상한 것보다 50배쯤 느려요. https://github.com/ConstexprCore/perfect_hash
erk__1일 전 HN

저도 예전에 아주 큰 switch 문(모든 맥 주소 제조사를 switch 하나에)을 가지고 놀아 본 적이 있어요. LLVM에서는 최적화를 끄면 컴파일이 잘 됐는데, 최적화를 켜면 컴파일에만 30분쯤 걸렸습니다. GCC는 더 빨랐던 것 같은데, 꽤 오래전 일이라 확실하진 않네요. 이 모든 일의 발단이었던 Rust 크레이트에서는 결국 완전 해싱을 썼고, 컴파일이 훨씬 빨랐습니다.
zamalek1일 전 HN

컴파일러는 이것을 결정 트리로 구현할 수 있다(어쩌면 그러지 않는 편이 낫겠지만).

결정 트리가 확실히 더 빠른 경우도 있습니다. System.HashCode를 개발할 때 저는 switch를 썼는데(.NET에서는 항상 점프 테이블로 컴파일되는 걸로 알고 있어요. 적어도 제 경우엔 그때 그랬습니다), 블록 크기에 맞지 않고 남는 바이트를 처리하는 부분이었던 것 같아요. 누가 결정 트리를 제안했거나 제가 직접 시도해 봤는데, 훨씬 빨랐습니다. 아주 오래전 일이라 수치는 없지만, 상황에 따라 결정 트리가 더 나을 수 있어요.
tsukikage1일 전 HN

왜 한 단계를 거치죠? 점프 테이블이 f0..fX를 직접 가리키면 되지, 왜 점프로 다시 점프하는 거죠?
Findecanor1일 전 HN

그 최적화가 그냥 빠져 있는 겁니다.

f0..fX로 가는 jmp는 각각 call과 ret을 최적화한 결과이고, 아마 switch-case 코드가 이미 전개된 뒤 별도 패스에서 처리했을 겁니다.

함수 맨 위의 mov edi, esi도 최적화인데, 레지스터 할당 패스에서 이뤄졌을 가능성이 높습니다. 모든 함수가 같은 값을 같은 레지스터로 받으니까 가능했던 겁니다. 그렇지 않았다면 각 호출 앞에도 mov가 있었을 거예요.
andikleen21일 전 HN

안타깝게도 gcc는 이걸 못 합니다(LLVM이 하는 관련 최적화인, 점프 테이블에 워드/바이트 오프셋을 쓰는 것도 못 하고요). 코드 크기를 근사치로만 추정하기 때문입니다. 코드 크기를 잘못 계산하면 잘못된 컴파일이 되거든요. 통합 어셈블러를 쓰지 않는 것과 관련이 있습니다.
cowlevel20시간 전 HN

점프 테이블에 함수 주소를 넣는 데 왜 코드 크기를 알아야 하죠?
jacquesm5시간 전 HN

꼭 함수 주소는 아니고 점프 테이블의 분기 대상입니다. 그 대상은 서브루틴 중간에 있을 수도 있어요. 주소를 모르면 심벌로 남겨 둬야 하는데, 심벌이면 값이 바뀔 수 있습니다. 예컨대 작은 오프셋에 들어가느냐 마느냐의 '경계선'에 걸려 있다가 더 큰 오프셋으로 넘칠 수도 있죠. 그러면 점프 테이블의 데이터 타입이 바뀌게 됩니다. 바이너리 코드 생성기를 내장하고 있으면 컴파일 시점에 주소를 정확히 알 수 있습니다.

Hacker News에서 보기 ↗