Быстрая конкатенация и скорость контейнеров map

О чем это я?

Доброго времени суток, читатели!
По долгу службы возникла необходимость сделать быстрый кэш в памяти с сохранением его в БД. Во время разработки, соответственно, встает вопрос о выборе стандартных и не очень контейнеров. Можно конечно руководствоваться выбором исходя из сложности применяемых алгоритмов, но я решил проверить все на практике, для чего были написаны парочка тестов. Задача проверки эффективности использования памяти не ставилась. Для проверки всего этого дела использовались STLPort 5.2.1 и собранный с ним boost 1.52.0, компилировалось все на gcc 4.6 под ОС Ubuntu 12.04.2. Задача проверки эффективности использования памяти не ставилась, только скорость.

Конкатенация строк

Для некоторых нужд мне потребовалась конкатенация большого количества строк. Погуглив на тему нашел разные предложения по реализации сей операции, но предложения были без оценки эффективности. Решил проверить следующие способы:
— сбор строк с помощью std::ostringstream;
— с помощью append-метода контейнера std::string;
— с помощью append-метода контейнера std::string с предварительным резервированием памяти;
— с помощью самописного StringBuilder, который складывает строки в std::list и собирает их append-ом с предварительным резервированием памяти.
StringBuilder выглядит следующим образом:

class StringBuilder
{
private:
    typedef std::list< std::string > StrList;

public:
    StringBuilder() : m_nSize( 0 ) {}

    ~StringBuilder() {}

    inline void operator<<( const std::string& s )
    {
        m_List.push_back( s );
        m_nSize += s.size();
    }

    inline const std::string& GetResult()
    {
        if( m_sResult.empty() )
        {
            m_sResult.reserve( m_nSize );

            for( StrList::const_iterator it = m_List.begin(), end = m_List.end(); it != end; ++it )
            {
                m_sResult.append( *it );
            }
        }

        return m_sResult;
    }

private:
    StrList m_List;
    std::string m_sResult;
    size_t m_nSize;
};

Подразумевается, что длина результирующей строки не известна, добавление в лист работает очень быстро и копирование строк идет в «ленивом режиме». Добавляя мы считаем длину результирующей строки. В итоге выделяем под результирующую строку память и складываем все строки в нее.
Тестировалось все это дело вот таким кодом:

int main(int argc, char* argv[])
{
    {
        StringBuilder builder;
        boost::posix_time::ptime time_start( boost::posix_time::microsec_clock::local_time() );

        for( int i = 0; i < 10000000; ++i )
        {
            builder << "adlkjeowihfxnnzdloifhoweisndlxkijnvosifs";
        }

        std::string s = builder.GetResult();
        boost::posix_time::ptime time_end( boost::posix_time::microsec_clock::local_time() );
        boost::posix_time::time_duration duration( time_end - time_start );

        TRACE( "Concatenation using StringBuilder duration: " << duration.total_microseconds() );
        s.clear();
    }

    {
        std::ostringstream stream;
        boost::posix_time::ptime time_start( boost::posix_time::microsec_clock::local_time() );

        for( int i = 0; i < 10000000; ++i )
        {
            stream << "adlkjeowihfxnnzdloifhoweisndlxkijnvosifs";
        }

        std::string s = stream.str();
        boost::posix_time::ptime time_end( boost::posix_time::microsec_clock::local_time() );
        boost::posix_time::time_duration duration( time_end - time_start );

        TRACE( "Concatenation using ostringstream duration: " << duration.total_microseconds() );
        s.clear();
    }

    size_t nSize;

    {
        std::string s;
        boost::posix_time::ptime time_start( boost::posix_time::microsec_clock::local_time() );

        for( int i = 0; i < 10000000; ++i )
        {
            s.append( "adlkjeowihfxnnzdloifhoweisndlxkijnvosifs" );
        }

        boost::posix_time::ptime time_end( boost::posix_time::microsec_clock::local_time() );
        boost::posix_time::time_duration duration( time_end - time_start );

        TRACE( "Concatenation using string append duration: " << duration.total_microseconds() );
        nSize = s.size();
        s.clear();
    }

    {
        std::string s;
        s.reserve( nSize );
        boost::posix_time::ptime time_start( boost::posix_time::microsec_clock::local_time() );

        for( int i = 0; i < 10000000; ++i )
        {
            s.append( "adlkjeowihfxnnzdloifhoweisndlxkijnvosifs" );
        }

        boost::posix_time::ptime time_end( boost::posix_time::microsec_clock::local_time() );
        boost::posix_time::time_duration duration( time_end - time_start );

        TRACE( "Concatenation using string append with reserve duration: " << duration.total_microseconds() );
        s.clear();
    }

    return 0;
}

Результаты получились следующие:

