Allocators Performance on STL Collections

Summary

In this article we'll talk about allocators performance on STL collections. We take performance comparison of:

Performance Comparison

Test Environment:

  • CPU: Intel(R) Pentium(R) D CPU 3.40GHz (2 CPUs)
  • Memory: 2G
  • OS: Ubuntu 4.1.2-0ubuntu4, Linux version 2.6.20-15-generic
  • Compiler: g++ (GCC) 4.1.3 20070929 (prerelease) (Ubuntu 4.1.2-16ubuntu2)

Test cases:

When testing performance of a value container (eg. deque, list, set, hash_set, etc), we insert 1000,000 integer into the container. Pseudo test code looks like this:

Container<int> s;
for (int i = 0; i < 1000000; ++i)
    s.insert(i);

When testing performance of a key-value pair container (eg. map, hash_map, etc), we insert 1000,000 integer-integer pair into the container. Pseudo test code looks like this:

Container<int, int> s;
for (int i = 0; i < 1000000; ++i)
    s.insert(Container<int, int>::value_type(i, i));

Test Result:

deque list set hash_set map hash_map
ScopeAlloc 5.71 ms 20.32 ms 198.44 ms 129.68 ms 225.12 ms 130.80 ms
STL 8.34 ms 66.56 ms 504.81 ms 232.63 ms 505.34 ms 242.21 ms
STLContainers.png

Performance of STL Containers based on ScopeAlloc is faster than the given data here in fact (because BlockPool is empty at the beginning of these test cases).

Source code (download from here):

template <class LogT>
class TestSTLContainersPerformance : public TestCase
{
    WINX_TEST_SUITE(TestSTLContainersPerformance);
        WINX_TEST(testComparison);
    WINX_TEST_SUITE_END();
 
private:
    std::Accumulator m_acc;
 
public:
    enum { Count = 1000000 };
    enum { TestN = 16 };
 
    void doDeque(LogT& log)
    {
        std::BlockPool recycle;
 
        log.print("\n===== Deque (ScopeAlloc) =====\n");
        m_acc.start();
        for (int j = 0; j < TestN; ++j)
        {
            std::PerformanceCounter counter;
            {
                std::ScopeAlloc alloc(recycle);
                std::Deque<int> s(alloc);
                for (int i = 0; i < Count; ++i)
                    s.push_back(i);
            }
            m_acc.accumulate(counter.trace(log));
        }
        m_acc.trace_avg(log);
    }
 
    void doStlDeque(LogT& log)
    {
        log.print("\n===== std::deque =====\n");
        m_acc.start();
        for (int j = 0; j < TestN; ++j)
        {
            std::PerformanceCounter counter;
            {
                std::deque<int> s;
                for (int i = 0; i < Count; ++i)
                    s.push_back(i);
            }
            m_acc.accumulate(counter.trace(log));
        }
        m_acc.trace_avg(log);
    }
 
    void doList(LogT& log)
    {
        std::BlockPool recycle;
 
        log.print("\n===== List (ScopeAlloc) =====\n");
        m_acc.start();
        for (int j = 0; j < TestN; ++j)
        {
            std::PerformanceCounter counter;
            {
                std::ScopeAlloc alloc(recycle);
                std::List<int> s(alloc);
                for (int i = 0; i < Count; ++i)
                    s.push_back(i);
            }
            m_acc.accumulate(counter.trace(log));
        }
        m_acc.trace_avg(log);
    }
 
    void doStlList(LogT& log)
    {
        log.print("\n===== std::list =====\n");
        m_acc.start();
        for (int j = 0; j < TestN; ++j)
        {
            std::PerformanceCounter counter;
            {
                std::list<int> s;
                for (int i = 0; i < Count; ++i)
                    s.push_back(i);
            }
            m_acc.accumulate(counter.trace(log));
        }
        m_acc.trace_avg(log);
    }
 
    void doSet(LogT& log)
    {
        std::BlockPool recycle;
 
        log.print("\n===== Set (ScopeAlloc) =====\n");
        m_acc.start();
        for (int j = 0; j < TestN; ++j)
        {
            std::PerformanceCounter counter;
            {
                std::ScopeAlloc alloc(recycle);
                std::Set<int> s(alloc);
                for (int i = 0; i < Count; ++i)
                    s.insert(i);
            }
            m_acc.accumulate(counter.trace(log));
        }
        m_acc.trace_avg(log);
    }
 
