2.1 문자열을 키로 쓰는 map, set 성능 향상시키기

문자열(std::string)을 키로 가지는 맵 같은 경우, 문자열 비교 자체에 걸리는 시간 때문에 검색이 느려질 수 있다. 이 경우, 키로 사용하는 문자열이 별로 중요한 내용이 아니라면 아래와 같은 클래스를 사용함으로서 성능을 약간 증가시킬 수 있다. 


////////////////////////////////////////////////////////////////////////////////
/// \class cStringKey
/// \brief STL 컨테이너를 위한 문자열 키
////////////////////////////////////////////////////////////////////////////////

class cStringKey
{
private:
    enum
    {
        BYTE_SIZE = 32,
    };

    char m_Text[BYTE_SIZE]; ///< 문자열


public:
    /// \brief 생성자
    cStringKey()
    {
        memset(m_Text, 0, sizeof(m_Text));
    }

    /// \brief 생성자
    cStringKey(const char* text)
    {
        memset(m_Text, 0, sizeof(m_Text));
        memcpy_s(m_Text, sizeof(m_Text), text, std::min(sizeof(m_Text), strlen(text)));
    }

    /// \brief 생성자
    cStringKey(const std::string& text)
    {
        memset(m_Text, 0, sizeof(m_Text));
        memcpy_s(m_Text, sizeof(m_Text), text.c_str(), std::min(sizeof(m_Text), text.size()));
    }

    /// \brief 복사 생성자
    cStringKey(const cStringKey& rhs)
    {
        memcpy_s(m_Text, sizeof(m_Text), rhs.m_Text, sizeof(m_Text));
    }


public:
    /// \brief 대입 연산자
    inline const cStringKey& operator = (const cStringKey& rhs)
    {
        if (this != &rhs)
            memcpy_s(m_Text, sizeof(m_Text), rhs.m_Text, sizeof(m_Text));

        return *this;
    }

    /// \brief 비교 연산자
    ///
    /// 이 함수는 약간 유의해야 하는데, 속도를 위해 루프를 풀어버렸기 때문이다.
    /// 클래스의 크기가 변경되면, 이 함수도 같이 변경해줘야 한다.
    inline bool operator < (const cStringKey& rhs) const
    {
        const int* buf1 = reinterpret_cast<const int*>(this);
        const int* buf2 = reinterpret_cast<const int*>(&rhs);

        if (*buf1 != *buf2) return *buf1 < *buf2; // 0-3

        ++buf1; ++buf2;
        if (*buf1 != *buf2) return *buf1 < *buf2; // 4-7

        ++buf1; ++buf2;
        if (*buf1 != *buf2) return *buf1 < *buf2; // 8-11

        ++buf1; ++buf2;
        if (*buf1 != *buf2) return *buf1 < *buf2; // 12-15

        ++buf1; ++buf2;
        if (*buf1 != *buf2) return *buf1 < *buf2; // 16-19

        ++buf1; ++buf2;
        if (*buf1 != *buf2) return *buf1 < *buf2; // 20-23

        ++buf1; ++buf2;
        if (*buf1 != *buf2) return *buf1 < *buf2; // 24-27

        ++buf1; ++buf2;
        return *buf1 < *buf2; // 28-31
    }
};


대소문자 구별없이 비교를 할 수 없다는 점이 좀 아쉽다. 어셈블리도 좀 안다면 비교 연산자를 좀 더 깔끔하게 만들 수 있을 텐데. 어쨌든 테스트해보니, 릴리즈 빌드에서 약 25~33% 정도의 성능이 향상되었다. 


typedef std::map<std::string, std::string> OLD_MAP;
typedef std::map<cStringKey, std::string> NEW_MAP;

OLD_MAP oldMap;
NEW_MAP newMap;

for (int i=0; i<1000; ++i)
{
    std::string key = generic::to_string(rand() % 1000, 4);
    std::string value = generic::to_string(rand() % 1000, 4);
    oldMap.insert(OLD_MAP::value_type(key, value));
    newMap.insert(NEW_MAP::value_type(key, value));
}

DWORD begin = 0, oldTime = 0, newTime = 0;
int repetition = 200000;

begin = timeGetTime();
for (int i=0; i<repetition; ++i)
{
    oldMap.find(generic::to_string(rand() % 1000, 4));
}
oldTime = timeGetTime() - begin;

begin = timeGetTime();
for (int i=0; i<repetition; ++i)
{
    newMap.find(generic::to_string(rand() % 1000, 4));
}
newTime = timeGetTime() - begin;

std::cout << "OLD: " << oldTime << std::endl;
std::cout << "NEW: " << newTime << std::endl;

출처 : http://serious-code.net/moin.cgi/CppSnippets