오랜만에 진짜 “엔지니어링” 냄새가 물씬 나는 글을 읽었습니다. 요즘처럼 AI가 코드를 짜주고, 수많은 추상화 레이어 위에서 개발하는 시대에 비트(Bit) 단위의 제어 와 CPU 인스트럭션 을 직접 다루는 글은 언제나 반갑더군요.

오늘 소개할 내용은 C++로 효율적인 Fixed-width 128-bit Integer(u128)를 구현하는 방법 입니다. 단순히 “큰 숫자를 다루고 싶다”는 니즈라면 GMP 같은 라이브러리를 쓰면 그만입니다. 하지만 기하학(Geometry) 연산이나 고빈도 트레이딩(HFT), 혹은 암호화폐 원장 같은 Hot Path 에서 동적 할당이 일어나는 BigInt를 쓴다? 그건 퍼포먼스 자살행위나 다름없습니다.

이 글은 Solidean의 기술 블로그와 Hacker News의 논쟁을 바탕으로, 왜 우리가 바퀴를 다시 발명해야 하는지, 그리고 어떻게 하면 컴파일러가 만들어주는 코드보다 더 예측 가능한 코드 를 짤 수 있는지 깊게 파고듭니다.

왜 굳이 직접 구현하는가?

많은 분들이 이렇게 생각하실 겁니다. “GCC/Clang에 이미 __int128 있잖아요?” 맞습니다. Hacker News 댓글에서도 가장 먼저 나온 지적이죠.

하지만 저자는 명확한 이유를 제시합니다:

1. 이식성(Portability): MSVC 같은 컴파일러는 __int128을 지원하지 않습니다.
2. 확장성: 128비트는 시작일 뿐입니다. 192비트, 256비트 정수로 확장하기 위한 기초 체력을 다지는 과정입니다.
3. 제어권: 컴파일러의 매직에 의존하기보다, 정확히 어떤 어셈블리가 떨어질지 예측하고 싶어 합니다.

특히 기하학 연산에서 Exact Arithmetic을 수행할 때, 고정된 비트 너비 안에서 오차 없는 연산을 수행하는 것은 필수적입니다. 동적 메모리 할당이 없는 struct 기반의 구현체는 캐시 지역성(Cache Locality) 측면에서도 압도적으로 유리합니다.

구현의 핵심: Intrinsic을 두려워하지 마라

이 구현의 핵심은 u64 두 개를 붙여서 u128을 만들되, C++의 기본 연산자가 아니라 CPU Intrinsic 을 적극 활용한다는 점입니다.

1. 덧셈 (Addition)

단순히 low + low를 하고 오버플로우를 체크하는 방식은 코드가 지저분해집니다. x64 아키텍처에는 ADC (Add with Carry)라는 훌륭한 명령어가 있습니다. 이를 C++에서 쓰려면 _addcarry_u64를 사용하면 됩니다.

u128 operator+(u128 a, u128 b)
{
    u128 r;
    // 하위 64비트 덧셈, 캐리 발생 시 c에 저장
    unsigned char c = _addcarry_u64(0, a.low, b.low, &r.low);
    // 상위 64비트 덧셈 + 하위에서 넘어온 캐리 처리
    (void)_addcarry_u64(c, a.high, b.high, &r.high);
    return r;
}

이 코드는 컴파일되면 군더더기 없는 add와 adc 인스트럭션으로 변환됩니다. 인라인 어셈블리를 직접 쓰는 것보다 Intrinsic이 좋은 이유는, 컴파일러가 이 함수의 의미(Semantics)를 이해하고 스케줄링 최적화를 할 수 있기 때문입니다.

2. 곱셈 (Multiplication)

곱셈은 조금 더 복잡합니다. 128비트 곱셈은 이론적으로 256비트 결과를 내지만, 우리는 하위 128비트만 필요합니다. 여기서 저자는 대수학적으로 항을 분리하여 필요한 부분만 계산합니다.

특히 _mulx_u64 (BMI2 명령어)를 사용하여 캐리 플래그를 건드리지 않고 곱셈을 수행하는 부분이 인상적입니다. 이는 파이프라인 효율을 높이는 데 기여합니다. Hacker News의 한 유저는 Karatsuba 알고리즘 (곱셈 횟수를 4번에서 3번으로 줄임)을 언급했지만, 128비트 정도의 작은 크기에서는 분기 비용이나 오버헤드 때문에 그냥 4번 곱하고 더하는 게 나을 수도 있습니다. 실제로 저자의 구현은 3번의 곱셈(low*low, low*high, high*low)만으로 하위 128비트를 완성합니다.

3. 비교 연산: 분기(Branch)를 없애라

제가 가장 무릎을 쳤던 부분은 비교 연산자(<) 구현입니다. 보통은 이렇게 짭니다.

if (a.high != b.high) return a.high < b.high;
return a.low < b.low;

이건 논리적으론 완벽하지만, 분기 예측 실패(Branch Misprediction) 의 위험이 있습니다. 저자는 이를 SBB (Subtract with Borrow)를 이용해 분기 없는(Branchless) 코드로 바꿉니다.

bool operator<(u128 a, u128 b)
{
    u64 dont_care;
    // a.low - b.low를 해서 borrow가 발생하는지 확인
    unsigned char borrow = _subborrow_u64(0, a.low, b.low, &dont_care);
    // 그 borrow를 포함해서 상위 비트를 뺄셈
    borrow = _subborrow_u64(borrow, a.high, b.high, &dont_care);
    return borrow != 0;
}

결국 a < b라는 건 a - b를 했을 때 Underflow(Borrow)가 발생하느냐와 동치입니다. 이걸 하드웨어 플래그를 통해 확인하는 것이죠. 정말 우아하지 않나요?

놓치기 쉬운 디테일과 한계

물론 이 구현이 만능은 아닙니다. Hacker News에서도 지적되었듯, 나눗셈(Division) 구현이 빠져 있습니다. 나눗셈은 하드웨어적으로도 비싼 연산이고, 128비트 나눗셈은 x64 명령어 하나로 해결되지 않습니다 (물론 divq를 이용해 128/64 나눗셈은 가능하지만, 128/128은 복잡합니다). 저자도 이를 인정하며 “이진 롱 디비전(Binary Long Division)“을 언급하지만, 실제 구현은 꽤 까다로울 겁니다.

또한, unsigned long long을 u64로 정의해서 쓴 부분에 대해 “표준 호환성” 논란이 있었습니다. uint64_t를 쓰는 게 더 안전하겠지만, x64 환경과 Intrinsic 시그니처를 고려하면 현실적인 타협이라고 봅니다.

결론: 기본기가 주는 강력함

이 글은 단순히 128비트 정수를 구현하는 튜토리얼이 아닙니다. 하드웨어가 어떻게 동작하는지 이해하고, 컴파일러가 최적의 코드를 뱉어내도록 유도하는 엔지니어링의 정수 를 보여줍니다.

솔직히 대부분의 웹 개발자나 앱 개발자에게는 필요 없는 기술일 수 있습니다. 하지만 시스템 프로그래밍, 게임 엔진, 블록체인 코어, 혹은 고성능 금융 시스템을 다루는 엔지니어라면 한 번쯤 Godbolt에 코드를 넣어보고 어셈블리를 뜯어보는 재미를 느껴보시길 바랍니다.

Reference:

• Building Your Own Efficient uint128 in C++
• Hacker News Discussion