    void doStlSet(LogT& log)
    {
        log.print("\n===== std::set =====\n");
        m_acc.start();
        for (int j = 0; j < TestN; ++j)
        {
            std::PerformanceCounter counter;
            {
                std::set<int> s;
                for (int i = 0; i < Count; ++i)
                    s.insert(i);
            }
            m_acc.accumulate(counter.trace(log));
        }
        m_acc.trace_avg(log);
    }
 
    void doMap(LogT& log)
    {
        std::BlockPool recycle;
 
        log.print("\n===== Map (ScopeAlloc) =====\n");
        m_acc.start();
        for (int j = 0; j < TestN; ++j)
        {
            std::PerformanceCounter counter;
            {
                std::ScopeAlloc alloc(recycle);
                std::Map<int, int> s(alloc);
                for (int i = 0; i < Count; ++i)
                    s.insert(std::Map<int, int>::value_type(i, i));
            }
            m_acc.accumulate(counter.trace(log));
        }
        m_acc.trace_avg(log);
    }
 
    void doStlMap(LogT& log)
    {
        log.print("\n===== std::map =====\n");
        m_acc.start();
        for (int j = 0; j < TestN; ++j)
        {
            std::PerformanceCounter counter;
            {
                std::map<int, int> s;
                for (int i = 0; i < Count; ++i)
                    s.insert(std::map<int, int>::value_type(i, i));
            }
            m_acc.accumulate(counter.trace(log));
        }
        m_acc.trace_avg(log);
    }
 
    void doHashSet(LogT& log)
    {
        std::BlockPool recycle;
 
        log.print("\n===== HashSet (ScopeAlloc) =====\n");
        m_acc.start();
        for (int j = 0; j < TestN; ++j)
        {
            std::PerformanceCounter counter;
            {
                std::ScopeAlloc alloc(recycle);
                std::HashSet<int> s(alloc);
                for (int i = 0; i < Count; ++i)
                    s.insert(i);
            }
            m_acc.accumulate(counter.trace(log));
        }
        m_acc.trace_avg(log);
    }
 
    void doStlHashSet(LogT& log)
    {
        log.print("\n===== stdext::hash_set =====\n");
        m_acc.start();
        for (int j = 0; j < TestN; ++j)
        {
            std::PerformanceCounter counter;
            {
                stdext::hash_set<int> s;
                for (int i = 0; i < Count; ++i)
                    s.insert(i);
            }
            m_acc.accumulate(counter.trace(log));
        }
        m_acc.trace_avg(log);
    }
 
    void doHashMap(LogT& log)
    {
        std::BlockPool recycle;
 
        log.print("\n===== HashMap (ScopeAlloc) =====\n");
        m_acc.start();
        for (int j = 0; j < TestN; ++j)
        {
            std::PerformanceCounter counter;
            {
                std::ScopeAlloc alloc(recycle);
                std::HashMap<int, int> s(alloc);
                for (int i = 0; i < Count; ++i)
                    s.insert(std::HashMap<int, int>::value_type(i, i));
            }
            m_acc.accumulate(counter.trace(log));
        }
        m_acc.trace_avg(log);
    }
 
    void doStlHashMap(LogT& log)
    {
        log.print("\n===== stdext::hash_map =====\n");
        m_acc.start();
        for (int j = 0; j < TestN; ++j)
        {
            std::PerformanceCounter counter;
            {
                stdext::hash_map<int, int> s;
                for (int i = 0; i < Count; ++i)
                    s.insert(stdext::hash_map<int, int>::value_type(i, i));
            }
            m_acc.accumulate(counter.trace(log));
        }
        m_acc.trace_avg(log);
    }
 
    void testComparison(LogT& log)
    {
        doDeque(log);
        doStlDeque(log);
        doList(log);
        doStlList(log);
        doSet(log);
        doStlSet(log);
        doHashSet(log);
        doStlHashSet(log);
        doMap(log);
        doStlMap(log);
        doHashMap(log);
        doStlHashMap(log);
    }
};

Output:

