GN⁺: AVX-512을 사용한 tolower() 함수

• 몇 년 전, SWAR 트릭을 사용하여 tolower()를 빠르게 처리하는 방법에 대해 글을 썼음. 며칠 전, Olivier Giniaux의 글에서 SIMD 명령어를 사용하여 작은 문자열을 처리하는 최적화 방법에 대해 흥미를 느꼈음. 이 방법은 Rust로 작성된 빠른 해시 함수에서 사용됨.

• SIMD 명령어는 짧은 문자열을 쉽게 처리할 수 있지만, 메모리와 벡터 레지스터 간의 전송이 어렵다는 점이 항상 불편했음. Olivier의 글은 이 문제를 해결하는 재미있는 방법을 제시했음.

희망의 징후

• 일부 SIMD 명령어 세트는 문자열 처리를 위한 유용한 마스크 로드 및 스토어 기능을 제공함. 이는 바이트 단위로 작동함.

  • ARM SVE: 최근의 큰 ARM Neoverse 코어에서 사용 가능, 예를 들어 Amazon Graviton. 하지만 Apple Silicon에서는 사용 불가.
  • AVX-512-BW: 최근 AMD Zen 프로세서에서 사용 가능. AVX-512는 복잡한 확장 세트로, Intel에서는 지원이 랜덤함.

• AMD Zen 4 박스를 가지고 있어 AVX-512-BW를 시도해보기로 했음.

tolower64()

• Intel intrinsics 가이드를 사용하여 한 번에 64바이트를 처리할 수 있는 기본 tolower() 함수를 작성함.
  • *를 와일드카드로 사용하여 mm512*epi8을 검색해 바이트 단위의 AVX-512 함수를 찾음.
  • 몇 가지 레지스터를 64개의 유용한 바이트로 채움.
  • 대문자를 소문자로 변환하기 위해 필요한 숫자를 설정함.
  • 입력 문자를 A와 Z와 비교하여 대문자인지 확인함.
  • 마스크를 사용하여 대문자인 경우 소문자로 변환함.

대량 로드 및 스토어

• tolower64() 커널을 더 편리한 함수로 감싸야 함. 예를 들어, 문자열을 복사하면서 소문자로 변환하는 함수.
  • 긴 문자열의 경우, 정렬되지 않은 벡터 로드 및 스토어 명령어를 사용함.

마스크 로드 및 스토어

• 작은 문자열과 긴 문자열의 끝 부분은 마스크된 정렬되지 않은 로드 및 스토어를 사용함.
  • 마스크는 첫 len 비트가 설정됨.
  • 로드와 스토어는 마스크가 추가된 전체 너비 버전과 유사함.

벤치마킹

• 여러 유사한 함수의 성능을 벤치마킹함.

  • Clang 16으로 컴파일하고 AMD Ryzen 9 7950X에서 실행함.
  • 각 함수는 별도로 컴파일하여 인라인 및 코드 이동의 간섭을 피함.

• 결과:

  • tolower64는 테스트된 모든 함수 중 가장 빠름.
  • copybytes64는 tolower64와 유사한 방식으로 AVX-512를 사용하지만 크게 빠르지 않음.
  • copybytes1은 바이트 단위로 memcpy를 수행하며, Clang 11의 자동 벡터화가 상대적으로 좋지 않음을 보여줌.
  • 표준 tolower()는 가장 느림.
  • tolower1은 Clang 16으로 컴파일된 바이트 단위 tolower()이며, 자동 벡터화가 개선되었지만 여전히 느림.
  • tolower8은 이전 블로그 글에서 소개한 SWAR tolower()이며, Clang이 자동 벡터화를 시도하지만 결과가 좋지 않음.
  • memcpy는 초기에는 빠르지만 copybytes64의 절반 속도로 떨어짐.

결론

• AVX-512-BW는 특히 짧은 문자열을 처리할 때 매우 유용함.

• Zen 4에서 매우 빠르며, 내장 함수가 사용하기 쉬움.

• AVX-512-BW의 성능은 매우 부드러움.

• ARM SVE 지원이 있는 박스가 없어 자세히 조사하지 못했지만, SVE가 짧은 문자열에 얼마나 잘 작동하는지 궁금함.

• 이러한 명령어 세트 확장이 더 널리 사용되기를 바람. 문자열 처리 성능을 크게 향상시킬 것임.

• 이 블로그 글의 코드는 내 웹사이트에서 확인 가능함.

GN⁺의 정리

• 이 글은 SIMD 명령어를 사용하여 짧은 문자열을 효율적으로 처리하는 방법을 설명함.
• AVX-512-BW와 ARM SVE 명령어 세트가 문자열 처리에 유용함을 보여줌.
• 벤치마킹 결과, AVX-512-BW가 특히 짧은 문자열에서 뛰어난 성능을 발휘함.
• 이 글은 성능 최적화에 관심 있는 개발자들에게 유용할 것임.

[neo]

Hacker News 의견

• Rust와 LLVM 메모리 모델에서 "unsafe read beyond of death" 트릭은 정의되지 않은 동작으로 간주됨

  • 컴파일러는 최적화를 위해 이러한 동작이 발생하지 않는다고 가정할 수 있음
  • 이를 피하려면 인라인 어셈블리를 사용해야 함

• AMD의 AVX512 구현과 Intel의 AVX10 경쟁에 대한 호기심이 생김

  • AVX10은 Intel의 P vs E 코어 문제를 해결하기 위한 것임
  • AMD는 상황에 맞게 Zen5의 전체 폭 또는 Zen4, Zen5 모바일의 256비트 더블 펌프를 사용함
  • 큰 성능 향상은 Zen4 코어에서 이루어짐

• SWAR 최적화는 8바이트 주소에 정렬된 문자열에만 유용함

  • 비정렬된 문자열에 적용하면 원래 알고리즘보다 느림
  • 알고리즘을 세 부분으로 나누면 더 많은 명령어가 필요함

• 마스크 추가가 깔끔해 보임

  • .NET 내장 기능에서 AVX512의 마스크 레지스터를 직접 조작할 수 있는 방법이 있었으면 좋겠음

• Clang을 사용하면 더 나은 결과를 얻을 수 있음

  • 더 나은 명령어 선택과 잘 풀린 결과를 제공함

• 짧은 길이의 문자열에 대한 코어 루프는 한 명령어가 더 적음

  • 짧은 문자열을 빠르게 처리하는 것이 중요함

• ASCII를 UTF-8로 대문자/소문자 변환하는 유사한 구현을 C#에서 작성함

  • 짧은 문자열이 대부분의 코드베이스를 지배하므로 빠르게 처리하는 것이 중요함

• AVX512를 사용하여 텍스트를 uwu로 변환하는 SIMD 사용 예시가 있음

• 유니코드 문자 변환을 고려하면 더 인상적일 것임

  • 대부분의 프로그래머는 ASCII에만 신경 쓰지만, 표준 문자 집합 외에도 많은 세계가 존재함

• 과거에 이미지 주위에 검은 테두리를 추가하여 버퍼 SIMD 문제를 피한 경험이 있음

  • 입력을 완전히 제어할 수 없을 때도 있음