• 도메인 특화 압축기의 최적 인코딩 경로를 순회하는 루프에
  조건문 하나를 추가해, 합성 벤치마크 실행 시간을 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

의 경로를 병렬 계산할 수 있음

• 작업을 여러 스레드로 나누고 결과를 병합하는 방식도 가능함