처음부터 설계하는 SIMD 알고리듬

 (mcyoung.xyz)
2P by GN⁺ | ★ favorite | 댓글 1개
  • Rust의 std::simd로 만든 vb64 base64 코덱은 절차적 루프를 그대로 벡터화하기보다, 데이터 배치와 연산 흐름을 회로처럼 다시 설계해야 빠르고 이식 가능한 SIMD 코드가 됨
  • 핵심 최적화는 분기와 메모리 접근으로 인한 stall을 줄이는 데 있으며, 비교·마스크·select·shuffle로 입력과 무관하게 같은 연산을 수행하는 branchless 구조를 만듦
  • base64 디코딩에서는 ASCII 문자를 sextet으로 바꾸기 위해 byte >> 4와 / 보정을 이용한 perfect hash를 만들고, SIMD 벡터 안의 lookup table과 shuffle로 offset을 찾음
  • 네 개의 6비트 sextet을 세 바이트로 패킹할 때는 lane을 u16으로 키워 shift한 뒤, low/high byte를 분리하고 rotate_lanes_left와 OR로 인접 lane의 바이트 조각을 합침
  • 벤치마크에서는 -Zbuild-std, -Ctarget-cpu=native, N = 32 조합과 remainder 로딩 최적화 후 crates.io의 baseline base64 구현 대비 거의 전 구간에서 약 2배 성능을 보임

SIMD가 필요한 물리적 배경

  • 컴퓨터 성능 향상은 이론적 CS만이 아니라 물리적 제약과 직접 연결됨
  • Moore’s law는 2023년 기준으로 여전히 유지되는 것으로 보이지만, 지난 15년 사이 Dennard scaling 효과가 무너지며 더 조밀한 트랜지스터가 전력 소모 밀도 증가로 이어짐
  • 클럭 주파수를 계속 올리기 어려워진 뒤, 2000년대 초반부터 성능 향상의 주요 방향은 더 많은 코어를 쓰는 쪽으로 이동함
  • 멀티스레딩은 코어 간 협력이 필요해 동기화 비용이 생기며, 점프·가상 호출·동기화 같은 제어 흐름은 stall을 일으킴
  • stall의 주요 원인은 두 가지임
    • 분기: if, 루프, 함수 호출, 함수 반환, C의 switch 같은 제어 흐름
    • 메모리 작업: load/store, 특히 캐시에 친화적이지 않은 접근

절차적 코드와 명령어 수준 병렬성

  • 현대 CPU 코어는 코드를 한 줄씩 실행하지 않고, 서로 의존하지 않는 연산을 동시에 발행함
  • a = x + y와 b = x ^ y처럼 서로 의존하지 않는 연산은 add와 xor 회로를 동시에 사용할 수 있음
  • 이런 방식이 명령어 수준 병렬성이며, 이를 방해하는 의존성은 data hazard로 불림
  • CPU가 functional unit을 더 잘 포화할수록 단위 시간당 더 많은 연산을 처리함
  • 분기는 다음 명령어를 가져오기 전에 조건 계산을 기다려야 하고, 메모리 작업은 데이터가 CPU까지 물리적으로 도착해야 하므로 stall이 발생함
  • GPU는 이미지를 벡터 형태의 픽셀로 다루고 지역성이 높은 연산을 많이 수행하므로, 배치 연산과 제한된 제어 흐름에 맞춰 설계된 SIMD 머신에 가까움
  • SIMD는 single instruction, multiple data로, 하나의 명령이 여러 데이터 lane에 병렬 연산을 수행하는 방식임

lane 단위 사고방식

  • SIMD와 vector는 자주 같은 의미로 쓰이며, SIMD 명령의 기본 단위는 고정 크기 숫자 배열인 vector임
  • vector의 각 구성 요소는 lane이라고 불림
  • SIMD 벡터는 레지스터에 들어가야 하므로 대체로 작음
    • 예시 환경의 최대 벡터 폭은 256비트
    • 이는 u8x32의 32바이트 또는 f64x8의 double 4개에 해당함
  • 작은 벡터라도 파이프라인 포화 부담을 4배 줄일 수 있으면 그만큼 latency 개선으로 이어질 수 있음