Concatenation using StringBuilder duration: 1395687
Concatenation using ostringstream duration: 1080554
Concatenation using string append duration: 413750
Concatenation using string append with reserve duration: 197131

В итоге получаем, что ничего изобретать не надо, быстрее всего работает самый обычный append, при этом, по возможности, следует резервировать память под результат.

Проверяем map

Проверке подверглись boost::unordered_map, std::hash_map и std::map.
Проверка заключалась в следующем, массивы заполнялись парами, ключом в которых были случайные строки по 40 байт длиной, а значением был 0. Всего элементов в массиве — 100 миллионов. Тестировалось все тысячей выборок 100 случайных строк, которые заведомо имелись в массиве.

std::string GetRandomSHA1();

int main(int argc, char* argv[])
{
    {
        typedef boost::unordered_map< std::string, int > Str2IntMap;
        Str2IntMap test_map;
        typedef std::list< std::string > HashList;
        HashList hash_list;

        for( int i = 0; i < 100000000; ++i )
        {
            std::string sSHA1 = GetRandomSHA1();
            test_map[ sSHA1 ] = 0;

            if( i < 100 )
            {
                hash_list.push_back( sSHA1 );
            }
        }

        boost::posix_time::ptime time_start( boost::posix_time::microsec_clock::local_time() );

        for( int i = 0; i < 1000; ++i )
        {
            for( HashList::const_iterator it = hash_list.begin(), end = hash_list.end(); it != end; ++it )
            {
                int n = test_map[ *it ];
                n = 0;
            }
        }

        boost::posix_time::ptime time_end( boost::posix_time::microsec_clock::local_time() );
        boost::posix_time::time_duration duration( time_end - time_start );

        TRACE( "unordered_map summary find element duration: " << duration.total_microseconds() );
    }

    {
        typedef std::hash_map< std::string, int > Str2IntMap;
        Str2IntMap test_map;
        typedef std::list< std::string > HashList;
        HashList hash_list;

        for( int i = 0; i < 100000000; ++i )
        {
            std::string sSHA1 = GetRandomSHA1();
            test_map[ sSHA1 ] = 0;

            if( i < 100 )
            {
                hash_list.push_back( sSHA1 );
            }
        }

        boost::posix_time::ptime time_start( boost::posix_time::microsec_clock::local_time() );

        for( int i = 0; i < 1000; ++i )
        {
            for( HashList::const_iterator it = hash_list.begin(), end = hash_list.end(); it != end; ++it )
            {
                int n = test_map[ *it ];
                n = 0;
            }
        }

        boost::posix_time::ptime time_end( boost::posix_time::microsec_clock::local_time() );
        boost::posix_time::time_duration duration( time_end - time_start );

        TRACE( "std::hash_map summary find element duration: " << duration.total_microseconds() );
    }

    {
        typedef std::map< std::string, int > Str2IntMap;
        Str2IntMap test_map;
        typedef std::list< std::string > HashList;
        HashList hash_list;

        for( int i = 0; i < 100000000; ++i )
        {
            std::string sSHA1 = GetRandomSHA1();
            test_map[ sSHA1 ] = 0;

            if( i < 100 )
            {
                hash_list.push_back( sSHA1 );
            }
        }

        boost::posix_time::ptime time_start( boost::posix_time::microsec_clock::local_time() );

        for( int i = 0; i < 1000; ++i )
        {
            for( HashList::const_iterator it = hash_list.begin(), end = hash_list.end(); it != end; ++it )
            {
                int n = test_map[ *it ];
                n = 0;
            }
        }

        boost::posix_time::ptime time_end( boost::posix_time::microsec_clock::local_time() );
        boost::posix_time::time_duration duration( time_end - time_start );

        TRACE( "std::map summary find element duration: " << duration.total_microseconds() );
    }

    return 0;
}

std::string GetRandomSHA1()
{
    char szSha1[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
    char* szSha1Tmp = szSha1;
    std::srand( std::time( 0 ) );

    for( size_t i = 0; i < 20; ++i )
    {
        unsigned int c = std::rand() % 255;
        sprintf( szSha1Tmp, "%02X", c );
        szSha1Tmp += 2;
    }

    return szSha1;
}

Вот тут начались сюрпризы.

unordered_map summary find element duration: 8154
std::hash_map summary find element duration: 3494
std::map summary find element duration: 6072

Оказалось, что boost::unordered_map всегда медленнее чем std::map. Не знаю, с чем это связано, не разбирался, но факт остается фактом.
А вот std::hash_map как раз показал ожидаемые результаты, он почти в два раза оказался быстрее std::map. Тестирование привело к тому, что я сквозной заменой во всем моем коде заменил boost::unordred_map на std::hash_map. Вот такие дела.

Автор: alex_shabalin

Источник