더 빠른 double→string 변환

모든 소프트웨어 엔지니어의 인생에는 새로운 이진→십진 부동소수점 변환 방법을 придум어내는 순간이 찾아온다고 한다. 내 차례가 온 것 같다. 주말 대부분을 써서 하나를 방금 작성했다: https://github.com/vitaut/zmij.

이 구현은 Dragon4, Grisu, Schubfach를 구현하면서 배운 교훈에, 나와 다른 사람들이 떠올린 몇 가지 새 아이디어를 더해 만들었다. 주요 지침 원칙은 Alexandrescu의 “어떤 일(some work)보다 일이 없는 것(no work)이 더 적은 일이다”라는 말로, Schubfach에서 여러 요소(조건 분기, 계산, 심지어 후보 숫자까지)를 제거하는 데서 많은 개선이 나온다.

성능

dtoa-benchmark에서의 성능은 다음과 같다:

• Dragonbox보다 약 68% 빠름(적어도 정확성 증명이 있는 알고리즘 중 이전 1위)
• 원 논문을 closely 따라간 내 Schubfach 구현보다 약 2배 빠름
• libc++의 std::to_chars (Ryu?)보다 약 3.5배 빠름
• Google의 double-conversion (Grisu3)보다 약 6.8배 빠름
• macOS의 sprintf(Dragon4?)보다 약 59배(퍼센트가 아니라 배수!) 빠름

Apple M1에서 double 하나를 변환하는 데 약 10~20 ns가 걸린다.

어떤 점이 개선됐나?

Schubfach 대비 개선점 목록은 다음과 같다:

• 후보를 24개가 아니라 13개 중에서 선택
• 짧은(shorter) 케이스에서 정수 곱셈 감소
• 더 빠른 로그 근사
• 더 빠른 나눗셈과 나머지(modulo)
• 조건 분기 감소
• 가수(significand)와 지수(exponent) 출력 효율 향상

몇 가지를 자세히 보자.

첫 번째 소소한 개선은 특수 케이스(NaN, 무한대, 0, 서브노멀)를 빠르게 확인하기 위해 단일 분기를 두는 것이다. 그 경로 안에서 추가 검사들이 있긴 하지만, 일반적인(common) 케이스가 더 간결해진다.

또 다른 개선은 더 빠른 고정소수점 로그 근사를 사용하는 것이다. Schubfach는 다음을 수행한다:

cpp
// log10_2_sig = round(log10(2) * 2**log10_2_exp)
constexpr int64_t log10_2_sig = 661'971'961'083;
constexpr int log10_2_exp = 41;

// Computes floor(log10(pow(2, e))) for e <= 5456721.
auto floor_log10_pow2(int e) noexcept -> int {
  return e * log10_2_sig >> log10_2_exp;
}

이는 64비트 곱셈을 사용한다:

asm
floor_log10_pow2(int):
        movsxd  rcx, edi
        movabs  rax, 661971961083
        imul    rax, rcx
        sar     rax, 41
        ret

하지만 입력(지수)의 범위를 고려하면 32비트 근사를 사용할 수 있다:

cpp
// log10_2_sig = round(log10(2) * 2**log10_2_exp)
constexpr int log10_2_sig = 315'653;
constexpr int log10_2_exp = 20;

auto floor_log10_pow2(int e) noexcept -> int {
  return e * log10_2_sig >> log10_2_exp;
}

그 결과는 다음과 같다:

asm
floor_log10_pow2(int):
        imul    eax, edi, 315653
        sar     eax, 20
        ret

Dragonbox도 약간 다른 상수를 사용하긴 하지만 32비트 근사를 사용한다.

비슷하게, 일부 정수 나눗셈을 정수 곱셈으로 바꿀 수 있다. 컴파일러도 이미 이를 할 줄 알지만, 입력 범위가 작다는 걸 알고 있으면 더 잘할 수 있다:

