지그재그 디코딩을 AVX-512로 가속하기 — 숫자 압축의 숨은 영웅 이야기

작은 숫자 하나에도 절약의 미학이

데이터를 저장하거나 네트워크로 보낼 때, 우리는 늘 "어떻게 하면 한 바이트라도 아낄까"를 고민하잖아요. 이번 이야기는 그 절약 기술의 한복판에 있는 지그재그 인코딩(zigzag encoding), 그리고 그걸 AVX-512라는 CPU 기능으로 초고속 처리하는 방법에 관한 거예요. 게임 엔진이나 데이터 직렬화 라이브러리를 깊게 파는 분들이 흥미로워할 주제인데, 차근차근 풀어볼게요.

varint와 지그재그, 그게 뭔데요

먼저 배경부터요. 숫자를 저장할 때 보통 정수 하나에 4바이트(32비트)를 통째로 쓰잖아요. 그런데 실제로는 작은 숫자가 훨씬 많거든요. 3이라는 값을 굳이 4바이트나 들여 저장하는 건 낭비죠. 그래서 나온 게 varint(가변 길이 정수)예요. 작은 숫자는 1바이트, 큰 숫자는 그만큼 더 많은 바이트를 쓰도록 길이를 유연하게 바꾸는 방식이에요. Protocol Buffers 같은 데이터 포맷이 이걸 즐겨 써요.

그런데 varint에 한 가지 약점이 있어요. 음수를 만나면 망가져요. 컴퓨터가 음수를 표현하는 방식(2의 보수) 때문에 -1 같은 작은 음수가 비트로는 엄청나게 큰 수처럼 보이거든요. 그러면 1바이트면 될 걸 최대 길이로 저장하는 참사가 벌어져요.

여기서 지그재그 인코딩이 구원투수로 등장해요. 아이디어가 기발한데요, 0은 0으로, -1은 1로, 1은 2로, -2는 3으로... 이런 식으로 양수와 음수를 번갈아 가며(지그재그로) 작은 숫자에 매핑하는 거예요. 그러면 절댓값이 작은 음수도 작은 양수로 변신해서 varint의 절약 효과를 그대로 누릴 수 있어요. 실제 변환은 비트 시프트와 XOR 연산 몇 개로 끝나는, 아주 가볍고 영리한 트릭이에요.

그런데 왜 AVX-512까지 동원할까

문제는 데이터가 수백만 개 단위로 쏟아질 때예요. 숫자 하나하나를 디코딩하면서 "시프트하고 XOR하고"를 반복하면, 양은 적어도 횟수가 많아서 티끌 모아 태산처럼 시간이 쌓여요. 게임에서 메시 데이터를 풀거나, 대용량 로그를 파싱할 때 이게 병목이 되기도 하죠.

그래서 등장하는 게 SIMD예요. 이게 뭐냐면, "하나의 명령으로 여러 데이터를 동시에 처리"하는 CPU 기술이에요. 보통 CPU는 숫자를 한 번에 하나씩 더하는데, SIMD는 한 명령으로 8개, 16개를 한꺼번에 처리해요. 컨베이어 벨트에서 한 명이 물건을 하나씩 집는 대신, 16개짜리 집게로 한 번에 쓸어 담는 셈이죠. AVX-512는 인텔/AMD CPU가 가진 SIMD 명령어 세트 중에서도 폭이 가장 넓은(512비트) 축에 속해요.

지그재그 디코딩은 마침 SIMD와 궁합이 환상적이에요. 변환 로직이 시프트와 XOR뿐이라 분기(조건문)가 없고, 모든 숫자에 똑같은 연산을 적용하면 되거든요. 이런 "단순 반복형 연산"이야말로 SIMD가 가장 빛나는 무대예요. AVX-512의 마스크 연산이나 셔플 명령을 잘 조합하면, 한 번에 수십 개의 정수를 병렬로 복원하면서 기존 방식 대비 몇 배의 처리량을 뽑아낼 수 있어요.

업계 맥락에서 보면

이런 저수준 최적화는 메시 압축 라이브러리나 고성능 직렬화 영역에서 꾸준히 연구돼 왔어요. 데이터를 작게 만드는 인코딩(varint, 지그재그, 델타 인코딩 등)과, 그걸 빠르게 푸는 SIMD 디코딩은 사실 한 세트로 발전하거든요. 압축률만 좋고 푸는 게 느리면 실전에선 못 쓰니까요. 그래서 "작게 + 빠르게"를 동시에 잡으려는 이런 시도들이 게임 에셋 로딩, 데이터베이스 컬럼 저장, 시계열 데이터 처리 같은 곳에서 실제 성능을 좌우해요.

한국 개발자에게 주는 시사점

대부분의 실무에서는 이 정도 저수준 최적화를 직접 짤 일이 드물어요. 우리가 쓰는 라이브러리들이 이미 안에서 이런 마법을 부려주고 있거든요. 하지만 이 글의 가치는 따로 있어요. "내가 무심코 쓰는 직렬화 한 줄 뒤에 이런 정교한 비트 연산과 SIMD 최적화가 숨어 있다"는 걸 아는 것 자체가 시야를 넓혀줘요. 언젠가 성능 병목을 만났을 때, "아 여기 SIMD로 풀 수 있는 패턴 아닐까?" 하는 직감이 생기거든요. 데이터 엔지니어링이나 게임, 임베디드처럼 성능이 곧 경쟁력인 분야를 노린다면 이런 밑바닥 지식이 결정적인 차이를 만들 수 있어요.

마무리

한 줄로 정리하면, 음수까지 알뜰하게 압축하는 지그재그 트릭을, CPU의 병렬 처리 능력(AVX-512)으로 한 번에 수십 개씩 풀어내는 속도의 미학이에요. 여러분은 평소 코드를 짤 때, 라이브러리 안쪽에서 무슨 일이 벌어지는지 궁금해하는 편이세요, 아니면 일단 동작하면 충분하다고 보는 편이세요?