my name is Jay

rpm2cpio php-5.1.4-1.esp1.x86_64.rpm | cpio -idmv

다른 곳도 마찬가지겠지만 NHN의 페이지랭크도 다음 단계로 이루어진다.

1. 웹그래프 빌딩
2. 페이지랭크 실행
3. 기타 통계 작업

(뭐 대단한 걸 말해주나보다 싶었을텐데 너무 간단해서 실망했을 듯 하다 ㅎㅎㅎ)

하둡 기반이 아니였던 페이지랭크 모듈을 하둡 기반으로 바꾸면서 1번 단계 이후부터는 모두 자바로 바꾸었지만 1번 단계는 워낙 NHN의 자산의 일종인 링크스팸탐지 휴리스틱이 많이 들어가있었던 상태라 쉽사리 건드릴 수가 없었다. 게다가 웹 그래프 빌딩은 단위 모듈 자체 scalability의 문제가 크게 부각되지 않았던 터라 앞단부터 바꾸기 시작해야한다는 부담은 없었다.

그런데 요즘 1번 작업도 자바로 변경 개발을 시작하였다. 멀쩡히 잘 돌아가는 프로그램, 내가 다시 짜는 건 아니고, 블로그에 몇 문장 적어놓는 것으로는 독자층(이렇게 적어놓고도 너무 읽는 이들이 없어서 가슴이 아프다 ㅠ.ㅠ)에게 정당성을 이해시킬 수 있을 거 같지 않아 그냥 거두절미하고...

솔직히 난 자바 개발 경험이 별로 없다. 오픈마루에서 심심풀이로 C++로 작성된 검색엔진을 자바로 만들어본 게 시작이었고 여기와서 페이지랭크를 자바로 만들고 있으니 1년 남짓 정도 되겠다. 오픈마루에서 작업하며 놀란 건, 엄청난 자바의 생산성과 OOP의 깔끔함! 기존 코드 베이스가 있었지만 3만 라인에 달하는 C++ 검색엔진을 자바로 포팅하는데 걸린 시간은 단 한달... 놀라운 SDK, 이클립스, 자바 문법의 힘을 처음으로 느꼈다. 자바로 그렇게 만들어놓은 소스 코드는 이후 C++ 검색엔진의 리팩토링에 그대로 반영되었다.

그때 테스트한 결과, 알고리즘/데이터구조가 동일한 상태에서 C++ 버전과 자바 버전의 throughput과 response time 모두 C++이 2배 빨랐다. 모든 색인 데이터를 메모리에 올리기 때문에 IO 성능은 관련이 없다. 내가 이때 결론내린 자바 성능의 결함은 strongly typed... 좀더 무식하게 이야기하면 byte array로부터의 데이터 캐스팅이 없기 때문이었다. 무슨 말이냐면...

C에서는 메모리에 올라와있는 byte array로부터 4바이트 integer를 하나 얻어내려면

int a = *(int*)byte_array;
byte_array += sizeof(int);

하면 되지만 자바에서는

int a = ((readByte() & 0xFF) << 24) | ((readByte() & 0xFF) << 16) | ((readByte() & 0xFF) <<  8) |  (readByte() & 0xFF);

이렇게 해야된다. 이러한 차이가 2배의 성능 차이를 내는 것이라고 결론내렸다. 그때 나의 자바 스승님이신 지민아빠께서는 2배 차이면 최고의 결과라고 칭찬해주셨다. 아무 대책없이 짜면 10배 느려진다고...

그런데 두둥... 위에서 이야기한 1번 프로그램의 초기 버전 성능 차이가 정말 10배 났다 -_- IO 성능도 관련있고 자바 특성상 substring 하나 만들기 위해서도 새로운 String 객체를 하나 할당하는 등(C에서는 대충 메모리 영역에 널문자 하나만 찍어놔도 substring이 만들어진다) C에 비교해서는 불필요한 작업이 많긴 하겠지만 그래도 10배까지 차이날 지 몰랐다.

그래서 성능 튜닝을 시작했다. 솔직히 내 바램은 10배에서 2배로 줄이는 건데 얼마나 줄일 수 있을 지 모르겠다. 결과나오면 또 글 쓰겠다.

마치 STL의 세부사항까지 꿰뚫고 있어서 defect 운운하기 시작할 땐 언제고 점점 글이 -_-

뭐 그래도 단점은 단점이니까... STL은 디버깅하기 힘들다.

