GCC가 switch 문을 점프 테이블로 바꾸는 기준은 무엇일까
Switch Lowering in GCC
GCC는 switch 문을 점프 테이블, 비교 트리, 비트셋 등으로 최적화한다. 예를 들어 값이 0부터 4까지 연속되면 점프 테이블을 만들고, 간격이 7인 값들은 여전히 점프 테이블로 처리하지만 간격이 8이 되면 비교 트리로 전환한다. 또한 연속된 case 레이블은 두 번의 비교로 묶어 처리하며, 드문 값은 분기로 분리한다. 저자는 GCC 소스의 analyze_switch_statement를 단계별로 분석해 이러한 휴리스틱이 어떻게 구현되는지 설명한다.
컴파일러는 해당 case들이 연속적임을 인식하고 네 번 대신 두 번의 비교로 구현할 수 있다.
HN 토론
36- LarsKrimi
sparse_8의 switch는 점프 전에 x를 8로 나누면 단순화할 수 있습니다. 흥미롭게도 gcc는 이 단순화를 찾지 못합니다.
그럴 수 없는 게, 그렇게 하면 각 case에 대해 7개의 값이 default case 대신 함수 호출로 처리되게 됩니다 - 0/8은 0이지만, 3/8도 0입니다.
- rurban
clang과 gcc에게 참 안타까운 일입니다! 그들은 여전히 큰 희소 switch 테이블에 대해 완벽한 해시를 구현하지 못하고 있습니다. 최근에 제 rcc C 컴파일러에 그걸 구현했는데, 겨우 하루 작업이었습니다. 특히 유니코드 작업에 유리합니다. LLVM 패치는 10년 전에 거부되었습니다. Gcc는 브랜치에 여러 유니코드 패치가 있는데, 그것들도 이게 필요할 겁니다.
- p-t
compact_7()에 있는 34는 35여야 하고, bittest()에 있는 edx는 어느 시점에 사용되어야 했을 거라고 생각합니다 (제가 뭔가 놓치고 있는 게 아니라면요 ㅋㅋ).
- tsukikage
왜 간접 참조를 할까요? - 점프 테이블이 점프로 점프하는 대신 f0..fX를 직접 참조하게 하면 안 될까요?
- Andi
자바스크립트에서 불변 Map과 Set을 위해 (코드를 생성해서) 비슷한 것들을 구현했던 기억이 납니다 - 최신 엔진에서는 성능 향상이 미미했습니다. 복잡한 유니코드 범위의 정규식의 경우 속도 향상이 약 2배였습니다!