[cpython] CPython int 덧셈의 '혹시 몰라 할당한 1 digit' 없애기: x_add() 과할당 줄이기
PR 링크: python/cpython#158002 상태: Merged | 변경: +30 / -3
들어가며
CPython의 int는 임의 정밀도 정수입니다. 내부적으로는 PyLongObject가 30-bit 단위의 digit 배열(ob_digit)로 값을 저장합니다. 두 양수(또는 같은 부호의 두 수)를 더할 때는 Objects/longobject.c의 x_add()가 절댓값 덧셈을 담당합니다.
지금까지 x_add()는 결과를 위해 항상 size_a + 1개의 digit을 할당했습니다. 최상위 digit에서 carry가 넘어올 가능성을 대비한 것입니다. 하지만 대부분의 덧셈에서 그 carry는 0입니다. 결국 대부분의 경우 다음 일이 일어납니다.
- 쓰지 않을 digit 하나를 더 할당하고
- 그 자리에 0을 쓴 다음
long_normalize()를 호출해 크기를 다시 줄입니다.
long_normalize()는 논리적 크기만 줄입니다. 이미 할당한 메모리는 돌려주지 않습니다. 그래서 sys.getsizeof()로는 차이가 보이지 않지만, 실제 resident memory에는 그 낭비가 남습니다. 이 PR(gh-100687, @mdickinson의 #100688 확장)은 carry가 실제로 가능할 때만 여분 digit을 할당하도록 바꿉니다.
코드 분석
Objects/longobject.c — 할당 크기 결정
Before
z = long_alloc(size_a+1);
After
assert(size_a >= 1);
/* A carry out of the top digit is only possible if the top digits sum
to at least PyLong_MASK; only then allocate a digit for it. */
digit top_sum = a->long_value.ob_digit[size_a - 1]
+ (size_b == size_a ? b->long_value.ob_digit[size_b - 1] : 0);
int extra_digit = top_sum >= PyLong_MASK;
z = long_alloc(size_a + extra_digit);
핵심은 간단한 수학적 관찰입니다. 아래 자리에서 올라오는 carry는 최대 1입니다. 그러므로 최상위 자리에서 overflow(>= 2^30)가 나려면 top_a + top_b + 1 >= PyLong_MASK + 1이어야 하고, 이는 곧 top_sum >= PyLong_MASK입니다.
size_b < size_a이면 b의 최상위 자리는 0으로 취급됩니다. 이때 carry가 나는 경우는top_a == PyLong_MASK일 때뿐입니다.- 두 digit은 각각 30 bit이므로 합은 최대 31 bit입니다. 따라서
digit(uint32) 안에서 overflow 없이 계산됩니다.
이 조건은 보수적입니다. carry가 실제로 날지 정확히 판정하지는 않지만, 날 수 있는 경우는 절대 놓치지 않습니다. 예를 들어 합이 정확히 MASK이고 아래에서 carry가 오지 않으면, 여분 digit을 할당하더라도 기존처럼 long_normalize()가 정리합니다.
Objects/longobject.c — 마무리 단계
Before
z->long_value.ob_digit[i] = carry;
return long_normalize(z);
After
if (extra_digit) {
z->long_value.ob_digit[i] = carry;
return long_normalize(z);
}
assert(carry == 0);
assert(z->long_value.ob_digit[i - 1] != 0);
return z;
여분 digit이 없는 경로에서는 long_normalize()를 호출할 필요가 없습니다. a가 정규화되어 있으므로 최상위 digit은 0이 아닙니다. 게다가 이 경로에서는 overflow도 없으므로 결과의 최상위 digit도 0이 될 수 없습니다. 두 assert가 바로 이 불변식을 문서화합니다. 작은 수의 덧셈에서 함수 호출 하나와 루프 하나가 사라지는 셈입니다.
Lib/test/test_long.py — 경계 테스트
def test_long_add_overallocate(self):
x = (MASK//2) * (MASK+1)
x2 = (MASK//2 + 1) * (MASK+1)
self.assertEqual(x + x2, MASK * (MASK + 1))
이 테스트는 최상위 digit의 합이 정확히 MASK인 경계 케이스를 검증합니다. 두 번째 테스트 test_karatsuba_single_digit_parts는 다른 경로를 겨냥합니다. k_mul()이 operand를 반으로 나눈 뒤 x_add()로 더할 때 그 조각이 single digit일 수 있는데, 이 경우를 다룹니다. 내부 호출자가 새 가정(size_a >= 1, 정규화된 입력)을 깨지 않는지 확인하는 테스트입니다.
리뷰 피드백
StanFromIreland의 리뷰는 대부분 스타일과 문서에 관한 것이었습니다. 삼항 연산자 줄 정렬을 다듬었고, NEWS 항목을 "Reduce the memory used by the result of adding two large int values"처럼 사용자 관점으로 바꾸자고 제안했습니다. 내부 구현 용어(x_add, overallocation) 대신 사용자가 체감하는 효과를 적는 것이 changelog의 좋은 관행이라는 점을 보여줍니다.
왜 이게 좋은가
메모리: size class 경계 효과
PyLongObject 헤더는 24 B이고 digit은 개당 4 B입니다. pymalloc은 16 B 단위 size class로 메모리를 나눠 줍니다. 2-digit 결과를 예로 들면 다음과 같습니다.
- 기존: 3 digit을 할당하므로 36 B가 되고, 48 B class에 들어갑니다.
- 개선 후: 2 digit만 할당하므로 32 B가 되고, 32 B class에 들어갑니다.
| Sum of | main | PR | |
|---|---|---|---|
| 2-digit | 48.1 B | 32.0 B | −33% |
| 6-digit | 64.1 B | 48.1 B | −25% |
| 10-digit | 80.0 B | 64.1 B | −20% |
| 3-digit | 47.8 B | 47.9 B | 동일 |
digit 4개가 16 B이므로, digit 하나를 줄였을 때 class가 바뀌는 경우는 4개 중 1개꼴입니다. 3-digit 결과에 변화가 없는 이유도 여기에 있습니다.
속도
- 3
10 digit 덧셈: 1.041.05x 빠름 fib(300): 1.04x 빠름- 100/1000 digit: 1.03x/1.01x 느림. top digit 검사 비용이 생기고, 생략한 normalize 호출의 이득은 상대적으로 묻히기 때문입니다.
- 20개 케이스 기하평균: 1.02x 빠름
실제 프로그램의 정수는 대부분 작습니다. 따라서 작은 크기를 빠르게 하고 거대한 수에서 1~3%를 내주는 trade-off는 합리적입니다.
일반적 교훈
- "만약을 위한" 과할당을 의심하세요. 최악의 경우를 대비하는 비용을 모든 호출이 치르고 있다면, 그 경우를 값싸게 미리 판별할 수 있는지 살펴볼 만합니다.
- 판정은 보수적이어도 됩니다. 정확한 판정이 아니라 false negative가 없는 판정이면 충분하고, 드문 경우는 기존 경로로 처리하면 됩니다.
- allocator의 size class를 의식하세요. 몇 바이트 절약이 실제 메모리 절감으로 이어지는지는 allocator의 granularity가 결정합니다.
- 측정 도구를 신중히 고르세요.
sys.getsizeof()는 논리적 크기만 보여주므로, 이 PR에서는 RSS로 측정해야 했습니다. - 불변식은
assert로 남기세요. 최적화로 생략한 단계(normalize)가 왜 안전한지를 코드 자체가 증명하게 됩니다.
참고 자료
- sys.getsizeof — PR에서 차이를 보여주지 못한다고 언급된 크기 측정 함수
- sys.int_info — int 내부 digit 크기(bits_per_digit) 정보
- Integer Objects (C API) — PyLongObject C API 문서
- pymalloc allocator — 결과 메모리 size class를 결정하는 allocator
- pyperf — 벤치마크에 사용된 도구
⚠️ 알림: 이 분석은 AI가 실제 코드 diff를 기반으로 작성했습니다.
관련 포스트
PR Analysis 의 다른글
- 이전글 [loki] Loki LogQL: 파서 뒤 label filter를 미리 검사해 통과할 수 없는 로그 라인의 파싱 건너뛰기
- 현재글 : [cpython] CPython int 덧셈의 '혹시 몰라 할당한 1 digit' 없애기: x_add() 과할당 줄이기
- 다음글 [flashinfer] Batch-invariant attention을 Rubin에 맞춰 재배치하기: 결과 비트는 그대로 두고 decode launch grid, PDL, 하드웨어 row max 손보기
댓글