앞 글에서 자리 수가 곧 한계라고 했다. 그 한계에 도달하면 어떤 일이 벌어지는지 본다.
주행계는 최대에서 멈추지 않는다
오래된 자동차 주행계를 떠올려 보자. 숫자 바퀴 여섯 개가 돌아가며 거리를 센다. 999999km를 달린 다음 1km를 더 달리면 어떻게 될까.
멈추지 않는다. 000000으로 돌아간다. 바퀴가 여섯 개뿐이라 일곱째 자리를 올릴 데가 없어서다. 계기판은 아무 경고도 하지 않고, 방금 백만 킬로미터를 달린 차가 새 차처럼 보인다.
정수 오버플로가 정확히 이 일이다. 그리고 이 주행계 비유 하나로 이 글이 굴러간다.
자리가 모자라면 되감긴다
컴퓨터에서 정수를 담는 칸은 대개 32비트 아니면 64비트다. 32비트짜리 칸에 담을 수 있는 가장 큰 수는 2,147,483,647, 대략 21억이다.
여기에 1을 더하면 어떻게 될까.
오른쪽 끝에서 한 칸 더 가면 멈추는 게 아니라 왼쪽 끝으로 들어온다. 주행계가 000000으로 돌아가는 것과 같다.
-2,147,483,648이 된다. 가장 큰 수 다음이 가장 작은 수다. 주행계가 000000으로 돌아가듯, 올릴 자리가 없어서 맨 끝에서 맨 앞으로 감긴 것이다.
int max = 2147483647;
System.out.println(max + 1); // -2147483648왜 하필 음수로 떨어지나
되감기는 건 알겠는데 왜 0이 아니라 음수일까. 음수를 담는 방식 때문이다.
자리가 32개뿐인데 음수도 담아야 하니, 맨 앞 자리 하나를 부호에 쓴다. 앞자리가 0이면 양수, 1이면 음수다. 그런데 단순히 “앞자리만 뒤집으면 음수”로 하지 않고, 컴퓨터는 2의 보수라는 방식을 쓴다.
2의 보수를 한 줄로 말하면 이렇다. 뺄셈을 덧셈으로 처리하려고, 음수를 “더하면 0이 되는 수”로 정의한 것이다. -1은 모든 자리가 1인 값이고, 거기에 1을 더하면 자리가 전부 넘쳐 0이 된다.
이 방식의 값은 회로가 단순해지는 것이다. 뺄셈 회로를 따로 만들 필요가 없다. 대가는 우리가 방금 본 그것이다. 양수의 끝과 음수의 시작이 맞닿아 있어서, 한 칸만 넘으면 부호가 뒤집힌다.
부호를 안 쓰기로 하면(부호 없는 정수) 32비트로 0부터 약 43억까지 담는다. 자리 하나를 부호에 안 뺏겨서 위쪽이 두 배로 넓어지는 것이다. 대신 음수를 아예 못 담고, 0에서 1을 빼면 43억이 나온다. 되감기는 성질 자체는 그대로다.
넘침은 조용하다
가장 나쁜 성질은 따로 있다. 아무도 알려 주지 않는다는 것이다.
주행계는 경고등을 켜지 않는다. 마찬가지로 대부분의 언어에서 정수 오버플로는 예외를 던지지 않는다. 계산은 성공하고, 프로그램은 계속 돌고, 값만 틀린다.
그래서 증상이 이렇게 나타난다.
- 합계가 갑자기 음수로 표시된다
- 조회수가 21억을 넘긴 순간 순위가 맨 아래로 내려간다
- 잘 돌던 배치가 데이터가 늘어난 어느 날부터 이상한 결과를 낸다
틀린 값이 정상적인 값처럼 생겼다는 게 핵심이다. 로그를 봐도 에러가 없다.
한가운데서 터진다
넘침이 가장 얄궂게 나타나는 자리는 최종 결과가 아니라 계산 도중이다.
두 수의 가운데를 구한다고 하자. (a + b) / 2는 누가 봐도 맞는 식이다. a도 b도 21억 안쪽이라 각각은 멀쩡하다. 그런데 더한 순간 이야기가 달라진다.
두 식의 답은 같다. 다른 것은 도중에 만들어지는 값이고, 그 값이 벽 안에 머무는 쪽만 살아남는다.
a + b가 먼저 계산되면서 칸을 넘고, 음수가 되어 버린다. 그 음수를 2로 나누니 가운데는커녕 범위 밖의 값이 나온다.
// 위험: 더하는 순간 넘칠 수 있다
int mid = (low + high) / 2;
// 안전: 차이의 절반만 더한다. 중간에 큰 값이 안 생긴다
int mid = low + (high - low) / 2;이 버그는 반씩 잘라 찾는 알고리즘의 표준 구현에 오래 숨어 있었던 것으로 유명하다. 최종 답이 아니라 도중의 값이 넘쳤기 때문에 눈에 안 띈 것이다. 입력이 작을 때는 영원히 재현되지 않는다는 점도 발견을 늦췄다.
이름만 같은 다른 이야기
오버플로라는 말은 다른 자리에서도 쓰인다. 스택 오버플로다. 이름이 같아 헷갈리기 쉬운데 전혀 다른 사고다.
| 정수 오버플로 | 스택 오버플로 | |
|---|---|---|
| 넘치는 것 | 값이 담긴 칸의 자리 수 | 함수 호출을 쌓아 두는 메모리 영역 |
| 증상 | 조용히 틀린 값 | 프로그램이 즉시 죽는다 |
| 알아채기 | 어렵다 | 쉽다(예외가 뜬다) |
메모리가 어떻게 나뉘어 쓰이는지는 다른 글에서 다뤘다. 여기서는 이름이 같을 뿐 원인이 다르다는 것만 짚어 두면 된다. 이 시리즈에서 오버플로라고 하면 늘 앞엣것이다.
실무에서: 언제 물어야 하나
실무에서 정수 넘침을 만나는 자리는 대체로 정해져 있다.
- 시간 - 초를 32비트에 담는 방식은 2038년에 되감긴다. 지금도 오래된 시스템에서 미래 날짜를 계산하다 걸린다.
- 누적값 - 조회수, 합계, 바이트 수처럼 계속 커지기만 하는 값이다. 처음 설계할 때는 21억이 아득해 보이지만 로그성 데이터는 금세 닿는다.
- 곱셈 - 덧셈보다 훨씬 빨리 넘친다. 5만 곱하기 5만이면 이미 25억이다.
- 자바스크립트의 큰 수 - 여기는 사정이 좀 다르다. 정수 타입이 따로 없고 다음 글에서 볼 부동소수점으로 수를 담아서, 약 9천조를 넘으면 정확도가 무너진다. 서버가 보낸 64비트 ID를 브라우저가 받아 JSON으로 주고받다 뒷자리가 바뀌는 사고가 여기서 나온다. 그래서 큰 ID는 문자열로 보내는 관행이 생겼다.
대응은 대개 간단하다. 누적되는 값은 처음부터 64비트로 잡는다. 64비트면 922경까지 담으니 현실의 누적값으로는 닿기 어렵다. DB 컬럼도 마찬가지로, 운영 중에 int를 bigint로 바꾸는 일은 데이터가 쌓인 뒤라 훨씬 비싸다.
정리
- 정수를 담는 칸은 자리 수가 정해져 있고, 넘으면 주행계처럼 되감긴다.
- 최대값 다음이 최소값인 이유는 2의 보수 때문이다. 뺄셈 회로를 없애 얻은 값의 대가다.
- 넘침은 예외를 던지지 않는다. 계산은 성공하고 값만 틀린다. 그래서 찾기 어렵다.
- 최종 결과보다 계산 도중이 위험하다.
(a+b)/2는a + (b-a)/2로 쓴다. - 스택 오버플로는 이름만 같은 다른 사고다.
- 누적되는 값은 처음부터 64비트로 잡는 것이 가장 싼 대비다.
다음 글은 정수 옆칸을 본다. 소수점이 붙는 순간 정확함이 어떻게 달라지는지가 주제다.