정수 하나를 문자열로 바꾸는 데 2나노초도 안 걸린다고? 숨겨진 최적화의 세계

'정수를 문자열로 바꾸는 거 그거 얼마나 빠르겠어?' 싶겠지만, 이게 의외로 성능에 큰 영향을 주는 연산이에요. 로그를 찍거나, JSON을 직렬화하거나, 데이터베이스에 쿼리를 만들 때마다 우리는 무의식적으로 이걸 호출하거든요. 최근 한 논문이 64비트 정수를 십진수 문자열로 바꾸는 데 2나노초 이내에 끝내는 알고리즘을 제시했어요. 단순해 보이는 함수 하나에 어떻게 그렇게까지 최적화 여지가 있는 건지, 한번 들여다볼 가치가 있습니다.

일단 왜 이게 중요한가

C 표준 라이브러리의 sprintf나 자바의 Integer.toString은 내부적으로 '10으로 계속 나누면서 나머지를 ASCII 문자로 바꾸기'를 반복합니다. 그런데 나눗셈은 현대 CPU에서 가장 느린 연산 중 하나예요. 곱셈은 한두 사이클에 끝나는데 정수 나눗셈은 수십 사이클이 걸리거든요. 그래서 핫패스(자주 호출되는 코드 경로)에서 이걸 그대로 쓰면 처리량이 뚝뚝 떨어집니다. 페이스북, 구글 같은 곳에서 자체 itoa(integer to ASCII) 함수를 만들어 쓰는 것도 이런 이유 때문이에요.

2나노초의 비결

이 분야의 핵심 기법은 두 가지예요. 첫째는 '매직 넘버 곱셈(magic number multiplication)' 이라고 해서, 나눗셈을 곱셈과 비트 시프트로 치환하는 거예요. 어떤 수를 10으로 나누고 싶다면, 미리 계산해둔 상수(예를 들어 약 2^32/10에 해당하는 값)를 곱하고 적당히 오른쪽으로 시프트하면 같은 결과가 나옵니다. 컴파일러가 상수 나눗셈일 때 자동으로 해주는 최적화인데, 이걸 가변 입력에도 일반화한 거죠. 둘째는 '룩업 테이블' 을 활용해서 두 자릿수씩 한 번에 변환합니다. 00부터 99까지의 두 글자 문자열을 미리 100개 만들어두고, 정수를 100으로 나누면서 두 글자씩 채워나가는 거예요. 한 자릿수씩 처리하는 것보다 분기와 메모리 접근이 절반으로 줄어듭니다. 더 나아가 SWAR(SIMD Within A Register) 기법으로 64비트 레지스터 안에서 여러 자릿수를 한꺼번에 굴리는 트릭도 들어가요.

기존 알고리즘과 비교

이 분야의 베이스라인은 'Jeaiii'라는 사람이 만든 알고리즘이에요. 깃허브에 공개되어 C++ 표준 라이브러리 구현체에도 영향을 줬죠. 그다음 Junekey Jeon의 Dragonbox(부동소수점 변환), 그리고 Daniel Lemire(simdjson을 만든 분)의 연구도 유명합니다. 이번 논문은 이런 선행 연구를 정리하면서, 분기 예측과 캐시 친화성까지 함께 고려한 새로운 변형을 제시했어요. 평균적으로 Jeaiii보다 10~30% 빠르다고 합니다. 절댓값으로 보면 한 호출에 0.5~2나노초 수준이에요.

어디서 효과를 볼까

대량의 로그를 텍스트로 쓰는 서비스, 고성능 JSON 직렬화 라이브러리(simdjson, rapidjson, sonic-cpp 등), 실시간 분석 파이프라인 같은 곳에서 효과가 큽니다. 카프카로 1초에 수십만 건의 이벤트를 직렬화한다고 생각해보세요. 이벤트 하나에 정수 필드가 다섯 개씩 있으면 itoa 호출만 초당 수백만 번이에요. 1나노초만 줄여도 무시 못 할 차이가 됩니다. 데이터베이스 클라이언트가 prepared statement를 안 쓰고 SQL 문자열을 직접 만드는 경우에도 비슷한 부담이 있어요.

한국 개발자에게는

대부분의 웹/앱 개발 상황에서는 기본 라이브러리로 충분합니다. 굳이 itoa를 갈아 끼울 일이 없어요. 하지만 다음 같은 경우엔 살펴볼 가치가 있어요. 첫째, 검색·광고·게임 서버처럼 마이크로초 단위로 SLA를 맞춰야 하는 곳. 둘째, 임베디드나 IoT 환경에서 CPU가 약한데도 직렬화를 자주 해야 하는 경우. 셋째, 빅데이터 ETL 파이프라인을 직접 구현하는 경우. 이 외에도, '라이브러리 안에서 이렇게까지 최적화가 일어나는구나'를 알고 있으면 성능 병목을 찾을 때 시야가 넓어집니다. 프로파일러에서 sprintf나 String.valueOf가 위에 떠 있는 걸 보고 그냥 넘기지 않게 되거든요.