AVX-512로 구현한 tolower() 함수

 (dotat.at)
1P by GN⁺ | ★ favorite | 댓글 1개
  • 문자열을 복사하며 ASCII 대문자를 소문자로 바꾸는 작업을 AVX-512-BW로 64바이트씩 처리해, 작은 문자열에서도 SIMD 성능을 끌어내는 실험임
  • 구현의 핵심은 각 바이트가 'A' 이상 'Z' 이하인지 비교한 뒤, 해당 위치에만 'a' - 'A'를 더하는 마스크 연산임
  • 짧은 문자열과 긴 문자열의 남은 꼬리는 마스크드 load/store로 처리해, SIMD 코드가 흔히 겪는 작은 조각 처리 비용을 줄임
  • Clang 16, Debian 11, AMD Ryzen 9 7950X에서 약 1MiB 복사를 1바이트~1KiB 청크로 측정한 결과, tolower64는 비교 대상 중 꾸준히 빠른 축에 속함
  • Zen 4에서는 AVX-512-BW가 문자열 처리에 잘 맞는 모습을 보였지만, ARM SVE와 RISC-V Vector 확장은 직접 자세히 검증하지 못함

AVX-512-BW로 64바이트 tolower() 만들기

  • 목표는 문자열을 복사하면서 대문자 ASCII 문자를 소문자로 바꾸는 tolower() 커널을 SIMD로 구현하는 것임
  • AVX-512-BW는 바이트와 워드 단위 연산을 지원하는 확장으로, 최근 AMD Zen 프로세서에서 사용할 수 있음
    • AVX-512는 여러 확장으로 나뉘어 지원 여부가 복잡함
    • Intel 쪽 지원은 특히 일정하지 않다고 평가함
  • ARM SVE도 문자열 처리에 적합한 바이트 단위 마스크드 load/store를 제공함
    • 최근 big-ARM Neoverse 코어, 예를 들어 Amazon Graviton에서 사용 가능함
    • Apple Silicon에서는 사용할 수 없음
  • RISC-V Vector extension도 ARM SVE와 비슷한 스타일이며, 여러 소형 싱글보드 컴퓨터에서 사용할 수 있음

tolower64()의 동작 방식

  • tolower64()는 한 번에 64바이트를 처리하는 AVX-512 기반 커널임
  • 먼저 64개 바이트가 들어 있는 벡터 레지스터에 기준값을 채움
    • 'A'
    • 'Z'
    • 'a' - 'A'
  • 입력 문자 벡터 c를 'A', 'Z'와 비교해 각각 64비트 마스크를 만듦
    • c >= 'A'인 위치
    • c <= 'Z'인 위치
  • 두 마스크를 _kand_mask64()로 결합해 대문자 위치만 표시하는 is_upper 마스크를 만듦
  • 마지막으로 _mm512_mask_add_epi8()를 적용함
    • is_upper가 false인 바이트는 원래 c를 유지함
    • is_upper가 true인 바이트는 c + ('a' - 'A')가 됨

긴 문자열과 짧은 문자열 처리

  • 긴 문자열의 대부분은 일반적인 비정렬 벡터 load/store로 처리함
    • _mm512_loadu_epi8()
    • tolower64()
    • _mm512_storeu_epi8()
  • 짧은 문자열과 긴 문자열의 마지막 남은 조각에는 마스크드 비정렬 load/store를 사용함
  • 마스크는 낮은 쪽 len비트만 켜진 형태로 만듦
    • uint64_t len_bits = (~0ULL) >> (64 - len)
    • _cvtu64_mask64(len_bits)로 SIMD 마스크 레지스터에 올림
  • _mm512_maskz_loadu_epi8()는 마스크가 꺼진 위치의 목적지 레지스터를 0으로 채움
  • _mm512_mask_storeu_epi8()는 마스크가 켜진 위치만 저장함
  • 이 방식이 작은 문자열 조각을 빠르게 처리하는 핵심임