popcnt로 보는 분할 정복

  • 가장 단순한 벡터 연산은 bitwise and/or/xor임
  • 일반 정수도 bitwise 연산 관점에서는 1비트 lane의 벡터로 볼 수 있음
    • i32는 이 관점에서 i1x32와 같음
  • popcnt는 정수 안의 1비트 개수를 세는 연산이며, i32를 i1x32로 보면 reduce 연산임
  • 32개 비트를 배열로 꺼내 더하는 단순 구현은 나쁜 코드를 만들 수 있음
  • 더 나은 방식은 인접한 비트 쌍을 더하고, 다시 쌍의 쌍을 더하는 식으로 lane 폭을 키우며 합산하는 것임
    • 0x55555555, 0xaaaaaaaa 마스크로 짝수/홀수 비트를 분리
    • shift로 lane을 맞춘 뒤 더함
    • 이후 2비트, 4비트, 8비트, 16비트 단위로 반복
  • 이 구현은 popcnt 명령으로 최적화되지는 않지만, 그런 명령이 없는 시스템에서 작고 빠른 코드가 됨
  • u64에도 reduction 단계 하나만 더 추가하면 적용 가능하며, 전체 u64 덧셈이 필요하지 않음
  • 이런 분할 정복 접근은 SIMD 프로그래밍의 핵심 패턴임

SIMD 명령 집합의 주요 도구

  • 실제 SIMD 벡터는 스칼라보다 더 복잡한 의미를 제공하며, 느린 제어 흐름을 대체하기 위한 기능이 특히 중요함
  • 사용 가능한 명령은 아키텍처에 크게 의존함
    • x86의 많은 고성능 코어는 AVX2를 구현함
    • AVX2는 256비트 ymm 벡터를 제공함
    • 레지스터 자체에는 lane 수가 없고, 명령이 lane 해석 방식을 정함
    • 예를 들어 vpaddb는 ymm을 i8x32로 해석함
  • 일반적으로 사용할 수 있는 연산은 다음과 같음
    • bitwise 연산: lane 폭이 항상 1비트로 암묵적임
    • lane-wise 산술: 덧셈, 뺄셈, 곱셈, 나눗셈, 정수 shift, min/max 등
    • lane-wise 비교: m[i] = a[i] < b[i] 같은 mask vector를 생성함
    • select: mask를 이용해 두 벡터 중 lane별로 값을 선택함
    • shuffle/swizzle: 한 벡터를 lookup table처럼 보고 index 벡터로 lane을 재배치함
  • mask vector의 true/false는 보통 all-ones 또는 all-zeros 비트 패턴을 사용함
  • 비교와 select는 SIMD 코드가 branchless 상태를 유지하도록 돕는 핵심 도구임
  • branchless 코드는 입력과 관계없이 같은 연산을 수행하고, x * 0 = 0, a ^ b ^ a = b 같은 성질로 불필요한 결과를 버림

shuffle로 데이터 위치 맞추기

  • shuffle은 SIMD에서 데이터가 “올바른 위치”에 오도록 만드는 핵심 도구임
  • broadcast 또는 splat은 모든 lane이 같은 scalar를 갖는 벡터를 만들며, [0, 0, ...] index shuffle로 표현할 수 있음
  • interleave 또는 zip/pack은 두 벡터 a, b의 lane을 번갈아 배치함
    • c = [a[0], b[0], a[1], b[1], ...]
    • shuffle2로 구현할 수 있음
  • deinterleave 또는 unzip/unpack은 interleave의 반대임
  • rotate는 b[i] = a[(i + j) % n] 형태로 lane을 회전시키며, 이것도 shuffle임
  • SIMD 프로그래밍에서는 정수보다 큰 데이터 블록을 다양한 크기의 작은 블록으로 재해석하고 재배치하는 일이 많음