===== Deque (ScopeAlloc) =====
---> Elapse 8126000 ticks (8.13 ms) (0.00 min) ...
---> Elapse 5533000 ticks (5.53 ms) (0.00 min) ...
---> Elapse 5541000 ticks (5.54 ms) (0.00 min) ...
---> Elapse 5551000 ticks (5.55 ms) (0.00 min) ...
---> Elapse 5536000 ticks (5.54 ms) (0.00 min) ...
---> Elapse 5541000 ticks (5.54 ms) (0.00 min) ...
---> Elapse 5543000 ticks (5.54 ms) (0.00 min) ...
---> Elapse 5551000 ticks (5.55 ms) (0.00 min) ...
---> Elapse 5543000 ticks (5.54 ms) (0.00 min) ...
---> Elapse 5552000 ticks (5.55 ms) (0.00 min) ...
---> Elapse 5545000 ticks (5.54 ms) (0.00 min) ...
---> Elapse 5547000 ticks (5.55 ms) (0.00 min) ...
---> Elapse 5553000 ticks (5.55 ms) (0.00 min) ...
---> Elapse 5549000 ticks (5.55 ms) (0.00 min) ...
---> Elapse 5559000 ticks (5.56 ms) (0.00 min) ...
---> Elapse 5570000 ticks (5.57 ms) (0.00 min) ...
Average: ---> Elapse 5708750 ticks (5.71 ms) (0.00 min) ...

===== std::deque =====
---> Elapse 8547000 ticks (8.55 ms) (0.00 min) ...
---> Elapse 8320000 ticks (8.32 ms) (0.00 min) ...
---> Elapse 8305000 ticks (8.30 ms) (0.00 min) ...
---> Elapse 8309000 ticks (8.31 ms) (0.00 min) ...
---> Elapse 8315000 ticks (8.31 ms) (0.00 min) ...
---> Elapse 8333000 ticks (8.33 ms) (0.00 min) ...
---> Elapse 8326000 ticks (8.33 ms) (0.00 min) ...
---> Elapse 8398000 ticks (8.40 ms) (0.00 min) ...
---> Elapse 8313000 ticks (8.31 ms) (0.00 min) ...
---> Elapse 8331000 ticks (8.33 ms) (0.00 min) ...
---> Elapse 8310000 ticks (8.31 ms) (0.00 min) ...
---> Elapse 8312000 ticks (8.31 ms) (0.00 min) ...
---> Elapse 8312000 ticks (8.31 ms) (0.00 min) ...
---> Elapse 8312000 ticks (8.31 ms) (0.00 min) ...
---> Elapse 8311000 ticks (8.31 ms) (0.00 min) ...
---> Elapse 8312000 ticks (8.31 ms) (0.00 min) ...
Average: ---> Elapse 8335375 ticks (8.34 ms) (0.00 min) ...

===== List (ScopeAlloc) =====
---> Elapse 35887000 ticks (35.89 ms) (0.00 min) ...
---> Elapse 18586000 ticks (18.59 ms) (0.00 min) ...
---> Elapse 19608000 ticks (19.61 ms) (0.00 min) ...
---> Elapse 20141000 ticks (20.14 ms) (0.00 min) ...
---> Elapse 18991000 ticks (18.99 ms) (0.00 min) ...
---> Elapse 18893000 ticks (18.89 ms) (0.00 min) ...
---> Elapse 19329000 ticks (19.33 ms) (0.00 min) ...
---> Elapse 18944000 ticks (18.94 ms) (0.00 min) ...
---> Elapse 20132000 ticks (20.13 ms) (0.00 min) ...
---> Elapse 18856000 ticks (18.86 ms) (0.00 min) ...
---> Elapse 18653000 ticks (18.65 ms) (0.00 min) ...
---> Elapse 18758000 ticks (18.76 ms) (0.00 min) ...
---> Elapse 20491000 ticks (20.49 ms) (0.00 min) ...
---> Elapse 19033000 ticks (19.03 ms) (0.00 min) ...
---> Elapse 19611000 ticks (19.61 ms) (0.00 min) ...
---> Elapse 19207000 ticks (19.21 ms) (0.00 min) ...
Average: ---> Elapse 20320000 ticks (20.32 ms) (0.00 min) ...