벤치마크 조건과 비교 대상

  • 벤치마크는 Clang 16, Debian 11, AMD Ryzen 9 7950X에서 실행함
  • 측정 대상은 약 1MiB 복사이며, 청크 길이는 1바이트부터 1KiB까지 바꿈
  • 소스와 목적지 문자열의 정렬 차이를 반영하기 위해 각 문자열 사이에 몇 바이트를 두었고, 이 바이트들은 1MiB 측정량에 포함하지 않음
  • Ryzen 9 7950X의 L2 캐시는 코어당 1MiB라서, 각 테스트 실행은 L3 캐시까지 넘어갈 것으로 예상함
  • 각 함수는 인라이닝과 코드 이동의 간섭을 피하려고 별도로 컴파일함
    • 실제 코드에서는 인라이닝을 막기보다 장려하는 편이 더 가능성이 높음

결과: tolower64의 매끄러운 성능

  • 분홍색 tolower64는 전반적으로 테스트 함수들 중 가장 빠른 축에 꾸준히 가까움
    • 길이가 65바이트일 때 두 번째 벡터로 넘어가면서 약간 떨어짐
    • 빠르게 상승하고 깊은 성능 골이 없어, 마스크드 load/store가 짧은 문자열 조각 처리에 효과적임을 보여줌
  • 초록색 copybytes64는 AVX-512를 비슷한 방식으로 쓰는 memcpy 버전임
    • tolower64보다 많이 빠르지는 않음
    • 최신 Clang은 이 함수의 의미를 인식해 완전히 다시 작성하므로 Clang 11로 컴파일함
  • 주황색 copybytes1는 바이트 단위 memcpy 버전임
    • Clang 11로 컴파일함
    • 256바이트보다 작은 문자열 조각에서 Clang 11의 자동 벡터화 휴리스틱이 상대적으로 좋지 않음을 보여줌
  • 빨간색 tolower는 <ctype.h>의 표준 tolower()를 호출하는 기준선이며 매우 느림
  • 보라색 tolower1은 Clang 16으로 컴파일한 바이트 단위 tolower()임
    • Clang 16의 자동 벡터화는 Clang 11보다 훨씬 좋아짐
    • 손으로 작성한 버전보다 느리고 훨씬 복잡한 코드를 생성함
    • 짧은 문자열 조각 처리가 tolower64만큼 좋지 않아 성능 그래프가 뾰족하게 흔들림
  • 갈색 tolower8은 이전 글의 SWAR tolower()임
    • Clang이 자동 벡터화를 시도하지만 함수가 복잡해 결과가 좋지 않음
    • Clang 16으로 컴파일했지만 Clang 11 스타일의 256바이트 성능 절벽이 나타남
  • 파란색 memcpy는 glibc의 memcpy를 호출함
    • 처음에는 빠르지만 copybytes64 속도의 절반 정도로 떨어지는 구간이 있음
    • 원인은 확인하지 못함

