The Lost Dialogue

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

'최적화'에 해당되는 글 1건

  1. 2010.01.21 STL std::set 에 저장된 엘리먼트의 값을 바꿔보자. (16)

한동안 굉장히 속을 썩이는 코드가 있었는데,  별 기대없이 펼친 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 타입을 꺼내고 또 다시 넣는 과정에서 생기는 오버헤드가 진정한 문제였던 것이다.

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

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

1 
분류 전체보기 (657)
느낌 (144)
아트 앤 싸이언스 (451)
표현 (3)
대기권 밖 이야기 (58)