The Lost Dialogue

"단기 4342년 늦은 가을의 LDK"

'c++'에 해당되는 글 4건

  1. 2010.01.21 STL std::set 에 저장된 엘리먼트의 값을 바꿔보자. (16)
  2. 2007.07.24 날 바꾸려 하지 마세요. (2)
  3. 2007.07.04 cxx에 얽힌 사연 (9)
  4. 2007.07.03 Valgrind, 사랑해! (6)

한동안 굉장히 속을 썩이는 코드가 있었는데,  별 기대없이 펼친 Effective STL 에서 해결책을 찾았다.

STL std::set 자료구조에 한 번 들어간 엘리먼트는 본래 업데이트가 안된다. 예를 들어,


set<int> s;
s.insert(1);
s.insert(2);
set<int>::iterator si = s.find(2);
(*si) = 10;     // 이 부분 때문에 이 코드는 컴파일이 안된다.

컴파일이 안되는 경우는, 저렇게 한 번 들어간 엘리먼트의 값을 바꿀 경우 전체 자료구조의 정렬된 상태가 망가지기 때문이다. 예를 int 타입으로 들었기 때문에, 왜 굳이 저 값을 바꿀려고 하는지 아무도 이해 못할 것 같은데, 사실은 다음과 같은 문제가 있다.


set<sibilla::path_t>::iterator where = v->find(p);
if (where != v->end()) 
    where->update_with_new(p);     // 이 부분 때문에 이 코드는 컴파일이 안된다.
else 
    v->insert(p);

path_t을 엘리먼트로 가지는 자료구조가 setv라는 데이터 저장소를 생각해보자. 새로운 데이터인 p가 들어오면 이게 저장소 v에 있는지 검색하고 없으면 새로 넣되, 있을 경우 기존의 값을 업데이트 하는 것이다. 위와 같이 쓰면 아주 깔끔한데, 문제는 저게 컴파일이 안된다는 거다. 읽기 전용 영역을 건드린다는 에러가 난다. 몇몇 STL 구현에서는 컴파일이 되는 경우도 있다고 하지만, 현재 사용 중인 g++ 4.2.4 환경에서는 컴파일이 되지 않았다. 그래서 결국은 다음과 같이 해야만 했는데,


set<sibilla::path_t>::iterator where = v->find(p);
if (where != v->end()) 
    path_t update_p = *(where);      // (1) 일단 사본을 따로 만들고,
    update_p.update_with_new(p);  // (2) 사본을 업데이트 하고,
    v->erase(where);        // (3) 원래 있던건 지우고,
    v->insert(update_p);    // (4) 업데이트한 사본을 다시 저장한다.
else 
    v->insert(p);

위 코드가 나름대로의 정석 플레이라 할 수 있는데, (1), (3), (4) 작업이 언뜻보기에도 굉장히 불합리해보인다. 게다가 이 path_t  자료구조가 크기가 만만치 않기 때문에 (내부에 vector가 하나 달려있는데, 이것의 크기는 영원히 늘어날 수 있다. 이론상 1600만개 정도를 최대치로 보고 있다.) 이걸 꺼냈다가 다시 넣는건 분명 좋은 생각이 아니다. update_with_new 함수에서 액세스하고자 하는 path_t 의 멤버변수는 path_t::operator< 에서 사용하는 멤버가 아니므로, set 자료구조의 정렬 상태를 망가뜨릴 염려도 없다. 그래서 다음과 같이 해결을 했다.


set<sibilla::path_t>::iterator where = v->find(p);
if (where != v->end()) 
    const_cast<path_t&>(*where).update_with_new(p);     // 이렇게 캐스팅을 한다.
else 
    v->insert(p);

자, 이제 컴파일도 잘 되고 이전과는 비교도 할 수 없을정도로 빠른 코드가 나왔다. 대충 보니, 이전에 2011초 걸리던 작업이 이제 40초만에 완료가 되었다. 50시간 걸리던 코드가 이제 잘 하면 1시간 안에 돌아갈 것 같다.