결론과 코드

  • AVX-512-BW는 문자열, 특히 짧은 문자열을 다루는 데 매우 적합함
  • Zen 4에서는 매우 빠르고, intrinsic 함수도 비교적 사용하기 쉬움
  • 가장 눈에 띄는 특징은 매끄러운 성능임
    • 자동 벡터화가 작은 문자열 조각에서 스칼라 코드로 전환하며 겪는 성능 골이 거의 보이지 않음
  • ARM SVE 지원 장비나 RISC-V Vector extension 장비에 편리하게 접근할 수 없어 두 확장은 자세히 조사하지 못함
  • 코드는 웹 사이트의 git 저장소에서 볼 수 있음

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • “unsafe read beyond of death” 트릭은 하드웨어에서 허용되더라도 Rust와 LLVM 메모리 모델에서는 정의되지 않은 동작으로 간주됨
    다른 정의되지 않은 동작과 마찬가지로 컴파일러는 최적화 과정에서 “그런 일은 일어나지 않는다”고 가정할 수 있어 예상 밖 결과가 나올 수 있고, 우회하려면 인라인 어셈블리를 써야 함
    https://github.com/ogxd/gxhash/issues/82

    • 이런 경우에 어셈블리 아닌 선택지가 있으면 좋겠음
      “할당 범위를 넘은 값은 미지정 요소로 읽고, 하드웨어가 싫어할 때만 정의되지 않은 동작” 같은 로드는 지원하기 어렵지 않아 보이며, 내부적으로 해당 어셈블리 호출의 별칭이어도 충분함
      더 나아가 malloc, 스택, 상수 등 모든 할당 뒤에 최소 64바이트 정도의 fault 없는 주소가 보장되면 좋겠지만, 여러 구성요소의 협력이 필요해 훨씬 복잡함
      커스텀 할당자에서는 사소한 일이지만, 그 경우 커스텀 힙 밖의 데이터에는 SIMD 코드를 쓰기 어렵고 아주 작은 세그폴트 가능성에 묶이게 됨
      sanitizer나 Valgrind도 여전히 쓸모가 있음. 범위를 넘은 값은 미정 값으로 추적할 수 있고, 실제 사용 시 오류를 낼 수 있기 때문
    • 하드웨어 수준에서도 정말 맞는 말인지 의문임
      매핑되지 않은 페이지나 보호된 메모리로 읽으면 어떻게 되는지 궁금하고, 코드를 안 봐서 정렬 보장이 이를 피하는지는 모르겠음
    • “정의되지 않은 동작이면 컴파일러가 그런 일이 없다고 가정할 수 있다”는 설명은 틀렸음
      정의되지 않은 동작은 C 표준의 전문 용어라 일반화 자체가 이상하고, ANSI C는 그런 가정을 명시적으로 허용하지 않으며 ISO C도 더 열려 있긴 하지만 그 가정을 구체적으로 정당화하지 않음
      “UB = 일어날 수 없다고 가정”이라는 식의 설명은 상당히 부정직한 공포 조장에 가깝다고 봄

  • 글의 깔끔하고 성능 좋은 코드를 보니 AMD의 AVX512 구현과 Intel의 예정된 AVX10이 어떻게 경쟁할지 궁금해짐
    AVX10의 핵심은 Intel의 P코어/E코어 상황을 해결하는 데 있어 보이는데, AMD는 상황에 따라 Zen5의 전체 폭 구현이나 Zen4·Zen5 모바일의 256비트 2회 처리 방식을 쓰면서 API는 매끄럽게 유지하는 더 나은 접근을 택한 듯함
    글의 큰 성능 향상도 모두 Zen4 코어에서 나온 결과이고, AVX512는 장점이 많기 때문에 Intel이 이를 시장 세분화로 지나치게 제한해 범용 클라이언트 코드에서 채택을 사실상 막은 점이 답답함

    • Intel이 앞으로 출시하는 모든 CPU에 AVX10/256을 실제로 넣는다면 결국 보급성 때문에 이길 것임
      시장은 CPU별 코드 경로 분기를 반복해서 거부해 왔고, 실제로 중요한 SIMD 구현은 최저 공통분모임
      AVX10.1/256과 AVX512VL은 공통 부분집합이 있으니 시간이 충분히 지나 대부분의 CPU가 지원하게 되면 사람들이 그 부분을 목표로 삼게 될 것임
      AMD는 AVX512를 지원하도록 업데이트된 일부 벤치마크 앱에서 쉬운 승리를 계속 얻겠지만, Intel이 AVX10 계획을 유지한다면 AMD도 결국 AVX512 호환성을 유지하면서 AVX10/256을 효율적으로 지원하기 위해 2회 처리 SIMD 파이프를 전면적으로 쓸 가능성이 큼
      Intel은 지난 10년간 나쁜 선택을 많이 했지만, 명령어 집합으로 시장을 쪼갠 것은 최악 중 하나였음. 최신 혁신의 추진력과 관심을 스스로 죽인 셈이고, 폭 자체보다 마스크 연산 같은 기능이 훨씬 중요하니 전 라인업에 AVX10/256을 넣길 바람
    • Zen 4의 AVX512 구현은 2회 처리(double-pumped)가 아니며, 기술 기자들이 그렇게 부르는 걸 멈춰야 함
      그 말은 특정한 의미가 있는데 실제 동작과 맞지 않음
      Zen 4는 ZMM 레지스터 연산을 여러 마이크로연산으로 디코드해 빈 256비트 유닛에 스케줄링할 뿐이고, 512비트 전체 폭 셔플은 비싼 에뮬레이션을 피하기 위한 전용 하드웨어로 특별 처리함
      그래서 4개의 256비트 SIMD 유닛을 가진 Zen 4도 강력한 2×512비트 코어처럼 동작하며, 이 구현은 결코 저렴한 방식이 아니고 지금까지 소비자용 하드웨어에서 가장 좋은 형태일 가능성이 큼
    • Intel이 E코어에 2회 처리 AVX512를 넣어 이 문제를 해결하지 않는 이유를 모르겠음. 아니면 데스크톱에는 원래 그래야 하듯 P코어만 있는 CPU를 만들면 됨
      이미 수년간 고칠 시간이 있었고, AMD가 지원해도 시장 점유율 때문에 채택이 안 되는 점이 짜증나며, AVX10은 안타깝게도 Intel이 세상을 더 오래 붙잡아 두게 만들 것 같음
      데스크톱에서는 더 나은 코어, 더 많은 코어, 넓은 SIMD·float16·gather/scatter 같은 유용한 기능을 여는 잘 표준화된 명령어 집합을 보고 싶고 AMD는 꽤 잘하고 있음
      반면 Intel은 괜찮은 코어 옆에 약한 코어를 붙이고, 약한 코어에 맞추려고 괜찮은 코어를 제한하며, 여러 세대 동안 같은 코어 수의 CPU를 내고, 약한 코어로 코어 수가 많은 것처럼 보이게 하며, 유용한 공통 집합이 생기기 어려울 만큼 너무 많은 명령어 변형을 내고, 자기들이 약속해 보이던 명령어 지원도 버림
      데스크톱 제조사 선호는 90년대 Intel, 2000년대 초 AMD, 2000년대 후반과 2010년대 Intel, 지금은 다시 AMD였음. Intel이 상대를 방해하는 것 말고 다시 기반을 얻으려면 뭘 할지 궁금하고, 경쟁이 계속되어야 한쪽이 너무 안주하지 않음

  • 재미 삼아 보면 좋은 자료: http://www.unicode.org/Public/3.1-Update1/CaseFolding-4.txt

    • 이런 것도 있음: 독일어 ß를 대문자로 바꾸면 문자열 길이가 바뀜
      예를 들어 "straße".upper()는 'STRASSE'가 됨
      또 로케일을 지정하지 않으면 튀르크어권의 점 없는 i를 대문자/소문자로 왕복 변환할 때 'ı'.upper().lower()가 'i'가 되어 망가짐
    • 다행히 이 코드는 DNS 작업에서 나온 것이라 ASCII 전용이라 그런 복잡성을 다룰 필요가 없음
      ASCII 대소문자 비구분 프로토콜은 여럿 있고, 많은 서버의 핫 경로에서 자주 나타남
    • 내부적으로 ID처럼 쓰는 문자열과 사람이 입력한 텍스트는 다름
      전자는 보통 8비트 인코딩의 순수 ASCII를 쓰면 되지만, 후자는 복잡해짐
      DNS 주소가 쉬운 예인데, 기술적으로는 거의 모든 Unicode를 담을 수 있지만 실제 DNS 해석에는 매우 제한된 ASCII 부분집합으로 변환되고, 그 해석 과정은 대소문자를 구분하지 않음
      물론 Unicode의 모든 문자 체계를 지원하면서 식별자가 대소문자를 구분하지 않는 프로그래밍 언어 같은 것도 있음. 그런 걸 다루고 있다면 애도를 표함
    • 독일어 maße가 MASSE로 바뀌는 예와 관련해, 독일어에는 대문자 Eszett인 ẞ도 있음
      아직 널리 배포되지는 않았고 지원 글꼴도 적지만, 이론적으로는 이제 존재함

  • 글의 “마스크 덧셈” 설명이 잘못된 것 아닌가 싶음
    is_upper가 false일 때 더하고 true일 때 그대로 복사해야 하는 것 아닌지 의문임

    • 아, to_upper 변수명이 거꾸로라서 to_lower라고 불러야 한다는 걸 뒤늦게 깨달음
      헷갈리는 부분을 짚어줘서 고맙고, 글과 코드를 고쳤음
    • 이 연산은 tolower임
      대문자 A는 0x40, 소문자는 0x60이므로 0x20 더하기는 is_upper가 true일 때 일어나야 함

  • 이런 SWAR 최적화는 문자열이 8바이트 주소에 정렬되어 있을 때만 유용한 경우가 많음
    정렬되지 않은 문자열에 SWAR 알고리즘을 적용하면 원래 알고리즘보다 느려지는 일이 흔함
    시작 부분을 정렬 주소까지 처리하고, 정렬된 본문을 처리하고, 8바이트 미만 꼬리를 처리하는 3단계로 쪼개면 명령어가 더 늘어남
    Go에서 utf8.IsValid가 더 빠르다는 잘못된 주장과 비슷한 사례 및 벤치마크가 여기 있음: https://github.com/sugawarayuuta/charcoal/pull/1

    • AVX-512와 ARM SVE의 마스크 SIMD 연산은 그 문제를 해결하려고 나온 것임
      메모리 연산은 항상 정렬되고 전체 벡터 크기로 하되, 유효한 요소에만 마스크를 걸 수 있음
      마스크된 벡터 메모리 연산이 정렬되지 않았고 매핑되지 않았거나 보호된 페이지를 걸치더라도, 해당 lane이 마스크로 꺼져 있으면 fault가 나지 않음
      strlen()처럼 길이를 미리 모르는 연산을 위해 fault가 날 첫 요소 직전에서 벡터 길이를 줄이는 특수 load 명령도 있음

  • 마스크 덧셈이 멋져 보임. .NET intrinsic에서 AVX512의 마스크 레지스터를 직접 조작할 수 있으면 좋겠지만, 지금은 “인식되는 관용구”에 의존해야 함
    GCC가 만든 작성자 핵심 루프를 uiCA(CQA/MAQAO)로 Ice Lake 기준 분석하면 약 32B/cycle이 나오고, 3GHz로 환산하면 메모리 병목이 없다고 가정할 때 거의 96GiB/s가 됨. 물론 이런 알고리즘에서는 메모리 접근이 늘 병목임
    다만 최적 활용에 아주 가깝지는 않아 보이고, Clang을 쓰면 더 잘 풀린 언롤 결과와 나은 명령어 선택으로 42.67B/cycle까지 나옴. L2 캐시도 그런 처리량을 유지하긴 어려울 것 같지만, 중간 길이 문자열의 대소문자 변환이 화면 빛이 각막에 닿는 시간쯤에 끝난다는 건 흥미로움
    몇 달 전 C#으로 비슷한 UTF-8 내 ASCII 대문자/소문자 변환을 구현했음: https://github.com/U8String/U8String/blob/main/Sources/U8Str...
    짧은 문자열이 대부분의 코드베이스를 지배하므로 벡터화 길이 미만을 위한 언롤 변환이 중요하고, switch는 점프 테이블과 branchless fall-through로 컴파일됨
    지금은 256비트까지만 쓰는데, Zen 3나 4처럼 256×4 SIMD 유닛만 있는 경우 이미 포화되기 때문임. C 버전과 나란히 비교한 예는 여기 있음: https://godbolt.org/z/eTGYhTPan
    AVX512에서는 vpternlogd로 3개 명령어 변환도 가능할 것 같고, AVX512 하드웨어를 쓸 수 있었을 때 .NET은 256비트 폭 + AVX512VL에서 그렇게 최적화했지만 지금은 이상하게 512비트 폭으로 재현이 안 됨
    switch dispatch 쪽의 실패한 SWAR 시도도 보일 텐데, 글의 라이선스가 궁금함. 테스트 스위트를 통과한다면 가져다 쓰고 싶음

    • Clang과 GCC는 intrinsic 처리 방식이 다르고, 특히 AVX-512 명령에서 Clang이 Intel 가이드의 지정 opcode와 알고리즘에서 벗어날 가능성이 GCC보다 큼
      두 컴파일러의 구조를 생각하면 이해는 되지만 결과가 개선일 때도 있고 손해일 때도 있음
      몇 년 전 둘 다로 컴파일되어야 하는 고도로 벡터화된 프로젝트를 하다가, C 참조 버전과 함께 특정 타깃용 인라인 어셈블리와 .S 파일을 저장소에 유지하게 됐음
      Makefile이 지저분해지고 테스트 스위트에 벤치마크까지 넣어야 해서 유지보수 부담이 컸고, 그래서 intrinsic을 자동 벡터화보다 나은 저수준 수단으로 쓰는 일은 아주 신중해야 한다는 결론에 이름
      예: https://godbolt.org/z/T4Pjhrz5d 에서 GCC 출력은 예상대로였지만 Clang 출력은 놀라웠고 실제로 더 느렸음. 루프로 돌리면 uiCA 기준 GCC 4사이클 대비 7사이클이며, brute-force 알고리즘에서 이 함수가 수십억 번 실행되는 실제 앱 벤치마크에서도 드러났음
      LLVM 코드베이스를 들여다보니 Clang 16이 내부 리팩터링 때문에 일부 마스크 AVX-512 명령을 아예 내지 못할 수도 있다는 문제도 봤던 기억이 있음
    • 분석이 아주 유익함
      가능한 최고 성능을 노린 것은 아니고, 처음에는 되는지만 보려 했는데 첫 시도가 꽤 잘 나온 것이 보너스였음
      주된 관심사는 벡터 레지스터보다 짧은 문자열과 처리량 그래프의 골짜기를 없애는 것임
      블로그 글 끝의 코드 링크를 따라가면 라이선스 정보가 있고, BIND용으로 원래 작성된 MPL-2.0 부분을 제외하면 0BSD 또는 MIT-0임
    • 큰 어셈블리 덩어리만 봐서는 잘 안 보이지만, Clang은 (x >= 'a' && x <= 'z')를 (x - 'a') < ... 형태로 다시 써서 명령어 하나를 줄임
      이상한 opcode 인코딩 때문에 레지스터 load까지 줄어드는 경우도 있음

  • swar가 뭔지 모르겠음

    • “SIMD Within A Register”의 약자임
      보통 레지스터 하나에 여러 항목을 packed해서 명시적인 SIMD 명령 없이도 사실상 SIMD처럼 쓰는 기법을 뜻함
      예를 들어 64비트 레지스터에 31비트와 32비트 숫자를 넣고 carry용 1비트를 남기면, 64비트 덧셈 하나로 두 덧셈을 할 수 있음
      게임에서는 RGB(A) 값을 32비트 정수에 packing해 그래픽에 이런 트릭을 써 왔고, ScummVM도 32비트 값 안의 16비트 RGB 픽셀 2개, 총 6개 성분을 보간하는 코드가 있음: https://github.com/scummvm/scummvm/blob/master/graphics/scal...
    • 레지스터 안의 SIMD라는 뜻임

  • Unicode가 등장한 뒤 대문자와 소문자 개념은 늪이 됐음
    제대로 하려면 많은 데이터가 필요함
    ASCII tolower 실행 속도에 제때 끝나는지가 달린 작업을 하고 있다면, 뭔가 판을 바꾸고 전제 조건을 바꾸는 편이 나음

  • 예전에 이미지 주위에 검은 테두리를 넣어 SIMD의 버퍼 너머 읽기 문제를 완전히 피한 적이 있음
    아주 잘 작동했고 속도 면에서 일부 OpenCV 구현을 이길 수 있었지만, 항상 그렇게 입력을 완전히 통제할 수 있는 것은 아님

  • 이런 식으로 해봤는지 궁금함. 자동 벡터화 결과가 꽤 깔끔해 보임
    https://godbolt.org/z/1c5joKK5n

    • 그건 기본적으로 tolower1과 같음. 그래프 아래 bullet들을 보면 됨
답변달기