이 실습은 컴파일러가 최적의 코드를 생성하지 못하는 코드 부분을 컴파일러 내장 함수를 사용해 빠르게 만드는 두 번째 실습입니다.

이 실습 과제의 목표는 파일에서 가장 긴 줄을 찾는 것입니다. 컴파일러 내장 함수를 활용하면 줄 끝 문자를 병렬로 찾는 방법이 있습니다.

보너스 과제: 내장 함수를 사용한 풀이가 기준 버전보다 빠른지는 입력 데이터에 크게 좌우됩니다. 여러 입력 파일로 풀이를 실행해 속도 향상/저하 정도를 확인하십시오.

이 실습의 아이디어는 Yuriy Lyfenko(@obender12)가 제안했습니다.

Co-authored-by: Andrew Evstyukhin (@andrewevstyukhin)

Co-authored-by: Jakub Beránek (@Kobzol)

힌트

힌트 1:

코드를 직접 벡터화하여 한 번에 최대한 많은 char를 읽고자 합니다. 대부분의 기기는 한 번에 최대 256비트까지 처리할 수 있습니다. Intel 내장 함수 가이드(Intel Intrinsics Guide)의 어떤 명령어 집합 계열이 이 용도에 가장 적합하겠습니까?


힌트 2:

AVX 명령어를 사용하십시오. 이제 하나의 벡터에 8비트 char 32개가 들어 있으니, 이 문자 중 몇 개가 개행 문자 \n과 일치하는지 어떻게 효율적으로 찾을 수 있겠습니까? _mm256_set1_epi8, _mm256_cmpeq_epi8, _mm256_movemask_epi8 명령어로 무엇을 할 수 있는지 살펴보십시오.


힌트 3:

마스크를 사용해 256비트 벡터에서 \n의 위치를 추출하는 방법을 알아냈다면, 결과 마스크에서 설정된 비트(1) 사이에 있는 0의 개수가 입력에서 한 줄의 길이를 나타냅니다. 어떤 줄은 길이가 32보다 길 것이므로, 반복 간에 이를 추적할 방법이 필요합니다. 256비트 벡터를 채우기에는 너무 짧은 나머지 줄을 처리하는 것도 잊지 마십시오.


풀이:

배경:

이 실습의 목표는 파일에서 가장 긴 줄, 더 구체적으로는 개행 문자(또는 EOL 문자)가 나오기 전까지 이어지는 가장 긴 연속 텍스트 문자열을 찾는 것입니다.

기존 코드는 문자를 하나씩 순회하며 \n과 비교합니다. 성능 벤치마크 예시는 다음과 같습니다.

-----------------------------------------------------------------
Benchmark                       Time             CPU   Iterations
-----------------------------------------------------------------
bench1/iterations:8000        344 us          344 us         8000

이 알고리즘은 입력의 전체 길이를 n이라 할 때 O(n) 시간에 실행되지만, 컴파일러 내장 함수를 사용하면 한 번의 반복에서 수행할 수 있는 비교 횟수를 늘려 속도를 높일 수 있습니다.

해결책

컴파일러 내장 함수를 사용하면 벡터 명령어 하나로 char 32개를 읽고, 이어서 명령어 하나로 이들을 비교할 수 있습니다. 이렇게 하면 알고리즘의 성능이 크게 향상될 것입니다. 이를 어떻게 구현하는지 살펴봅시다.

먼저 문자열에서 현재 위치를 추적하기 위해 pos 변수를 설정합니다. 그런 다음 입력 내용의 길이를 확인합니다. 입력 내용이 32 char 이상이면 SIMD 코드를 사용할 수 있습니다.

int pos = 0;
int len = inputContents.size();

if (len >= 32) {
    // SIMD code goes here...
}

한 번에 32개의 char를 다루게 되며, 이는 32바이트 = 256비트입니다. 줄 바꿈 문자 '\n'의 SIMD 마스크를 준비합시다:

using v32i = __m256i;
const v32i eol = _mm256_set1_epi8('\n');