* 사실 이렇게 저 부분만 놓고 보면 문제가 명확해 보이지만, 한참 테스트를 할 때는 엉뚱한 곳을 계속해서 최적화하고 있었다. path_t 타입 안에는 무한히 늘어나는 vector가 하나 있다고 위에서 말했는데, 사실은 vector가 아니라 set이었다. 프로그램이 너무 느리다보니 막연히 path_t 안에 들어있던 set에 문제가 있다고 생각했다. 데이터를 업데이트할 때마다 set을 검색하는 오버헤드가 문제라 생각하고 이걸 vector로 대체한 것이었다. 그냥 vector에 push_back만 해두고 일이 다 끝난 다음에 일괄적으로 set으로 변형할 생각이었는데, 이렇게 바꿔봐도 여전히 느리더군.

* gprof로 프로파일링을 해보니, 결국 문제는 엉뚱하게도 path_t의 대입 연산자 (operator=) 에서 발견 되었다. set에서 path_t 타입을 꺼내고 또 다시 넣는 과정에서 생기는 오버헤드가 진정한 문제였던 것이다.

* 역시 문제는 정공법으로 풀어야한다. 프로파일러를 사용하자.

* 막상 인터넷에서 검색할 땐 뾰족한 해결책을 찾기 힘들었는데, 오랫동안 잊고 지내던 책에서 해답을 찾았다. 아무리 인터넷이 발전하고 많은걸 검색할 수 있어도, 여전히 책에서 얻을 수 있는 지혜가 많다.

내 오더는 내가 내린다!

오늘은 다 함께 C++의 판타스틱한 const의 세계로 빠져들어 볼까요?

const int* const method(const int* const&) const;

여기서 const는 5번 사용되었다. 이 메서드가 반환한 포인터가 가리키는 값은 건드리지 말 것. 반환한 포인터 그 자체도 건드리지 말 것. 메서드는 매개변수의 포인터가 가리키는 값을 건드리지 말 것. 매개변수의 포인터& 그 자체도 건드리지 말 것. 끝으로 이 메서드는 자기가 속하여 있는 개체의 멤버를 건드리지 말 것 ... 이라고 말하고 있다.

여기서 건드리는건 읽기만 하는게 아니라 쓰기도 하는겁니다.

'아트 앤 싸이언스 > 별난 세상' 카테고리의 다른 글

커피 미학  (6) 2007.07.27
뮤직 인 마이 하트  (0) 2007.07.25
날 바꾸려 하지 마세요.  (2) 2007.07.24
티 로프트  (10) 2007.07.15
워드 파일 살려요!  (39) 2007.07.09
cxx에 얽힌 사연  (9) 2007.07.04
TAG c++
__gnu_cxx

C++ 프로그래밍을 하다보면 종종 마주치는 cxx.
왠지 직관적으로 C가 아니라 C++인 듯하다! 란 느낌만 모호하게 주던 cxx.

Makefile에서도 CXX 환경 변수로 C++ 컴파일러를 지정하기 때문에 더 친숙한 cxx.

지난 새벽에 hash_map 정보를 찾다가 우연히 발견했는데, x는 +를 45도 기울인거랜다.
즉 cxx == c++
+를 쓸 수 없는 상황에선 x로 표현하면 된다.

참고로 hash_map의 헤더는 ext/hash_map
아직 표준은 아닌거 같고, 내 시스템에선 __gnu_cxx 네임스페이스 안에 있더군.

키를 char*가 아니라 std::string으로 쓰면 (많이 느릴거 같아도) 쓸 때(는) 유용할텐데,
기본 제공 __gnu_cxx::hash 템플릿이 std::string과는 친하지 않은 관계로 전개 버전 하나를 분명하게 만들어 주어야만 한다. STL은 std::string을 그렇게나 밀면서 hash 키는 char*를 쓰라네.