intrinsics, target feature, portable SIMD

  • SIMD에서 사용할 수 있는 연산은 아키텍처와 instruction set extension에 따라 달라짐
  • x86에는 ARM에 없는 연산이 있을 수 있고, Intel AVX-512처럼 같은 벤더 안에서도 고급 서버 칩에만 제공되는 확장도 있음
  • 툴체인은 이런 확장을 target feature로 일반화함
    • Linux의 lscpu는 CPU가 인식하는 feature를 보여줌
    • LLVM은 feature 설정에 따라 명령어 선택을 다르게 함
    • +avx2가 있어야 LLVM이 ymm 사용 코드를 낼 수 있음
  • -march=native나 -Ctarget-cpu=native는 빌드한 머신에 맞는 좋은 코드를 만들 수 있지만, 다른 프로세서로의 이식성은 떨어질 수 있음
  • 런타임 feature detection은 CPU가 지원하는 기능을 확인해 어떤 함수 버전을 호출할지 결정하는 방식이며, 암호화 라이브러리처럼 다양한 장치에 배포되는 코드에서 사용됨
  • C++의 SIMD 코드는 보통 _mm256_cvtps_epu32 같은 intrinsics를 사용함
    • 특정 instruction set의 저수준 연산을 나타냄
    • 반드시 단일 명령으로 매핑되지는 않음
    • 컴파일러가 병합, 중복 제거, 명령어 선택 최적화를 수행할 수 있음
  • 여러 instruction set에 대해 비슷한 코드를 반복해서 작성하게 되면 assembly보다 유지보수 이점이 크지 않을 수 있음
  • portable SIMD 라이브러리는 라이브러리 수준에서 일부 명령어 선택을 처리하고, 나머지는 컴파일러에 맡기는 접근임
  • vb64 구현은 Rust의 portable SIMD가 경쟁력 있는 코드를 생성하는지 확인하기 위한 실험임

base64 디코딩을 SIMD로 바꾸기

  • base64는 임의의 바이너리 데이터를 ASCII로 인코딩하는 방식임
  • 입력 바이트열을 비트 벡터로 보고 6비트 chunk인 sextet으로 나눔
  • sextet 값은 다음 문자로 매핑됨
    • 0..25 → 'A'..'Z'
    • 26..51 → 'a'..'z'
    • 52..61 → '0'..'9'
    • 62 → +
    • 63 → /
  • base64에는 여러 변형이 있지만 복잡도의 대부분은 공통임
  • 주의할 점은 두 가지임
    • base64는 바이트 안의 비트가 big endian인 형식임
    • 입력 길이가 4로 나누어떨어지지 않을 수 있으며, 원칙적으로는 = padding으로 4의 배수에 맞추지만 padding이 올바르지 않은 메시지도 처리할 수 있음
  • decoded length는 input / 4 * 3에 input % 4에 따른 나머지 길이를 더해 계산함

branchless를 향한 기본 리팩터링

  • 단순 base64 디코더에는 여러 분기가 있음
    • 입력을 chunk로 순회하는 루프
    • chunk 내부 byte 루프
    • ASCII 문자별 match
    • 오류 시 return Err
    • decoded_len 내부 match
    • Vec::extend_from_slice와 allocator 호출 가능성
  • 최적화 지침은 모든 분기를 제거하는 것임
  • decoded_len의 match는 input % 4 값 0, 1, 2, 3을 0, 1, 1, 2로 매핑함
  • 이를 mod4 - mod4 / 2로 바꾸면 branchless 버전이 됨
  • LLVM은 원래 match를 switch table로 접을 수 있지만, 이 영역에서는 불필요한 메모리 접근이 성능을 낮춤