gdb로 디버깅하면서 vector에 저장된 메모리의 내용을 살펴보려면 복잡한 콜스택을 따라가야한다. 그래서 stdout이나 stderr로 출력하면서 디버깅을 하는 것이 더 편한 상황이 온다. 하지만 core 파일을 가지고 디버깅을 하는 경우에는 난감한 경우가 많다.

그래서 난 왠만하면 vector는 쓰지 않는다. vector 정도는 간략하게 구현할 수 있다. 물론 내부적으로 생성자/소멸자/복사생성자/assignment를 호출해주지 않으므로 primitive type이나 pointer만 저장해야한다.

vector 코드를 자세히 들여다보면 vector 내부 array가 커지거나 작아질 때 delete, new를 호출하면서 생성자, 소멸자를 함께 호출한다. 즉

vector<int> a; for (int i = 0; i < 1024; ++i) a.push_back(i);

코드를 호출하면 1024번의 생성자와 소멸자가 호출된다. primitive type이라고 해도 호출하게 되어있다. 그래서 gprof로 프로파일링해보면 저런 생성/소멸자의 호출때문에 프로파일링 데이터가 상당히 지저분해지기 쉽다. 그래서 난 왠만하면 vector를 쓰지 않는다.

또한 C++에 경험이 부족한 사람들은 vector 안에 저장하는 데이터 형식은 string 혹은 value type만을 써야한다는 것을 잘 알지 못한다. 코드가 지저분해지더라도 난 vector에 포인터만 저장한다.

일반적인 경우에 대해서 STL만큼 훌륭한 성능의 코드를 작성해내기란 굉장히 힘들다고 생각한다. 예를 들어 STL map이 차용하고 있는 Red-Black tree는 알고리즘도 꽤나 복잡해서 - insertion은 그럭저럭 코딩할만 한데, deletion은 정말 어렵다 - 빨리 개발해야 하는 경우에는 STL을 잘 쓰는 것이 매우 중요하다. 꼭 Red-Black tree가 아니더라도 훌륭하게 작동하는 balanced binary search tree를 작성하기란 쉬운 일이 아니다. 트리의 rotation을 반복하면 balancing이 된다는 게 참 ㅎㅎㅎ 식은 땀나기 쉬운 이론이다.

그런데 시간이 그리 촉박하지 않다면 난 왠만한 코드는 STL과 무관하게 작성하고자 노력한다. 물론 개발 비용이야 많이 들겠지만 최적의 성능을 만들어내는 코드를 위해서는 STL이 지원하는 거의 대부분의 기능을 직접 구현할 수 있어야 한다. 그런 취지에서 내가 생각하는 STL의 결함을 정리해보고자 한다. 관점에 따라서 이게 결함이 되지 않을 수 있다. 단지 '스펙'의 문제일 수도 있다. 자바가 C보다 느린게 결함은 아니지 않는가. 단지 언어 스펙이 그렇다는 거지.

하나씩 써 나가기로 한다.

이건 prefix 검색이 되고 string matching이 좀 빠르다는 장점이 있어서 형태소 분석기 사전에 많이 쓰인다. exact matching 자체는 hash table보다 느리고 빌딩 시에 메모리도 상상을 초월할 정도로 많이 먹는 등... prefix 검색이 아니라면 그리 좋은 구조는 아니다.

사실 내가 직접 형태소 분석기를 개발할 일이 없었기 때문에 그냥 교과서에서만 대충 보고 지나쳤고 탑코더 연습문제로 간단하게 짜본 거 외에 직접 구현해본 적은 없는데... 회사에서 Aho-Corasic을 포함하여 여러 가지 string matching 데이터 구조를 테스트한다는 이야기를 듣고 문득 트라이를 구현해보고 싶어졌다.

선택한 알고리즘과 구조는 모란소프트 조영환 박사님꺼... 그림을 보고 고대로 구현해서 엔씨 오픈마루 심보준님에게 성능 비교를 의뢰한 바.. ㅋㅋㅋ 내께 조금 더 빨랐단다.

사실 이 포스팅은 이거 자랑하려고 ^^

조박사님 트라이 포스팅이 얼마나 유명하면 구글에서 '한국어 웹' 검색으로 trie라고 치면 1등으로 나온다.

http://hanigamo.egloos.com/1001847

unordered set/map으로는 최고의 성능을 발휘하는 게 hash table이다. 꼭 extendible하지 않아도 버킷 크기가 1024*1024개 정도 되면 어지간한 크기의 색인어들을 모두 저장하고도 남으며 lookup 성능도 결코 개선의 여지가 없을 정도로 잘 나온다. 문제는 두 가지...