루프에서는 길이를 세고 있는 현재 줄의 시작 위치와 함께, 각 반복에서 불러오는 32개 요소 중 첫 번째 요소를 가리키는 포인터도 추적해야 합니다:

uint32_t curr_begin = 0;
auto* ptr = inputContents.data();

내부 루프가 어떻게 생겼는지 살펴보고 단계별로 설명하겠습니다:

for (; pos + 32 < len; pos += 32) {
  v32i v = _mm256_loadu_si256(reinterpret_cast<const v32i*>(ptr));
  v32i v_mask = _mm256_cmpeq_epi8(v, eol);
  uint32_t mask = _mm256_movemask_epi8(v_mask);
  while (mask) {
    uint32_t chars = _tzcnt_u32(mask); // C++20 version: uint32_t chars = std::countr_zero(mask);
    uint32_t curr_len = (pos - curr_begin) + chars;
    if (pos < curr_begin) {
      // Case where our mask has picked up multiple '\n' in one chunk.
      // Therefore, the `curr_len` should just be the gap between adjacent '\n', which is `chars`
      curr_len = chars;
    }

    curr_begin += curr_len + 1;
    longestLine = std::max(longestLine, curr_len);

    // Prepare bit-shift to remove current line of length `chars` plus the extra '\n' character
    chars++;
    if (chars > 31) {
      break;
    }
    mask >>= chars;
  }
  ptr += 32;
}

먼저 ptr이 가리키는 주소에서 다음 32개 문자를 불러옵니다. 그런 다음 YMM 레지스터를 사용하는 단일 벡터화 명령어로 32개 문자 모두를 '\n'과 비교하는 SIMD 벡터 비교를 수행하며, 이는 매우 효율적입니다. 그 후에는 벡터 출력을 표준 스칼라 uint32_t로 변환해야 하며, 이 값의 설정된 비트는 32개 문자 묶음 중 '\n'과 같았던 문자에 대응합니다:

v32i v = _mm256_loadu_si256(reinterpret_cast<const v32i*>(ptr)); // Get next 32 characters
v32i v_mask = _mm256_cmpeq_epi8(v, eol); // SIMD compare 32 characters with '\n'
uint32_t mask = _mm256_movemask_epi8(v_mask); // Convert to scalar value. Set bits correspond to positions where comparisons were equal

mask가 0이 아니면 '\n'을 하나 이상 포함하는 구간을 찾은 것입니다. mask의 후행 0의 개수를 세어 현재 줄 길이에 더해지는 몫을 구하고, 새로운 가장 긴 문자열을 찾았다면 longestLine을 갱신합니다. mask가 0이 될 때까지 mask의 모든 설정된 비트에 대해 이 작업을 수행합니다.

  while (mask) {
    uint32_t chars = _tzcnt_u32(mask); // C++20 version: uint32_t chars = std::countr_zero(mask);
    uint32_t curr_len = (pos - curr_begin) + chars;
    if (pos < curr_begin) {
      // Case where our mask has picked up multiple '\n' in one chunk.
      // Therefore, the `curr_len` should just be the gap between adjacent '\n', which is `chars`
      curr_len = chars;
    }

    curr_begin += curr_len + 1;
    longestLine = std::max(longestLine, curr_len);

    // Prepare bit-shift to remove current line of length `chars` plus the extra '\n' character
    chars++;
    if (chars > 31) {
      break;
    }
    mask >>= chars;
  }
  ptr += 32;

그런 다음 코드에 원래 있던 루프를 수정하여 입력 문자열 중 길이가 32 미만인 나머지 부분을 처리합니다:

  for (; pos < len; pos++) {
    curLineLength = (inputContents[pos] == '\n') ? 0 : curLineLength + 1;
    longestLine = std::max(curLineLength, longestLine);
  }

이러한 변경이 성능에 미치는 영향은 상당합니다. 원래 코드의 344 us에 비해 86.3 us의 실행 시간을 보입니다:

-----------------------------------------------------------------
Benchmark                       Time             CPU   Iterations
-----------------------------------------------------------------
bench1/iterations:8000       86.3 us         86.1 us         8000

해결책 코드(링크):

해결 코드 링크