가장 뜨거운 루프 분리

  • SIMD의 강점은 한 번에 많은 데이터를 처리해 루프를 강하게 unroll하고 branchless에 가깝게 만드는 데 있음
  • hot loop의 목표는 최대 4바이트를 읽고 최대 3바이트 디코딩 결과를 만들며, 문법 오류 여부도 알려주는 것임
  • 활용할 수 있는 사실은 세 가지임
    • 출력 길이는 branchless decoded_len()으로 계산 가능함
    • 잘못된 base64는 매우 드문 경로로 보고, 오류 위치가 필요하면 사후에 다시 스캔할 수 있음
    • base64에서 A는 0이므로 truncated chunk를 A로 padding해도 값이 바뀌지 않음
  • decode_hot()은 네 입력 바이트를 처리하고, 디코딩 결과와 성공 여부 bool을 반환하는 형태로 분리됨
  • Option<[u8; 3]> 대신 bool을 따로 반환하면 이후 if !ok 분기를 제거하기 쉬움
  • SIMD 버전에서는 Simd<u8, 4>를 입력으로 받고, 출력도 power-of-two lane 수에 맞춰 Simd<u8, 4>로 둠
    • 실제로 필요한 출력은 3바이트
    • 마지막 lane은 사용하지 않음

ASCII를 sextet으로 바꾸는 방법

  • ASCII 문자를 sextet으로 바꾸는 match의 대부분은 byte - C 형태로 표현 가능함
    • 'A'..'Z' → byte - 'A'
    • 'a'..'z' → byte - 'a' + 26
    • '0'..'9' → byte - '0' + 52
    • '+' → byte - '+' + 62
    • '/' → byte - '/' + 63
  • lane별 offset 벡터를 만들고 ascii - offsets를 수행하면 됨
  • 첫 접근은 compare-and-select임
    • A-Z, a-z, 0-9, +, /에 대한 mask를 만듦
    • mask가 하나도 선택되지 않은 lane은 invalid로 판단함
    • 각 mask에 대응 offset을 splat하고 OR로 합침
  • 이 방식은 우아하고 경쟁력 있는 코드를 만들 수 있지만, 비교가 총 8개 필요하고 살아 있는 값이 많아 register pressure가 생길 수 있음

SIMD hash table과 perfect hash

  • A-Z, a-z, 0-9의 byte 범위는 각각 0x41..0x5b, 0x61..0x7b, 0x30..0x3a이며 high nibble이 다름
  • +와 /는 0x2b, 0x2f이므로 byte >> 4만으로 대부분 구분 가능함
  • /인 경우 하나를 빼면 범위에 대한 perfect hash가 됨
  • (byte >> 4) - (byte == '/')의 매핑은 다음과 같음
    • A-Z → 4 또는 5
    • a-z → 6 또는 7
    • 0-9 → 3
    • + → 2
    • / → 1
  • 이 값은 작아서 offset lookup table을 SIMD 벡터 안에 넣고, shuffle로 lookup할 수 있음
  • 이 perfect hash 아이디어는 GitHub issue의 익명 사용자가 제시함
  • Simd::swizzle_dyn()은 index 배열과 lookup table 길이가 같아야 하는 제약이 있음
  • perfect hash 방식에서는 sextet 계산 과정에서 validation을 부수효과로 얻지 못하므로, 같은 GitHub issue의 exact bloom filter를 이용해 byte 유효성을 검사함
  • 구현 예시는 vb64의 simd.rs에 있음

네 sextet을 세 바이트로 패킹하기

  • 네 개의 6비트 sextet을 세 바이트로 합치는 단계는 더 까다로움
  • 특정 입력 sextet 하나를 all-ones로 두고 출력에서 비트가 어디로 이동하는지 확인하면 배치 관계를 추적할 수 있음
  • byte 단위 shuffle만으로는 충분하지 않음
    • 이동해야 하는 대상이 바이트 조각임
    • shift만으로도 부족함
    • overshift된 비트가 인접 lane으로 이동해야 함
  • 해결책은 lane을 더 크게 만드는 것임
  • sextets를 u16 벡터로 cast한 뒤 lane별로 shift함
    • input[0]은 2비트 shift
    • input[1]은 4비트 shift
    • input[2]은 6비트 shift
    • input[3]은 8비트 shift로 조정
  • shift 결과에서 low byte와 high byte 벡터를 분리함
  • hi.rotate_lanes_left::<1>()로 high byte 쪽 조각을 인접 lane에 맞춘 뒤 lo | hi_rotated로 합침
  • 이 방식은 hardware primitive를 적극적으로 활용하기 때문에 코드가 작고 효율적임

