- 도메인 특화 압축기의 최적 인코딩 경로를 순회하는 루프에 조건문 하나를 추가해, 합성 벤치마크 실행 시간을 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의 경로를 병렬 계산할 수 있음
- 작업을 여러 스레드로 나누고 결과를 병합하는 방식도 가능함
2 days ago
4
English (US) · 