'IT'에 해당되는 글 3건

  1. 2013.02.07 [코드이야기] 자바 JDK의 버그
  2. 2013.01.21 OpenCL 에러
  3. 2013.01.07 야후 코리아 철수 (2)

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년이 지나서야 버그가 발견되었다.


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


힌트1


힌트2


힌트3


힌트4










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


버그가 있는 부분은 아래의 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



저작자 표시 비영리 변경 금지
신고

'Program Language' 카테고리의 다른 글

[C#] toString assembly  (0) 2013.02.11
[코드이야기] 자바 JDK의 버그  (0) 2013.02.07
OpenMP 디버깅 Tips  (0) 2012.07.31
OpenCL Typedef enum  (0) 2012.04.26
yacc, bison highlight plugin for eclipse  (0) 2011.12.19
if 안에 boolean expression Optimization  (0) 2011.09.16
Posted by Leo 리오 트랙백 0 : 댓글 0

OpenCL 에러

2013.01.21 14:20 from Program Language/OpenCL

void boo()

{

if(get_local_id(2)!=0) return;

foo();

barrier(CLK_LOCAL_MEM_FENCE);

}


작동 안한다.

알아서 작동할 줄 알았는데....


void boo()

{

if(get_local_id(2)!=0) 

foo();

barrier(CLK_LOCAL_MEM_FENCE);

}


이렇게 하자.






atomic 함수는 shared-reg에 써도 느리다.


왠만하면 피하자!


branch divergence를 유발한다!







저작자 표시 비영리 변경 금지
신고

'Program Language > OpenCL' 카테고리의 다른 글

GPGPU Computing의 기본 개념.  (0) 2013.04.19
OpenCL 에러  (0) 2013.01.21
global memory replay overhead  (0) 2012.12.21
[CUDA] occupancy  (0) 2012.11.07
NVIDIA clEnqueueReadBuffer non-blocking bug(?)  (0) 2012.11.02
Intel opencl platform analyzer  (0) 2012.10.15
TAG IT, OpenCL
Posted by Leo 리오 트랙백 0 : 댓글 0




지난해 12월 31일자로 서비스를 종료한 야후코리아의 직원이 자신의 블로그를 통해 밝힌 '한국을 떠나는 외국기업들 : 침략자를 몰아낸 집주인의 승리인가?'라는 제목의 글이 트위터,페이스 북 등 SNS를 통해 빠르게 확산되며 파문을 일으키고 있다.
 
야후코리아의 前직원으로 알려진 이 블로거는 지난해 한국시장에서 철수한 야후코리아(Yahoo Korea)의 사업실패의 원인을 소비자의 탓으로 돌리는 내용의 글을 지난 1일 자신의 블로그에 올렸다.
 
그는 자신의 글에서 한국 언론은 야후코리아 철수가 ‘IT 트랜드를 따라잡지 못했기 때문’이라고 분석했지만 이는 사실이 아니며 외국계 기업이 한국 기업과 승부를 겨루기엔 출혈이 너무 큰 데다 명분도 딱히 없을 정도로 한국시장이 중국이나 동남아시아에 비해 매력적이지 않기 때문에 한국시장을 '버리는'것이라고  밝혔다.
 
이어 그는 외국계 기업들이 한국에서 철수하는 이유를 크게 '지나치게 까다로운 소비자의 입맛''로컬기업들의 치열한 선두경쟁'으로 들었다. 
 
그는 외국계 기업들의 철수가 '지나치게 까다로운 소비자 입맛’때문이며 “비슷한 환경과 조건이라면 기업은 소비자에게 덜 시달리는 시장을 선택할 것”이고 “한국과 일본은 로컬 기업들의 선두경쟁이 치열해 (외국기업이)피를 흘리면서까지 시장에 진입할 이유가 없다"고 부연했다.

또한 그는 야후를 비롯해 최근 모토로라, HTC, 골드만삭스자산운용, GM(제너럴모터스) 등 한국을 떠난 여러 업계의 외국 기업이 한국 시장 철수나 인력 감축을 결정한 것에 대해 언급하며 “철수하는 기업 당 적게는 200~300명 많게는 수천 명의 직원들이 직장을 잃게 되는데, 이런 기업이 7~8개만 돼도 그 숫자는 상당히 커진다”고 했다. 
 
그는 이럴 경우 “결국엔 전자제품은 삼성, 자동차는 현대, 유통은 롯데, 통신사는 SK를 사용할 수밖에 없게 돼 장기적으로는 소비자 선택의 폭이 감소될 것”이라고 우려했다.
 
그는 글의 마지막 부분에서  "이 사태의 가장 큰 책임은 바로 소비자에게 있다"며 "자신을 편하게 해주기만 하는 기업의 맞춤형 상품만을 소비하는 수동적 소비자가 되기보다는, 약간의 불편함을 감수하면서도 다양한 상품들을 사용해 보면서 보다 국제적인 시야를 갖추려는 능동적 소비자가 될 필요가 있다"고 결론을 내리고 한국 소비자들을 향해 일침을 가했다.
 
하지만 그는 자신의 글이 트위터와 페이스북 등 SNS를 통해 급속히 펴지며 논란의 대상이 되자 지난4일 원문을 삭제했다.

한편, 야후코리아는 지난 해 10월 “올해 말 한국에서 철수한다.”고 전격 발표한 뒤 직원들에게 스스로 일자리를 찾아서 나가라고 일방적으로 통보한 바 있다.






야후, 모토로라, HTC 세계적 IT대기업들이 한국시장을 버렸다.


우리나라 기업이 잘되는게 보기좋긴 하지만, 소비자가 선택권을 잃어간다는건 심각한일이 될수있다.


그래도 지금 네이버 - 다음 - 구글 세강이 있지만, 누구하나가 독점하게되면 


소비자가 기업을 선택하는게 아닌 기업이 소비자를 선택하게 될것이다.






저작자 표시 비영리 변경 금지
신고

'Thinking Differently' 카테고리의 다른 글

카카오톡 PC지원이 갖는 의미  (0) 2013.04.04
야후 코리아 철수  (2) 2013.01.07
종교  (0) 2012.03.28
노가다  (2) 2012.02.03
Cauly  (0) 2011.12.29
TAG IT
Posted by Leo 리오 트랙백 0 : 댓글 2