lane 수 확장과 garbage lane 제거

  • Simd<u8, 4>는 x86의 최소 128비트 벡터 레지스터보다도 작으므로, decode_hot()을 lane 수 N에 대해 generic하게 만듦
  • LaneCount<N>: SupportedLaneCount 제약으로 작은 power-of-two lane 수를 보장함
  • lookup table과 shift table은 tiled() helper로 반복 패턴 벡터를 만듦
  • N = 4에서는 마지막 lane의 garbage 값을 무시하면 됐지만, N이 커지면 every fourth lane에 garbage가 섞임
  • 이를 제거하기 위해 shuffle을 사용함
    • 원하는 관계는 shuffled[i] = output[i + i / 3]
    • 네 번째 인덱스마다 건너뛰어 garbage lane을 삭제함
    • overflow되는 부분은 최종 출력 벡터의 상위 1/4이므로 무시됨
  • 이렇게 하면 decode_hot::<32>()로 32개의 base64 byte를 병렬 디코딩할 수 있음

outer loop 최적화

  • decode()도 내부 lane 수 N에 대해 generic하게 바꿈
  • 남아 있는 비용은 다음과 같음
    • for chunks in ...의 길이 비교 분기
    • [T]::copy_from_slice의 variable-length memcpy
    • 매 loop iteration의 ok 분기
    • Vec::extend_from_slice의 allocator 호출 가능성과 또 다른 memcpy
  • 출력 길이를 알고 있으므로 out.reserve(final_len + N / 4)로 미리 공간을 확보함
  • 추가로 slop 공간을 둬서 variable-length memcpy 대신 full SIMD store를 수행함
  • 각 iteration은 전체 SIMD 벡터를 쓰고, 다음 write는 3/4 * N만큼 이동해 이전 garbage byte를 덮어씀
  • 마지막 garbage byte는 최종 Vec::set_len()에 포함되지 않으므로 삭제된 것처럼 처리됨
  • if !ok 때문에 early return하더라도 set_len()으로 commit하지 않았으므로 out은 수정되지 않은 상태로 남음

오류 처리를 hot loop 밖으로 미루기

  • 매 iteration마다 if !ok로 return하지 않고, error |= !ok로 누적함
  • 최종 set_len() 직전에 한 번만 오류 여부를 확인함
  • 대부분의 base64 blob이 valid라는 전제에서, 오류 경로는 hot loop 밖으로 밀려남
  • 문법 오류가 있어도 이후 SIMD 연산이 임의로 misbehave하지 않기 때문에, garbage write는 commit되지 않고 사라짐
  • 이후 Vec::push() 같은 호출이 같은 버퍼 영역을 덮어쓸 수 있음

unroll and jam과 remainder 처리

  • copy_from_slice의 variable-length memcpy를 줄이기 위해 unroll and jam을 적용함
  • 루프를 두 부분으로 나눔
    • hot vectorized loop: 항상 길이 N 입력만 처리
    • cold remainder part: i < N 입력을 최대 한 번 처리
  • Rust의 Iterator::chunks_exact()를 사용해 hand-rolled unroll-and-jam을 구현함
  • hot loop에서는 Simd::from_slice()를 호출해 단일 vector-sized load를 수행함
  • bounds check는 컴파일러가 제거하기 쉬운 형태가 됨