===== std::list =====
---> Elapse 109242000 ticks (109.24 ms) (0.00 min) ...
---> Elapse 65746000 ticks (65.75 ms) (0.00 min) ...
---> Elapse 61358000 ticks (61.36 ms) (0.00 min) ...
---> Elapse 64262000 ticks (64.26 ms) (0.00 min) ...
---> Elapse 59243000 ticks (59.24 ms) (0.00 min) ...
---> Elapse 63945000 ticks (63.95 ms) (0.00 min) ...
---> Elapse 60470000 ticks (60.47 ms) (0.00 min) ...
---> Elapse 65006000 ticks (65.01 ms) (0.00 min) ...
---> Elapse 61946000 ticks (61.95 ms) (0.00 min) ...
---> Elapse 63794000 ticks (63.79 ms) (0.00 min) ...
---> Elapse 61271000 ticks (61.27 ms) (0.00 min) ...
---> Elapse 67989000 ticks (67.99 ms) (0.00 min) ...
---> Elapse 61531000 ticks (61.53 ms) (0.00 min) ...
---> Elapse 67216000 ticks (67.22 ms) (0.00 min) ...
---> Elapse 62308000 ticks (62.31 ms) (0.00 min) ...
---> Elapse 69648000 ticks (69.65 ms) (0.00 min) ...
Average: ---> Elapse 66560937 ticks (66.56 ms) (0.00 min) ...

===== Set (ScopeAlloc) =====
---> Elapse 230359000 ticks (230.36 ms) (0.00 min) ...
---> Elapse 197193000 ticks (197.19 ms) (0.00 min) ...
---> Elapse 194803000 ticks (194.80 ms) (0.00 min) ...
---> Elapse 195222000 ticks (195.22 ms) (0.00 min) ...
---> Elapse 195897000 ticks (195.90 ms) (0.00 min) ...
---> Elapse 197511000 ticks (197.51 ms) (0.00 min) ...
---> Elapse 196196000 ticks (196.20 ms) (0.00 min) ...
---> Elapse 195394000 ticks (195.39 ms) (0.00 min) ...
---> Elapse 195777000 ticks (195.78 ms) (0.00 min) ...
---> Elapse 195353000 ticks (195.35 ms) (0.00 min) ...
---> Elapse 195871000 ticks (195.87 ms) (0.00 min) ...
---> Elapse 195364000 ticks (195.36 ms) (0.00 min) ...
---> Elapse 195064000 ticks (195.06 ms) (0.00 min) ...
---> Elapse 199112000 ticks (199.11 ms) (0.00 min) ...
---> Elapse 199384000 ticks (199.38 ms) (0.00 min) ...
---> Elapse 196605000 ticks (196.60 ms) (0.00 min) ...
Average: ---> Elapse 198444062 ticks (198.44 ms) (0.00 min) ...

===== std::set =====
---> Elapse 556947000 ticks (556.95 ms) (0.01 min) ...
---> Elapse 497091000 ticks (497.09 ms) (0.01 min) ...
---> Elapse 497079000 ticks (497.08 ms) (0.01 min) ...
---> Elapse 498965000 ticks (498.96 ms) (0.01 min) ...
---> Elapse 494998000 ticks (495.00 ms) (0.01 min) ...
---> Elapse 495250000 ticks (495.25 ms) (0.01 min) ...
---> Elapse 491596000 ticks (491.60 ms) (0.01 min) ...
---> Elapse 501581000 ticks (501.58 ms) (0.01 min) ...
---> Elapse 497751000 ticks (497.75 ms) (0.01 min) ...
---> Elapse 520702000 ticks (520.70 ms) (0.01 min) ...
---> Elapse 492612000 ticks (492.61 ms) (0.01 min) ...
---> Elapse 493891000 ticks (493.89 ms) (0.01 min) ...
---> Elapse 496398000 ticks (496.40 ms) (0.01 min) ...
---> Elapse 502701000 ticks (502.70 ms) (0.01 min) ...
---> Elapse 495359000 ticks (495.36 ms) (0.01 min) ...
---> Elapse 544092000 ticks (544.09 ms) (0.01 min) ...
Average: ---> Elapse 504813312 ticks (504.81 ms) (0.01 min) ...