어쨌든 이렇게 하나 만들어주자.

using namespace __gnu_cxx; 
namespace __gnu_cxx {
template<>struct hash<std::string>{
size_t operator()( const std::string& x ) const {
return hash<const char*>()( x.c_str() );
}
};
};

이제 다음과 같이 map과 거의 같은 형태로 hash_map을 사용할 수 있다.

typedef hash_map<std::string, std::set<sibilla::path_t>> path_map_t;
path_map_t interpath_pool;


내친 김에 hash_map 생성사 옵션 인자로 _HashFcn, _EqualKey 펑터 얘기도 써둘까 했는데, 꺽쇠 <> 문제 때문에 이만 줄인다. 문자표에서 꺽쇠 찾기 너무 어려워요. 흑흑.

__gnu_cxx::hash 템플릿은 /usr/include/c++/4.1.2/ext/hash_fun.h
나머진 /usr/include/c++/4.1.2/ext/hash_map 참고.

'아트 앤 싸이언스 > 별난 세상' 카테고리의 다른 글

티 로프트  (10) 2007.07.15
워드 파일 살려요!  (39) 2007.07.09
cxx에 얽힌 사연  (9) 2007.07.04
Valgrind, 사랑해!  (6) 2007.07.03
63빌딩 프로젝트  (14) 2007.07.02
2007년의 CDP  (14) 2007.06.01
TAG c++
사랑해요, Valgrind.
나의 주말을 지켜주셨어요. 덕분에 오늘은 밤새지 않겠습니다.

==7303== 314,855,244 bytes in 9,541,068 blocks are definitely lost in loss record 18 of 18
==7303== at 0x401D4B0: malloc (vg_replace_malloc.c:149)
==7303== by 0x804B9F9: Pool::_binary(char*) (pool.cpp:132)
==7303== by 0x804BBBE: Pool::read_mrt(std::istream&) (pool.cpp:208)
==7303== by 0x804C8E0: main (pool.cpp:548)

메모리 릭으로 고생하시는 분들 많죠? Valgrind 설치하고 돌려보3.
(아, 이렇게 깔끔하게 잘 컴파일되는 프로그램도 참 오랜만. 속는셈치고 일단 한번 돌려봐요.)

$ valgrind --tool=memcheck --leak-check=full --log-file="./valgrind_log" ./your_program

--tool로 세부 툴을 선택하고, --leak-check=full 식으로 세부 옵션을 주면 된다.

로그 파일엔 ==와 ==로 둘러쌓인 프로세스 아이디, 에러 메시지, 에러가 발생한 코드 상의 위치, 문제가 발생한 메모리 주소가 출력된다. 로그 파일의 끝 무렵에는 각종 에러들에 대한 요약 리포트를 발견할 수 있다. 에러 메시지의 예는 다음과 같다.

Illegal read / Illegal write errors
Use of uninitialised values
Illegal frees
When a block is freed with an inappropriate deallocation function
Passing system call parameters with inadequate read/write permissions
Overlapping source and destination blocks
Memory leak detection
- Still reachable
- Possibly lost, or "dubious"
- Definitely lost, or "leaked"

어머; 언뜻 보기에도 열라 유용하지 않은가요?

자세한건 메뉴얼: http://valgrind.org/docs/manual/manual.html

'아트 앤 싸이언스 > 별난 세상' 카테고리의 다른 글

워드 파일 살려요!  (39) 2007.07.09
cxx에 얽힌 사연  (9) 2007.07.04
Valgrind, 사랑해!  (6) 2007.07.03
63빌딩 프로젝트  (14) 2007.07.02
2007년의 CDP  (14) 2007.06.01
발로 만든 웹  (20) 2007.05.11
TAG c++, 디버깅
1 
분류 전체보기 (657)
느낌 (144)
아트 앤 싸이언스 (451)
표현 (3)
대기권 밖 이야기 (58)