STL 을 믿지 마세요. – std::string 의 find()

보통 C++ 프로그래머들이 코드를 작성할 때 STL 에 대한 믿음은 꽤나 크다. 나 역시 STL 은 범용적으로 사용 가능하도록 잘 최적화되어 있고 웬만한 프로그래머가 직접 짜는 것보다는 훨씬 잘 짜여져있다고 믿는 편이다. 대부분의 경우 이런 우리의 생각은 옳고, 우리가 쉽게 생각하기 어려운 부분들까지 고려하여 잘 구현되어 있다.

하지만 가끔은 우리가 STL 을 지나치게 만능으로 생각하고 있었다는 것이 증명되기도 한다. 특히 표준에 complexity 가 정확히 명시되어 있지 않은 부분들은 컴파일러에 따라 상당히 비효율적으로 구현된 경우도 있다.

이번에 심심해서 grep-like 한 툴을 짜고 있는데 그 중 생각없이 std::string 의 find() 멤버 함수를 썼다가 알게된 점들에 대해서 포스팅을 한다.

우선 SGI 의 STL 레퍼런스를 참조해보자.

basic_string

size_type find(const basic_string& s, size_type pos = 0) const

Searches for s as a substring of *this, beginning at character pos of *this.

흐음 … 이제 뭔가 입질 감이 오지 않는가? 이렇게 구현에 대해 입 한번 뻥긋하지 않을 정도면 보통 두가지 결론이 나올 수 있다. 첫째는 우리가 생각할 필요없이 잘 구현되어 있다. 걱정하지 말고 사용해라. 라는 경우와 둘째는 표준에서 딱히 정해진게 없으니 구현에 따라 다를 수 있다. 라는 경우이다.

그런데 보통 STL 사용자들은 std::string 의 find() 멤버 함수면 적어도 스트링에 최적화된 서치 알고리즘이 구현되어 있으리라 예상한다. 하지만 과연 그럴까? 아래 코드를 한번 보자.

이 코드는 GCC 의 find() 함수 구현이다.

- basic_string.tcc

template<typename _CharT, typename _Traits, typename _Alloc>
typename basic_string<_CharT, _Traits, _Alloc>::size_type
basic_string<_CharT, _Traits, _Alloc>::
find(const _CharT* __s, size_type __pos, size_type __n) const
{
  __glibcxx_requires_string_len(__s, __n);
  size_type __ret = npos;
  const size_type __size = this->size();
  if (__pos + __n <= __size)
  {
    const _CharT* __data = _M_data();
    const _CharT* __p = std::search(__data + __pos, __data + __size, __s, __s + __n, traits_type::eq);
    if (__p != __data + __size || __n == 0)
      __ret = __p - __data;
  }
  return __ret;
}

이 코드를 읽다가 아마 대부분 std::search( … ) 부분에서 다들 시선이 멈췄을 것이다. 사실 이 함수는 std::search() 함수 호출 외에는 특별히 다른 일을 하지 않는다. 그러면 우리 기억 속의 std::search() 함수는 어떤 complexity 를 가지고 있던가? 잘 생각해보고 그래도 설마하며 SGI 의 레퍼런스를 다시 뒤져본다.

Complexity

Worst case behavior is quadratic: at most (last1 – first1) * (last2 – first2) comparisons. This worst case, however, is rare. Average complexity is linear.

그렇다. 우리가 생각했던 naive search 가 맞다. 즉, 텍스트와 패턴을 하나 하나 처음부터 비교하다가 틀리면 한칸 앞으로 쉬프트해서 다시 비교 … 따라서 컴플렉시티는 O(m * n) 이다. 워스트 케이스의 경우 input 인 m 과 n 의 크기가 각각 2배씩 증가하면 시간은 4배가 증가하는 quadratic 그래프를 그리는 알고리즘이다.

여기까지 읽고도 “설마 … 뭔가 다른게 있겠지.” 하는 분들을 위해 (나도 그랬다.) 직접 테스트를 돌려보았다.

테스트 입력은 naive search 의 경우 워스트 케이스인 m = a+b 에 n = a+b 다.

아주 모범적인 quadratic 그래프가 아닌가? 입력이 커짐에 따라 내가 STL 을 사용해서 작성한[..] Boyer-Moore 구현이 리니어하게 증가함과 달리 std::string::find() 함수는 무지막지하게 느려졌다. 사실 이 포스트를 작성하면서 다른 STL 구현들에 대해서도 검색해봤는데 딱히 naive search 가 아니라는 증거는 찾지 못했다. 코드를 보거나 테스트를 해본 것은 아니라서 확신할 수 는 없지만 아마 비슷하지 않을까 생각한다.

가끔 C++ 프로그래머들은 STL 이나 각종 라이브러리 (Boost, et cetera) 에 대한 지나친 믿음을 가질 수 있다. 내가 여기서 말하고 싶은 것은 라이브러리는 유용한 툴은 될지언정 그런 믿음의 대상은 될 수 없다는 것이다. 그러니 STL 이 가끔씩 당신의 뒤통수를 치더라도 노여워하거나 슬퍼할 것은 전혀 없다.

std::string::find() 함수는 이런 익스트림한 조건에서도 사용될 수 있지만 수십글자를 넘어가지 않는 스트링에 대해서 자주 사용될 수도 있다. 따라서 이런 범용적인 사용을 모두 염두에 두고 구현되기 때문에 특정 경우에 최적화된 코드는 아니다. 처음 프로그래밍을 시작할 적에는 라이브러리가 마치 신이 작성한듯, 하늘에서 뚝 떨어진 콜라병처럼 만능이고 완벽하게 보이지만 실제로 프로그래밍을 하다보면 라이브러리도 가끔 버그도 나타나는, 다 사람이 작성한 코드의 일부일 뿐이다.

여기서 내가 STL 사용에 대해 부정적인 입장을 가지고 있는 것처럼 보일 수 있지만 사실은 그렇지 않다. 일단 라이브러리를 최대한 사용해서 쉽게 구현하고 나중에 프로파일링을 해서 문제가 되는 부분을 찾아서 고치면 실제로 모든 부분을 다 최적화된 코드를 작성해서 프로그램을 만드는 것보다는 훨씬 빠르고 버그없이 작성할 수 있다. 그 외의 유지 보수와 관련하여 생각해보면 표준 라이브러리를 최대한으로 사용하는 것이 최선이다. 다만 내가 아까 말했듯이 이렇게 자주 사용하다보면 믿음에 빠질 수 있는데 이런 턱없는 믿음만 경계한다면 라이브러리와 함께 행복한(?) 프로그래밍 생활을 보낼 수 있을 것이다.

(… 물론 나는 텍스트와 패턴의 크기를 보고 어느 정도는 동적으로 적당한 알고리즘을 선택해주길 바랐지만 그렇게 하자면 사실 STL 구현은 지금도 끝나지 않았을 수 있다[..])

주1. STLPort 와 MS Visual C++ 의 STL 구현에 대해서도 피드백을 받습니다. (트랙백, 리플 다 환영합니다~)

관련된 포스트들

• 홀짝도 구분 못하는 STL (5)
• STL 사용과 코드의 복잡성 및 가독성에 대한 소고 (4)
• 모든 상위 클래스의 소멸자는 가상이어야 하는가? (2)
• C++ Labyrinth #1 (4)
• 스도쿠 규칙 검사의 하스켈 구현 (0)