cpp
// Returns {value / 100, value % 100} correct for values of up to 4 digits.
inline auto divmod100(uint32_t value) noexcept -> divmod_result {
  assert(value < 10'000);
  constexpr int exp = 19;  // 19 is faster or equal to 12 even for 3 digits.
  constexpr int sig = (1 << exp) / 100 + 1;
  uint32_t div = (value * sig) >> exp;  // value / 100
  return {div, value - div * 100};
}

또 다른 최적화이자 단순화는 비정규(irregular) 반올림 구간을 분기 없이(branchless) 처리하는 것이다. 반올림 구간에 대해서는 내가 이전 글에서 다뤘지만, 이 글의 목적상 다음만 알면 충분하다: 어떤 부동소수점 수의 반올림 구간은, 그 수로 반올림되어 돌아오는 모든 실수들을 포함하는 구간이다. 일반적으로 구간은 대칭이지만, 지수가 점프하는 경우(비정규 케이스)에는 예외가 된다.

대부분의 알고리즘은 비정규 구간을 완전히 별도의 경로로 처리하거나, 적어도 몇 번의 분기를 통해 처리한다. 난수에 가까운 부동소수점 수에서는 비정규 케이스가 드물기 때문에 이는 크게 나쁘지 않다. 하지만 추가 복잡성을 피하면서도 값싸게, 그리고 분기 없이 처리하는 것이 가능하며, 내가 그렇게 했다.

더 흥미로운 개선은 Cassio Neri의 발표 Fast Conversion From Floating Point Numbers에서 나온다. Schubfach에서는 후보 숫자 네 개를 본다. 첫 두 개는(최대 하나만 반올림 구간에 들어감) 더 큰 십진 지수에 대응하고, 나머지 두 개는(최소 하나가 반올림 구간에 들어감) 더 작은 지수에 대응한다. Cassio의 통찰은 첫 번째 경우에서 상한(upper bound)으로부터 단 하나의 후보를 직접 구성할 수 있다는 것이다.

이 개선은 좋은 효과가 있다. 값 자체를 10의 거듭제곱으로 스케일링할 필요가 없어지기 때문이다. 하한과 상한만 필요하다. 이로 인해 짧은 케이스에서 64비트 정수 곱셈 두 번을 절약한다.

불행히도 이는 긴(longer) 케이스에는 도움이 되지 않지만, 그쪽에도 개선할 여지가 있다. 고전적인 Schubfach는 먼저 두 번째 집합에서 반올림 구간 안에 있는 후보가 하나뿐인지 검사하고, 그렇다면 일찍 반환한다. 우리는 이 검사를 closedness 검사와 결합할 수 있다. 직관에 반하는 듯한데(더 많은 일을 하니까… 미안해요, Andrei), 예측이 잘 안 되는 조건 분기를 제거하고 코드도 단순화한다.

즉, 다음에서:

cpp
uint64_t dec_sig_over = dec_sig_under + 1;
bool under_in = lower + bin_sig_lsb <= (dec_sig_under << 2);
bool over_in = (dec_sig_over << 2) + bin_sig_lsb <= upper;
if (under_in != over_in) {
  // Only one of dec_sig_under or dec_sig_over are in the rounding interval.
  return write(buffer, under_in ? dec_sig_under : dec_sig_over, dec_exp);
}

// Both dec_sig_under and dec_sig_over are in the interval - pick the closest.
int cmp = scaled_sig - ((dec_sig_under + dec_sig_over) << 1);
bool under_closer = cmp < 0 || cmp == 0 && (dec_sig_under & 1) == 0;
return write(buffer, under_closer ? dec_sig_under : dec_sig_over, dec_exp);

다음으로 바뀐다:

cpp
// Pick the closest of dec_sig_under and dec_sig_over and check if it's in
// the rounding interval.
int64_t cmp = int64_t(scaled_sig - ((dec_sig_under + dec_sig_over) << 1));
bool under_closer = cmp < 0 || (cmp == 0 && (dec_sig_under & 1) == 0);
bool under_in = (dec_sig_under << 2) >= lower;
write(buffer, (under_closer & under_in) ? dec_sig_under : dec_sig_over,
      dec_exp);

가수와 지수 출력 부분에도 많은 개선이 있다. 가장 단순한 것은, {fmt}에서 수년간 사용되어 왔고 Alexandrescu의 “Three Optimization Tips for C++” 발표에서 배운 방식인데, 십진수 두 자리 쌍을 출력하기 위한 룩업 테이블을 사용하는 것이다. 이것만으로도 정수 곱셈 횟수가 절반으로 줄어든다. 특히 여기서는 가수가 16~17자리인 경우가 많기 때문에 중요하다.

또 다른 트릭은 작은 룩업 테이블을 이용해 뒤따르는 0(trailing zeros)를 분기 없이 제거하는 것이다. 이는 Alexander Bolz의 훌륭한 Drachennest 프로젝트에서 온 아이디어라고 믿는다. 이를 더 개선하고, 잠재적으로는 룩업 테이블 자체를 완전히 제거할 아이디어도 있다.

이건 새로운 알고리즘인가?

이게 새로운 알고리즘이라고 불릴 만한지, 아니면 Schubfach의 최적화에 불과한지?

확신은 없지만, 최소한 별도의 GitHub 프로젝트로 둘 가치는 있다고 생각한다 =).

어디에 사용할 수 있나

이 방법(또는 그 일부 요소)은 {fmt}에서 사용될 예정이며, Thrift 등에서의 JSON 직렬화에도 좋은 후보이다. 더 빠른 부동소수점 포매팅의 이점을 얻을 수 있는 다른 응용이 있다면, 지금 바로 살펴봐도 좋고 {fmt}에 통합될 때까지 기다려도 좋다.

내 ISO C++ 페이퍼 P2587 “to_string or not to_string” 덕분에 std::to_string도 이 방법 또는 유사한 방법을 사용할 수 있게 될 것이다. 그러면 이 표준 API는 성능이 좋으면서도 실제로 유용한 것이 된다.

현재의 한계

이름과는 달리 구현은 아직 완전히 다듬어지지(polished) 않았다. 특히 현재는 지수 표기, 즉 과학(scientific) 표기만 지원하지만, 고정(fixed) 포맷을 추가하는 일은 간단할 것이다.

“재미” 사실

예전 직장 동료 David Gay는 Bell Labs에서 초기 dtoa 구현을 작성했고, 이는 수년 동안 널리 사용되었다.

---

2025-12-13에 마지막으로 수정됨