1. 좋은 해시 함수
2. 메모리 lay out

좋은 해시 함수를 고안해내는 건 고도의 수학적 배경을 필요로 하는데 그냥 Bob Jenkinson의 해시 함수를 쓰거나 MD5Hash의 8바이트를 쓰거나 해도 된다. Bob 아저씨의 해시 함수를 강추한다.

사실 hash table에서 key의 collision이 일어났을 때 open addressing으로 해결하느냐 chaining으로 해결하느냐에 따라서 구조가 달라지는데 교과서에는 chaining이 더 성능이 우수하다고 나온다. 그런데 사실 두개 똑같은거 아닌가?

검색엔진에서 색인 데이터를 메모리에 최대한 많이 올리려면 데이터 구조의 메모리 layout을 최대한 sequential하게 사용하여 heap fragmentation을 최소화해야한다. Jon Bentley의 Programming Pearls에도 나오는 문제이며 '좋은' 회사의 프로그래밍 인터뷰에서도 꽤나 자주 등장하는 문제이다. 내 생각에 sequential array에 모든 데이터를 저장해놓고 open addressing하는 방식으로 chain을 생성하고 bucket을 만드는 것이 가장 효율적인 메모리 layout일 것이다.

엔씨에서 처음 엔진을 만들기 시작할 때 색인 저장소로 B-tree를 쓰려고 했었다. 동적 색인을 위해서 포스팅 데이터의 크기가 작으면(블록 크기보다 작으면) 포스팅 데이터 자체를 B-tree의 leaf에 저장하고, 그렇지 않으면 별도 heap file에 저장하고 링크만 leaf에 저장하는 구조를 선택했었다.

맨날 야근하고 집에서는 회사 서버에 접속이 안되서 pseudo-code써놨다가 출근해서 구현하고... 아주 난리를 쳤는데, 이때 가장 어려운 버퍼 매니저는 민보가 짰었다. 다 만들고 났더니 이런 -_- fill factor가 너무 낮아서 공간 효율성이 별로다. fill factor를 높이려면 prefix로 압축해야 하는데 너무 어렵다. 공간 효율성이 별로니 많은 데이터를 메모리에 올리기도 힘들고, 블록 구조이다보니 메모리에 올라와있다고 한들 throughput이 잘 안나온다.

뭐 한마디로 구현하기는 복잡한데 만들어놔도 오픈소스 패키지에 비해서 성능도 안나오는... 한마디로 철저하게 연습용 데이터 구조되겠다.

concurrency, 디스크 IO, binary search 등을 모두 구현해야 하므로 코딩 스킬 키우는 데는 최고다!

전산학과 학생 혹은 개발자에게 가장 기본적이고 중요한 소양인 데이터 구조...

일반적으로 '좋다'고 소문난 소프트웨어 개발 회사들은 입사 기술 인터뷰로 간단한 데이터 구조와 알고리즘 퀴즈를 내면서 손으로 코드를 작성해보라고 한다. 이력서와 말만으로는 개인의 개발 능력을 정확하게 가늠하기 힘들다.

학교다닐 때는 데이터 구조와 알고리즘이 그렇게나 중요한 지 몰랐고 솔루션 회사에서 API 코딩만 하고 있을 때도 사실 몰랐다. 구글 인터뷰에서 쓴 물을 마시고 미국 비컴 사람들과 함께 프로젝트하고 엔씨에서 엔진 개발을 바닥부터 시작하면서 느끼게 된 것...

큐, 스택, 리스트 이런 것보다는 문제를 효율적으로 해결하는 방법 자체가 중요할텐데 문제를 해결하는 수단이 데이터 구조 및 알고리즘이 아닐까 싶다. 구구단을 외워서 계산을 빨리 하듯이 말이다.

검색엔진 개발을 하면서 꼭 한번 구현해보라고 권하고 싶은 데이터 구조 3가지가 있다.

1. b-tree
2. hash table
3. trie

글 편수를 늘리기 위해 자세한 이야기는 다음에 ㅋㅋㅋ

1. 열심히 논문 읽는 데 이해안될 때...

2. 힘들게 이해한 뒤 구현해서 실험했는데 결과 이상할 때...

3. 데이터가 달라서일까, 내 구현의 버그일까, 고민할 때...

인간들 좀 쉽게 써주면 어디가 덧나나 ㅠ.ㅠ

선형대수와 통계 및 해석학을 잘 알면 많이 도움이 될 거 같은데 그렇다고 지금 수학책 펴놓고 공부할 수도 없고...