GCC switch lowering: 점프 테이블 임계값은 case당 약 8개, gcc가 못 찾는 8로 나누기와 perfect hash 부재

sparse_8에서 x를 8로 나누면 된다는 부분, gcc가 못 하는 이유는 나머지 값들이 전부 default로 가야 하기 때문임. 0/8은 0이지만 3/8도 0이거든.

근데 모든 case 값이 8의 배수니까 이렇게 하면 됨. cmp eax,40으로 범위 체크하고 ja로 0 리턴, test eax,7 하고 jnz로 0 리턴, 그다음 jmp JumpTable[rax].

범위를 줄이는 건 점프 테이블 크기를 줄일 때나 쓸모 있고 결정 트리면 상관 없음. 예제에선 상수가 다 imm8에 들어가서 코드 크기도 안 변함.

하드웨어 분기 예측이랑 BTB 들여다보기엔 switch lowering이 딱 좋음. 큰 switch는 분기 오예측이 많이 나는 지점이라 컴파일러가 하드웨어 맞추려고 엄청 꼬아 놓거든.

그 코드에 하드웨어 관련 내용은 의외로 적음. 비용 계산에 상수 두세 개뿐이고 그중 하나둘만 하드웨어 의존적임. 나중 패스가 점프 타깃 주소를 조정해서 예측기에서 false sharing을 피하게 할 수도 있음.

clang이랑 gcc가 큰 sparse switch에 perfect hash를 아직 안 넣은 게 아쉬움. 내 rcc C 컴파일러엔 하루 만에 넣었고 유니코드 처리에 특히 이득임. LLVM 패치는 10년 전에 거절됐고 gcc도 브랜치에 유니코드 패치가 있음.

성능이 더 안 나아서 거절된 거 아닐까. LLVM 패치 거절 사유가 뭐였는지 궁금하네.

성능 특성이 궁금함. perfect hash로 연속 범위에 매핑한 다음 점프 테이블을 쓰는 방식임, 아니면 바로 베이직 블록 상대 오프셋으로 가는 방식임?

LLVM은 열린 이슈 3만 개를 읽느라 성능 개선할 시간이 없는 듯. 내가 올린 += 2 루프 버그 리포트도 3년째 아무도 확인 안 했음. omp parallel for에서 i += 2로 돌리면 13을 넘어서까지 세더라.

왜 점프 테이블이 f0부터 fX를 직접 안 가리키고 jmp로 한 번 더 뛰는 거임?

그 최적화가 그냥 빠진 거임. jmp f0는 call이랑 ret을 합치는 최적화라 switch 확장이 끝난 뒤 별도 패스에서 함. mov edi,esi도 레지스터 할당 패스에서 나온 거고, 모든 함수가 같은 레지스터로 값을 받아서 가능했음.

자바스크립트에서 불변 Map이랑 Set용으로 코드 생성해봤는데 최신 엔진에선 성능 차이가 없었음. 복잡한 유니코드 범위 정규식에서는 2배 정도 빨라졌고.