===== HashSet (ScopeAlloc) =====
---> Elapse 150568000 ticks (150.57 ms) (0.00 min) ...
---> Elapse 124236000 ticks (124.24 ms) (0.00 min) ...
---> Elapse 127112000 ticks (127.11 ms) (0.00 min) ...
---> Elapse 127240000 ticks (127.24 ms) (0.00 min) ...
---> Elapse 129835000 ticks (129.84 ms) (0.00 min) ...
---> Elapse 126990000 ticks (126.99 ms) (0.00 min) ...
---> Elapse 126621000 ticks (126.62 ms) (0.00 min) ...
---> Elapse 127549000 ticks (127.55 ms) (0.00 min) ...
---> Elapse 126948000 ticks (126.95 ms) (0.00 min) ...
---> Elapse 127519000 ticks (127.52 ms) (0.00 min) ...
---> Elapse 126703000 ticks (126.70 ms) (0.00 min) ...
---> Elapse 127068000 ticks (127.07 ms) (0.00 min) ...
---> Elapse 145131000 ticks (145.13 ms) (0.00 min) ...
---> Elapse 127001000 ticks (127.00 ms) (0.00 min) ...
---> Elapse 127132000 ticks (127.13 ms) (0.00 min) ...
---> Elapse 127182000 ticks (127.18 ms) (0.00 min) ...
Average: ---> Elapse 129677187 ticks (129.68 ms) (0.00 min) ...

===== stdext::hash_set =====
---> Elapse 228141000 ticks (228.14 ms) (0.00 min) ...
---> Elapse 230162000 ticks (230.16 ms) (0.00 min) ...
---> Elapse 233248000 ticks (233.25 ms) (0.00 min) ...
---> Elapse 234439000 ticks (234.44 ms) (0.00 min) ...
---> Elapse 230686000 ticks (230.69 ms) (0.00 min) ...
---> Elapse 231472000 ticks (231.47 ms) (0.00 min) ...
---> Elapse 236312000 ticks (236.31 ms) (0.00 min) ...
---> Elapse 232374000 ticks (232.37 ms) (0.00 min) ...
---> Elapse 229600000 ticks (229.60 ms) (0.00 min) ...
---> Elapse 231822000 ticks (231.82 ms) (0.00 min) ...
---> Elapse 233218000 ticks (233.22 ms) (0.00 min) ...
---> Elapse 236823000 ticks (236.82 ms) (0.00 min) ...
---> Elapse 232509000 ticks (232.51 ms) (0.00 min) ...
---> Elapse 231615000 ticks (231.62 ms) (0.00 min) ...
---> Elapse 231503000 ticks (231.50 ms) (0.00 min) ...
---> Elapse 238118000 ticks (238.12 ms) (0.00 min) ...
Average: ---> Elapse 232627625 ticks (232.63 ms) (0.00 min) ...

===== Map (ScopeAlloc) =====
---> Elapse 257778000 ticks (257.78 ms) (0.00 min) ...
---> Elapse 223163000 ticks (223.16 ms) (0.00 min) ...
---> Elapse 223218000 ticks (223.22 ms) (0.00 min) ...
---> Elapse 222969000 ticks (222.97 ms) (0.00 min) ...
---> Elapse 223063000 ticks (223.06 ms) (0.00 min) ...
---> Elapse 222795000 ticks (222.79 ms) (0.00 min) ...
---> Elapse 222646000 ticks (222.65 ms) (0.00 min) ...
---> Elapse 222203000 ticks (222.20 ms) (0.00 min) ...
---> Elapse 222331000 ticks (222.33 ms) (0.00 min) ...
---> Elapse 223463000 ticks (223.46 ms) (0.00 min) ...
---> Elapse 222514000 ticks (222.51 ms) (0.00 min) ...
---> Elapse 223578000 ticks (223.58 ms) (0.00 min) ...
---> Elapse 223207000 ticks (223.21 ms) (0.00 min) ...
---> Elapse 222589000 ticks (222.59 ms) (0.00 min) ...
---> Elapse 222669000 ticks (222.67 ms) (0.00 min) ...
---> Elapse 223761000 ticks (223.76 ms) (0.00 min) ...
Average: ---> Elapse 225121687 ticks (225.12 ms) (0.00 min) ...