벤치마크와 수동 로딩 최적화

  • 벤치마크는 길이 0부터 약 200 또는 500바이트까지의 메시지를 디코딩하고, crates.io의 baseline base64 구현과 비교함
  • 컴파일 옵션은 -Zbuild-std와 -Ctarget-cpu=native를 사용함
  • 튜닝 결과 N = 32가 가장 좋았고, hot loop iteration마다 YMM 레지스터 하나를 사용함
  • 처음에는 baseline을 이겼지만, data.len() % 32와 강하게 상관된 heartbeat 형태의 성능 변동이 나타남
  • assembly를 확인한 뒤 copy_from_slice가 byte 단위 load loop로 inline/unroll된 것 같다고 판단함
  • Simd::gather_or()도 시도했지만 더 나쁜 assembly를 만들어 사용하지 않음
  • 대신 variable-length 데이터를 위한 수동 loading 함수를 작성함
    • hot part는 가능한 큰 scalar load인 u128 load를 루프에서 수행함
    • LLVM은 16바이트 chunk를 XMM load로 낮춤
    • remainder는 겹치는 u64, u32, u8 load를 이용함
  • 15바이트를 읽을 때는 p에서 u64, p + 7에서 u64를 읽어 1바이트가 겹치게 하고 OR로 합침
  • 4~7바이트는 겹치는 u32 load를 사용함
  • 1~3바이트는 p, p + len/2, p + len - 1에서 읽어 일부 byte를 중복 load할 수 있지만 분기 수를 줄임
  • 새 loading code 적용 뒤 variance가 매우 작아졌고, baseline 대비 거의 전 구간에서 2배 성능을 보임

encoding과 web-safe base64

  • encoding 함수는 decode_hot()의 연산을 거꾸로 수행하는 encode_hot()을 구현하면 됨
  • 디코딩에서 사용한 perfect hash는 encoding에는 맞지 않아 새로운 hash가 필요함
  • encoder 주변의 loading/storing 코드도 decoder와 조금 다름
  • vb64는 효율적인 encoding routine도 구현함
  • web-safe base64는 +와 /를 -와 _로 바꾸는 변형임
  • web-safe base64의 perfect hash 구성은 더 까다로우며, 예시로 (byte >> 4) - (byte == '_' ? '_' : 0) 같은 방식이 필요할 수 있음
  • vb64는 아직 web-safe base64를 지원하지 않음

