Rope based on GC Allocator

Introduction

Rope is a complex string implementation with scaled performance. The original rope implementation is appeared SGI STL. I rewrite the rope class based on GC Allocator. Code size is much reduced and performance is better.

Source code

Source code of the original rope implemention:

Rope based on GC Allocator:

I divided rope source code into six parts:

  • RopeRep.h implements the underlying representation of rope data structure.
  • RopeIter.h implements rope's iterators.
  • CharProxy.h implements element reference proxy of rope containers.
  • Rope.h/RopeImpl.h implements the rope class.
  • SequenceBuffer.h implement SequenceBuffer class which enhance rope performance of data insertion.

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)

Source code (download from here):

template <class LogT>
class TestRopePerformance : public TestCase
{
    WINX_TEST_SUITE(TestRopePerformance);
        WINX_TEST(testComparison);
    WINX_TEST_SUITE_END();
 
private:
    std::Accumulator m_acc;
 
public:
    enum { Count = 1000000 };
    enum { TestN = 16 };
 
    void doRope(LogT& log)
    {
        std::BlockPool recycle;
 
        log.print("\n===== Rope (ScopeAlloc) =====\n");
        m_acc.start();
        for (int j = 0; j < TestN; ++j)
        {
            std::PerformanceCounter counter;
            {
                std::ScopeAlloc alloc(recycle);
                std::Rope<char> s(alloc);
                for (int i = 0; i < Count; ++i)
                    s.push_back('a' + (i % 26));
            }
            m_acc.accumulate(counter.trace(log));
        }
        m_acc.trace_avg(log);
    }
 
    void doSgiRope(LogT& log)
    {
        log.print("\n===== rope (GNU C++) =====\n");
        m_acc.start();
        for (int j = 0; j < TestN; ++j)
        {
            std::PerformanceCounter counter;
            {
                stdext::rope<char> s;
                for (int i = 0; i < Count; ++i)
                    s.push_back('a' + (i % 26));
            }
            m_acc.accumulate(counter.trace(log));
        }
        m_acc.trace_avg(log);
    }
 
    void testComparison(LogT& log)
    {
        doRope(log);
        doSgiRope(log);
    }
};

Output:

===== Rope (ScopeAlloc) =====
---> Elapse 218547000 ticks (218.55 ms) (0.00 min) ...
---> Elapse 137644000 ticks (137.64 ms) (0.00 min) ...
---> Elapse 137528000 ticks (137.53 ms) (0.00 min) ...
---> Elapse 138033000 ticks (138.03 ms) (0.00 min) ...
---> Elapse 137502000 ticks (137.50 ms) (0.00 min) ...
---> Elapse 137563000 ticks (137.56 ms) (0.00 min) ...
---> Elapse 137581000 ticks (137.58 ms) (0.00 min) ...
---> Elapse 137566000 ticks (137.57 ms) (0.00 min) ...
---> Elapse 138171000 ticks (138.17 ms) (0.00 min) ...
---> Elapse 137877000 ticks (137.88 ms) (0.00 min) ...
---> Elapse 138233000 ticks (138.23 ms) (0.00 min) ...
---> Elapse 144543000 ticks (144.54 ms) (0.00 min) ...
---> Elapse 137052000 ticks (137.05 ms) (0.00 min) ...
---> Elapse 137262000 ticks (137.26 ms) (0.00 min) ...
---> Elapse 137534000 ticks (137.53 ms) (0.00 min) ...
---> Elapse 137164000 ticks (137.16 ms) (0.00 min) ...
Average: ---> Elapse 143112500 ticks (143.11 ms) (0.00 min) ...

===== rope (GNU C++) =====
---> Elapse 233977000 ticks (233.98 ms) (0.00 min) ...
---> Elapse 250007000 ticks (250.01 ms) (0.00 min) ...
---> Elapse 244236000 ticks (244.24 ms) (0.00 min) ...
---> Elapse 244169000 ticks (244.17 ms) (0.00 min) ...
---> Elapse 245037000 ticks (245.04 ms) (0.00 min) ...
---> Elapse 248907000 ticks (248.91 ms) (0.00 min) ...
---> Elapse 245017000 ticks (245.02 ms) (0.00 min) ...
---> Elapse 244629000 ticks (244.63 ms) (0.00 min) ...
---> Elapse 244008000 ticks (244.01 ms) (0.00 min) ...
---> Elapse 246478000 ticks (246.48 ms) (0.00 min) ...
---> Elapse 245325000 ticks (245.32 ms) (0.00 min) ...
---> Elapse 245033000 ticks (245.03 ms) (0.00 min) ...
---> Elapse 244252000 ticks (244.25 ms) (0.00 min) ...
---> Elapse 269536000 ticks (269.54 ms) (0.00 min) ...
---> Elapse 250466000 ticks (250.47 ms) (0.00 min) ...
---> Elapse 244375000 ticks (244.38 ms) (0.00 min) ...
Average: ---> Elapse 246590750 ticks (246.59 ms) (0.00 min) ...

Conclusion:

The performance of Rope based on GC Allocator (ScopeAlloc) has distinct promotion in contrast with rope of GNU C++.

page revision: 9, last edited: 21 Apr 2008 00:58
Edit Tags Discuss History Files Print Site tools + Options
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License