[코드이야기] 자바 JDK의 버그

Jon Bentley가 CMU에서 박사과정 학생들을 불러서 binary search 알고리즘을 써보라고 하였다.

당연히 binary search 알고리즘은 아주 기본적인 알고리즘이기 때문에 간단하게 구현할 수 있었을 것이다.

하지만, 모든 학생들의 코드에는 버그가 있었다.

그건, 무엇일까?

아래는 java.util.Arrays에 있는 실제 코드이다.

1:     public static int binarySearch(int[] a, int key) {
2:         int low = 0;
3:         int high = a.length - 1;
4:
5:         while (low <= high) {
6:             int mid = (low + high) / 2;
7:             int midVal = a[mid];
8:
9:             if (midVal < key)
10:                 low = mid + 1
11:             else if (midVal > key)
12:                 high = mid - 1;
13:             else
14:                 return mid; // key found
15:         }
16:         return -(low + 1);  // key not found.
17:     }

이 코드는 1946년에 추가 되었으며, 버그가 발견되지 않다가 1962년, 20년이 지난 후에야 버그가 발견되었다.

앞에서 말했듯이 binary search는 기본적인 알고리즘이여서 아주 많이 쓰였을꺼다.

20년동안 계속 쓰였으니 못해도 수백억번은 불렸을 것이다.

그런데 20년이 지나서야 버그가 발견되었다.

어느 부분이 버그인지 알아 차렸나?

6번째 라인을 주시해서 보아라.

합(sum)

Integer

버그를 고친 코드: int mid = low + ((high - low) / 2);

몇번째 힌트를 보고 알아차렸는가?

버그가 있는 부분은 아래의 6번째 라인이다.

6:             int mid = (low + high) / 2;

이거만 봐도 머가 버그지? 하면서 알아차리지 못한 사람들이 많을 것이다.

low, high, mid는 모두 integer형이다. 그렇다면 low+high가 2^32가 넘는다면?

그렇다. Overflow가 일어나는 것이다. 그럼 mid값은 완전 다른 값(음수)이 나올것이다.

int mid = low + ((high - low) / 2);

이런식으로 더하기 대신 빼기를 사용하면 overflow를 방지 할 수 있다. 그런데 기존 코드보단 좀 느리다.

int mid = (low + high) >>> 1;

나,

int mid = ((unsigned int)low + (unsigned int)high)) >> 1;

이런식으로 성능의 저하 없이 고쳐 쓸 수 있다.

PS. >>> operator는 logical shift이다. 부호 extend를 하지 않는다.

자. 이제 이 코드는 버그가 없을까? bug-free 과연?

그렇다고 느끼겠지만, 모른다.

물론 2^32는 정말 큰 수이다. 

메모리문제등등 때문이더라도, 이 만큼의 배열을 가지고 있을 확률도 정말 낮을 것이다.

모든 버그를 고치기 위해선 모든 input에대한 테스트가 필요하다.

하지만 그건 당연히 거의 불가능한 일이다.

그렇지만, 이 일례를 통해 

어떤 코드든(특히 내가 짠 코드) 버그가 있을 수 밖에 없고, 

이것을 최소화하기 위해선 잘짜여진 테스트도구가 중요할것이다.

참조 : http://googleresearch.blogspot.kr/2006/06/extra-extra-read-all-about-it-nearly.html