앞서 포스팅 한 "뉴욕의 프로그래머" 라는 책에서 언급하고 있는 이야기 중 하나이다. 
원래 이것은 조수아 블로흐( Joshua Bloch ) 라는 유명한 소프트웨어 엔지니어가 구글랩 블로그에 올린 글에서 유래하는 이야기이다.  조수아 블로흐는 자바 플랫폼의 유명한 개발자이자 Effective Java (2001년 Jolt Award 수상작)  의 저자이기도 하다. 현재 구글에서 자바 아키텍트로 근무중.

글의 원문 : Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken

저자가 카네기멜론 대학의 박사과정에 입학해서, 알고리즘 수업을 듣던 첫날, 존 벤틀리 교수 (Jon Bentley, Programming Pearl 의 저자, 국내에는 "생각하는 프로그래밍" 이란 책으로 번역. ) 가 학생들에서 이진검색을 구현해 보라고 시킨 후에 그중 몇명을 앞에 나와서 발표하라고 했을 때의 충격을 아직도 기억하고 있다고 쓰고 있다. 물론, 당연하게도 ^^, 대부분의 학생들이 구현한 이진검색은 버그가 있었다.

문제는 자바 라이브러리에 기본으로 포함되어 있던 이진검색 조차도 버그가 숨어있었다는 것이다. 아래 글을 읽어보면 왜 20 여년간이나 이 버그가 쉽게 발견되지 않았는지에 대한 설명이 있다. 수십년간 사람들이 아무 문제없이 써오던 대중적인 라이브러리에도 이와같이 숨어있는 버그를 지적하면서 Bug-Free 소프트웨어가 얼마나 힘든 것인지를 말하고 있다.

최근까지 Java.util.Arrays 에 포함되어 기본 라이브러리로 제공되던 바이너리 서치의 코드는 아래와 같다.


자, 이 코드의 어떤 부분에 버그가 있을까..

정답은 아래 라인이다.

만약 low 와 high 가 충분히 큰 숫자라서 이 두수의 합이 integer 의 범위 ( 32 비트의 경우 2,147,483,648 ) 를 넘어서게 되면 결국 Overflow 가 발생하게 된다. 그래서  이 부분에서
mid 값을 배열 a 의 인덱스로 사용한 부분에서 배열의 잘못된 인덱스로 접근하게 되어 생기는 
ArrayIndexOutOfBoundsException 에러가 나게 된다.

 * 주의사항 : 조수아 벤틀리는 원문에서 두 양수의 합이 Overflow 가 나는 경우 그 결과는 음수가 되어 배열의 인덱스를 음수로 접근하게 되어 ArrayIndexOutOfBoundsException 에러가 난다고 쓰고 있으나, 후에 덧글을 통해서 C99 스펙의 경우 signed integer 의 두 수의 overflow 의 경우 항상 음수가 되는 것은 아닌 undefined 가 된다고 수정하고 있다. 어쨌든 에러는 에러이다... ^^ ;

조수아 벤틀리는 이 라인을 아래와 같이 고치는 것이 좋겠다고 쓰고 있다. ( C / C++ 의 경우 )
 
참고로 비트연산자 >> 1 은 /2 와 같다. >> 1 과 같이 비트연산으로 계산을 할 경우 /2 보다 조금 더 빠르다. ;)

- 그런데, 조수아 벤틀리가 제시한 저 수정안도 low 와 high 의 값의 합이 unsigned int 의 범위를 넘게 된다면 여전히 Overflow 문제가 생길 수 있다... -_-;  결국 ASSERT 등을 사용해서 인덱스의 범위 내에서만 사용이 가능하도록 제약을 걸거나, Overflow 를 피하려면 여유있게 long long 과 같은 64 비트 변수를 쓰는 것이 보다 안전할 것 같다.


댓글을 달아주세요!
  1. 김훈동 2010.06.30 12:59 신고  댓글주소  수정/삭제  댓글쓰기

    위 내용하고는 다른 내용인데..
    최근에 발견한 win32 api 버그는 머냐면... 소켓통신 관련된 모듈인데..
    xp 에서는 잘되는 놈인데... vista 랑 windows7 에서는 버그가 있더라고..왜그러나 하고 디버깅을 해보니까...
    ip 를 처리하는 모듈이 vista 이상의 os 에서 default 로 활성화 되어 있는 ipv6 땜에 ipv6 로 ip 를 받았다가
    내부적인 코드에서 문제가 발생하고 있더라고...

    또 하나 위하고는 다른 내용인데...
    아폴로 XX 호 던가... 그 40초만에 로켓트가 터져버린 사건...
    그사건의 원이이 바로.. 저런거 때문이었었다지.... 하드웨어적인 결함이 아닌 숫자형 type 하나를 잘못쓰는것으로 인하여
    로켓트가 폭발해버리는..

    • BlogIcon mynotepad 2010.07.08 01:46 신고  댓글주소  수정/삭제

      오호... 그런 일이 있었군...

      근데 그 공중폭팔한 아폴로 호는 내가 듣기로는 연료 계통에서 문제가 있어서 폭팔했다고 하던데.. 소프트웨어 문제도 있었낭..??

  2. BlogIcon hyperdash 2010.07.03 00:37 신고  댓글주소  수정/삭제  댓글쓰기

    포스팅이 프로그래밍 관련 일색이구나....

    일상에서는 포스팅 할 것이 없어진 것이냐...

    • BlogIcon mynotepad 2010.07.08 01:47 신고  댓글주소  수정/삭제

      있긴한데 요새 자꾸 게을러져서...

      그리고 그냥 공부하는 거 가끔 블로깅 하는게 나한테 맞는 거 같아서...

      개인적인 이야기 블로그에 올리는 건 별로 안좋아해서..

  3. 2010.07.13 23:36  댓글주소  수정/삭제  댓글쓰기

    비밀댓글입니다

이름 암호 홈페이지