===== std::map =====
---> Elapse 553438000 ticks (553.44 ms) (0.01 min) ...
---> Elapse 500515000 ticks (500.51 ms) (0.01 min) ...
---> Elapse 504050000 ticks (504.05 ms) (0.01 min) ...
---> Elapse 497704000 ticks (497.70 ms) (0.01 min) ...
---> Elapse 511301000 ticks (511.30 ms) (0.01 min) ...
---> Elapse 498399000 ticks (498.40 ms) (0.01 min) ...
---> Elapse 514708000 ticks (514.71 ms) (0.01 min) ...
---> Elapse 494241000 ticks (494.24 ms) (0.01 min) ...
---> Elapse 504770000 ticks (504.77 ms) (0.01 min) ...
---> Elapse 499898000 ticks (499.90 ms) (0.01 min) ...
---> Elapse 498683000 ticks (498.68 ms) (0.01 min) ...
---> Elapse 499024000 ticks (499.02 ms) (0.01 min) ...
---> Elapse 513798000 ticks (513.80 ms) (0.01 min) ...
---> Elapse 500845000 ticks (500.85 ms) (0.01 min) ...
---> Elapse 496447000 ticks (496.45 ms) (0.01 min) ...
---> Elapse 497569000 ticks (497.57 ms) (0.01 min) ...
Average: ---> Elapse 505336875 ticks (505.34 ms) (0.01 min) ...

===== HashMap (ScopeAlloc) =====
---> Elapse 151127000 ticks (151.13 ms) (0.00 min) ...
---> Elapse 126669000 ticks (126.67 ms) (0.00 min) ...
---> Elapse 129396000 ticks (129.40 ms) (0.00 min) ...
---> Elapse 129948000 ticks (129.95 ms) (0.00 min) ...
---> Elapse 129511000 ticks (129.51 ms) (0.00 min) ...
---> Elapse 129670000 ticks (129.67 ms) (0.00 min) ...
---> Elapse 129504000 ticks (129.50 ms) (0.00 min) ...
---> Elapse 129928000 ticks (129.93 ms) (0.00 min) ...
---> Elapse 129603000 ticks (129.60 ms) (0.00 min) ...
---> Elapse 129783000 ticks (129.78 ms) (0.00 min) ...
---> Elapse 129697000 ticks (129.70 ms) (0.00 min) ...
---> Elapse 130063000 ticks (130.06 ms) (0.00 min) ...
---> Elapse 129574000 ticks (129.57 ms) (0.00 min) ...
---> Elapse 129322000 ticks (129.32 ms) (0.00 min) ...
---> Elapse 129325000 ticks (129.32 ms) (0.00 min) ...
---> Elapse 129655000 ticks (129.66 ms) (0.00 min) ...
Average: ---> Elapse 130798437 ticks (130.80 ms) (0.00 min) ...

===== stdext::hash_map =====
---> Elapse 240273000 ticks (240.27 ms) (0.00 min) ...
---> Elapse 238712000 ticks (238.71 ms) (0.00 min) ...
---> Elapse 242619000 ticks (242.62 ms) (0.00 min) ...
---> Elapse 245612000 ticks (245.61 ms) (0.00 min) ...
---> Elapse 248101000 ticks (248.10 ms) (0.00 min) ...
---> Elapse 239930000 ticks (239.93 ms) (0.00 min) ...
---> Elapse 240632000 ticks (240.63 ms) (0.00 min) ...
---> Elapse 245002000 ticks (245.00 ms) (0.00 min) ...
---> Elapse 244293000 ticks (244.29 ms) (0.00 min) ...
---> Elapse 238797000 ticks (238.80 ms) (0.00 min) ...
---> Elapse 239317000 ticks (239.32 ms) (0.00 min) ...
---> Elapse 244015000 ticks (244.01 ms) (0.00 min) ...
---> Elapse 243347000 ticks (243.35 ms) (0.00 min) ...
---> Elapse 242070000 ticks (242.07 ms) (0.00 min) ...
---> Elapse 240476000 ticks (240.48 ms) (0.00 min) ...
---> Elapse 242236000 ticks (242.24 ms) (0.00 min) ...
Average: ---> Elapse 242214500 ticks (242.21 ms) (0.00 min) ...

Conclusion

When we use ScopeAlloc, performance of STL containers has distinct promotion.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License