결론

  • vb64는 중요한 병목을 해결하려는 라이브러리는 아니며, base64 decoding이 실제로 병목인 곳을 알지 못한다고 밝힘
  • branchless 코드는 종종 과하지만, 컴파일러가 해줄 수 있는 것과 해줄 수 없는 것을 이해하는 데 도움이 됨
  • Rust의 std::simd는 전반적으로 좋고 훌륭한 코드를 생성함
  • SIMD 코드를 더 단순하게 만들기 위해 고쳐졌으면 하는 rough edge는 있지만, 현재 작업 결과에는 만족한다고 평가함
  • SIMD와 성능 최적화는 많은 트릭과 하드웨어 지식을 요구하는 복잡한 주제이며, 그중 상당수는 문서화되어 있지 않음

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • portable SIMD를 실제로 쓰는 걸 보니 흥미로웠고, Zen 3 시스템에서 벤치마크를 재현해 보니 동일한 속도 향상이 나왔음
    M1 MacBook Pro에서는 입력 길이 110바이트에서 성능 향상이 1.4배에서 시작해 점진적으로 2배까지 올라갔고, x86_64보다는 낮지만 목표는 달성한 것으로 보임
    다만 코드를 보면 Rust가 SIMD와 포인터 관련 작업, 더 넓게는 성능 엔지니어링에서 인체공학이 꽤 나쁘다는 내 경험을 확인해 줌

    • Rust 엔지니어 입장에서 어느 정도 동의하지만, 포인터와 원시 메모리 작업은 안전성 때문에 의도적으로 제약이 많고, 언어가 무엇을 하는지 정말 생각하게 만들려는 면이 있음
      그래도 Rust의 portable SIMD는 C++에 비해 아직 좋은 이야기가 아니고, 원시 바이트 영역·포인터·버퍼 조작으로 내려가려면 Pin, MaybeUninit 등에 익숙해져야 함
      portable_simd와 allocator_api는 수년째 불안정 상태이고 진입 장벽도 높으며 더 어색한데, 대부분 의도된 설계임
      다만 자기 프로그램 안에서 더 쓰기 좋게 만들 추상화를 직접 만들거나 서드파티 크레이트를 쓰는 걸 막는 건 없음
    • 인체공학이 나쁘다는 데는 동의하지 않음
      C++ SSE intrinsic은 밑줄도 보기 흉하고 이름도 외우기 어려워 훨씬 더 나쁨

  • 고전적인 C++로 최선을 다해 구현했는데, 누군가 SIMD 버전으로 10배 이상 빠르게 만들어 오는 걸 보면 가끔 정말 놀라움
    대신 이 코드는 이식성이 떨어짐
    컴파일러의 자동 벡터화가 더 좋아졌으면 하고, 일부 연산 재정렬을 국소적으로 허용하는 언어 차원의 주석 같은 지원도 있었으면 함

    • 좋은 SIMD 코드는 데이터가 메모리에 어떻게 배치되어 있는지 세심하게 고려해야 함
      컴파일러가 아주 국소적인 문맥 밖에서는 데이터를 대신 고쳐줄 수 없어서 자동 벡터화가 정말 어려워짐
    • 컴파일러가 완벽하게 최적화할 수 있어도 피할 수 없는 직렬 보장이 많음
      예를 들어 for(double v: vec) sum+=v에서 부동소수점 덧셈은 결합법칙이 성립하지 않으므로, 값을 순서대로 더하는 것과 8개 간격으로 더한 뒤 나머지를 합치는 SIMD 방식은 같지 않음
      컴파일러 입장에서는 명백한 최적화처럼 보여도, 특정 보장을 완화하라고 알려주지 않는 한 최적화보다 직렬 의미 보장을 우선함
      그래서 난잡해지고, janwas 말처럼 뜨거운 경로에는 라이브러리, 특히 Google Highway나 Intel ISPC 같은 걸 쓰는 편이 낫다고 봄
    • 그게 C++ 같은 시스템 프로그래밍 언어의 포인트 중 하나임
      가능한 한 이식성 있게 효율적이려고 하면서도, 필요할 때는 대상 특화 프로그래밍을 쉽게 해줌
      자동 벡터화는 FORTRAN 컴파일러가 확실히 더 잘하는데, 별칭이 허용되지 않기 때문임
      C++은 C의 메모리 모델을 따르느라 발목이 잡힘
    • 그냥 CUDA를 쓸 수도 있음
      CUDA는 오늘날의 궁극적인 SIMD 기계인 GPU를 위해 설계된 C++이고, ROCm은 사실상 AMD용 CUDA에 가까움
      개인적으로는 Microsoft의 C++AMP를 좋아했는데, 입문하기 가장 쉬웠다고 봄
      다만 결국 자리 잡지 못해 아쉬움
    • 이런 일은 내 경험상 자주 일어남
      또한 SIMD 래퍼 라이브러리를 쓰면 실제로는 꽤 이식성 있게 만들 수 있음

  • 작은 참고로, 컴파일러가 해당 popcount 구현을 단일 명령으로 최적화하지는 못했지만 다른 구현에서는 가능함
    물론 꽤 까다롭긴 함: https://godbolt.org/z/T69KxWWW8

  • _mm256_cvtps_epu32는 특정 명령어 집합의 저수준 연산을 나타낸다고 했고 AVX2의 float-to-int 캐스트라고 설명했지만, 그 명령은 AVX-512에 속함
    AVX2에는 float-to-int 캐스트가 없고, AVX1에는 정수 결과가 signed이며 명령은 _mm256_cvtps_epi32임

  • fastbase64[0]와 비교하면 어떨지 궁금함
    글은 훌륭하고 이런 내용을 온라인에서 볼 수 있어 반갑지만, portable SIMD 라이브러리에 대한 작성자의 낙관론까지는 공유하기 어려움
    [0]: https://github.com/lemire/fastbase64

  • SIMD를 C++이나 Rust에 덧붙이는 것보다 ISPC가 그냥 더 낫다고 봄
    동적 디스패치도 지원하는데, 직접 구현하려면 고통스러운 기능임

    • 사람들이 SIMD를 더 많이 쓰게 해주는 도구라면 대체로 좋은 일이겠지만, 개인적으로는 SIMD가 같은 도구체인에 통합되어 있는 쪽을 선호함
      그래야 C++로 인라인 호출을 되돌려 보낼 수 있고, SIMD 코드에서 템플릿과 클래스를 쓰며, 여러 SIMD 코드 영역을 함께 인라인할 수도 있음
      동적 디스패치 구현이 어렵다는 데는 동의하지만, Highway가 그 부분을 처리해 줌
    • 본문 같은 작은 서브루틴에서 C++이나 Rust가 ISPC를 호출하기 쉬운지 궁금함

  • 훌륭한 글이고, “난 절대 이렇게 똑똑해질 수 없겠다”는 느낌이 강하게 남음

    • 그냥 본인 업무 분야가 아닐 뿐임
      보통 사람이 소프트웨어 엔지니어나 물리학자가 아닌 것과 비슷함
      몇 달 집중해서 공부하면 비슷한 수준으로 할 수 있을 것임
    • 이런 게 필요한 고용주나 프로젝트를 만날 기회가 있다면 아마 “이 정도로 똑똑해질” 수 있음
      결국 흥미와 필요의 문제임
      나도 성능 최적화나 더 시스템에 가까운 베어메탈 엔지니어링을 개인 프로젝트에서 오가며 해보지만, 업무에서 더 필요했으면 좋겠음
      다만 대부분의 업계 일이 요구하는 건 그쪽이 아님
    • AoC '23을 APL/j/k, BQN, Python/numpy, CUDA 등으로 해보면 좋음
      관용적인 Python이 아니라 모든 걸 numpy로 푸는 식임
      재미있고 이런 종류의 영리함을 배울 수 있으며, 글의 많은 부분이 그런 언어들에서 문제를 푸는 사고방식으로는 아주 자연스럽게 느껴짐
      시간이 지나면 문제를 그런 형태로 보기 시작함
    • https://fgiesen.wordpress.com/2016/02/05/smart/

  • 흥미로운 글임
    초반 첫 예시에서 벡터화되지 않은 popcnt 구현이 “솔직히 우스꽝스러울 정도로 나쁜 코드”를 만든다고 했지만, release 모드에 native 대상 CPU를 쓰면 해당 함수가 꽤 괜찮게 벡터화되는 것처럼 보임
    https://godbolt.org/z/WE1Eq65jY

    • 아래 코드는 동등한 출력을 만들어야 함
      pub fn popcnt(mut x: u32) -> u32 { x.count_ones() }
      이는 popcnt eax, edi; ret로 컴파일됨
      큰 비트 벡터에서는 AVX2 구현이 POPCNT보다 빠를 수 있음
      “Faster Population Counts Using AVX2 Instructions” 참고: https://academic.oup.com/comjnl/article/61/1/111/3852071
      32비트는 충분히 크지 않고, Rust가 생성하는 코드는 실제로 우스꽝스러울 정도로 나쁨
    • 이상적으로는 이게 popcnt 명령으로 낮아져야 할 것 같음
    • 자동 벡터화는 될 때도 있고 안 될 때도 있음
      최근에 벡터 연산 결과 마스크의 비트 수를 세야 하는 코드를 작성했는데, 이건 popcnt로 잘 바뀜
      https://godbolt.org/z/zT9Whcnco

  • “이건 함정 질문 같은데… 그냥 add 아닌가?” 같은 부분 때문에, 보통은 중간 벡터 표현을 대상으로 삼고 세부 사항은 컴파일러가 결정하게 하고 싶어짐
    예를 들어 Haswell 칩은 코어당 여러 부동소수점 실행 유닛이 있고, CPU는 파이프라인화된 부동소수점 연산을 둘 이상 동시에 실행할 수 있었지만, 그중 add 명령은 하나만 가능했음
    이전 결과에 의존하지 않는 덧셈이 많아 지연을 피할 수 있다면, 곱셈항이 1인 융합 곱셈-덧셈 명령도 함께 보내 덧셈 처리량을 두 배로 만들 수 있었음
    그 명령은 일반 벡터 부동소수점 덧셈과 동시에 실행될 수 있었음

답변달기