Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Channels ▼
RSS

C/C++

C++ String Performance

Source Code Accompanies This Article. Download It Now.



A New String Class

In creating a new string class, I wanted to be able to:

  • Avoid heap allocation and copying completely; just to set an internal pointer to some C string.
  • Avoid heap allocation for the nonheap variables; just copy the value to the buffer inside the object.

  • Force heap allocation and copying for any string object (as with a std::string implementation, minus reference counting/COW).

Since it supported the last two of these three requirements, I used SString (see Thinking In C++, by Bruce Eckel; Prentice-Hall, 1995, ISBN 0-13-917709-4) as the basis for my new string class. I then implemented the fastest and most important mode, which doesn't do any allocation or copying. It also occurred to me that the string class features should be selectable by programmers who instantiate the string objects, not the string implementation. Consequently, it's up to users of this class (see Listing Three) to instantiate particular string objects in particular modes. The complete implementation of this new CGenStringT<> class (again, Eckel's SString was used as a basis) is in util.h (also available electronically in the source code file listed at the top of this article).

Listing Three

template
class CGenStringT
{
public:
  CGenStringT ( const char *S = "", int bAlloc = 1 ) : m_s(m_buf)
  {
    if ( !bufsize )
 ...
private:
  char *m_s;
   int   m_bAlloc;
  char  m_buf[bufsize+1];
};

The mode of the string being created in Listing Three is set by the combination of two parameters: template parameter bufsize, and constructor parameter bAlloc. CGenStringT is a template with one template parameter, bufsize, that governs the size of the internal buffer. In addition to specifying the size of the internal buffer, this parameter defines the mode of the string in conjunction with a bAlloc constructor's parameter. The possible combinations are:

  • Mode 1: bufsize == 0 && bAlloc == 0. No heap allocation, no copying, just setting the pointer (fastest).
  • Mode 2: bufsize > 0. No heap allocation, copying into the internal buffer (slower).

  • Mode 3: bufsize == 0 && bAlloc == 1. Heap allocation and copying (slowest).

Once you understand the idea, the implementation is straightforward: Constructor, copy constructor, assignment operator, and destructor are doing the right thing for the three different modes (like allocation, copying, deleting), or none of them. For example, the copy constructor in Listing Four is a good example of handling all three modes (only ASCII null-terminated strings are currently supported).

Listing Four

 ...
 ...
  CGenStringT ( const CGenStringT& rv ): m_s(m_buf)
  {
    if ( !bufsize )
    {
      if ( m_bAlloc = rv.m_bAlloc )
      {
        // make on heap
        m_s = new char [ strlen(rv.m_s)+1 ];
        strcpy ( m_s, rv.m_s );
      }
      else
        // just set a pointer
        m_s = rv.m_s;
    }
    else
    {
      // make on stack
      m_buf[bufsize] = 0;
      strncpy ( m_s, rv.m_s, bufsize );
    }
#ifdef MEM_ALLOC_DEBUG
    printf ("CGenString copy constructor called: this=%x allocation=%s"
            " ptr=%x\n", this, (!bufsize && m_bAlloc ) ? "yes":"no", m_s );
#endif
  }
 ...

Right after the CGenStringT class definition there's a bunch of useful typedefs and a define:

typedef CGenStringT<0> CGenString;

typedef CGenStringT<100> CStackString100;

#define FAST_STRING(id,str) CGenString id(str,0);

CGenString is a Mode 3 string (allocation and copying), CStackString100 is a Mode 2 string (copying) with an internal buffer of 100 bytes, and FAST_STRING defines a Mode 1 string variable ID (no alloc, no copying) and sets its value to str.

The "stack" word is being used in comments throughout the CGenStringT implementation and in CStackString100 to denounce Mode 2 strings (with an internal buffer). In general, this term is incorrect, because the internal buffer is on the stack only when the string variable itself is a stack variable. If this variable is created on the heap (using new()), then the buffer is on the heap as well. So, in general, the buffer as a part of the string object is always allocated in the same class of memory as the string object that owns it.

Performance Testing

To gauge performance, I start by testing the slowest mode (forced heap allocation and copying) to see if the removal of reference counting helps. Teststring3.cpp (available electronically) tests one thread, while teststring4.cpp (also available electronically) tests 10 threads. They are the same, respectively, as teststring1.cpp and teststring2.cpp, except that std::string is replaced with CGenString.

Example 3(a) shows the result of running teststring3, and Example 3(b) the results for teststring4. Compared to std::string, this isn't bad at all for the slowest version—it's 45 percent faster with one thread (59 versus 108) and it's more or less 100(!) times faster with 10 threads running (~100 versus ~10000). And since the heap is still being hit, it looks like std::string reference counting hurts big time!

(a)
Thread <1024>: Creating/destroying 100000 strings...
Thread <1024>: total time=59 millisecs, average=0.000590

(b)
Thread <1026>: Creating/destroying 100000 strings...
Thread <9226>: Creating/destroying 100000 strings...
Thread <9226>: total time=60 millisecs, average=0.000600
Thread <4101>: Creating/destroying 100000 strings...
Thread <5126>: Creating/destroying 100000 strings...
Thread <5126>: total time=65 millisecs, average=0.000650
Thread <4101>: total time=125 millisecs, average=0.001250
Thread <6151>: Creating/destroying 100000 strings...
Thread <7176>: Creating/destroying 100000 strings...
Thread <8201>: Creating/destroying 100000 strings...
Thread <10251>: Creating/destroying 100000 strings...
Thread <6151>: total time=130 millisecs, average=0.001300
Thread <1026>: total time=81 millisecs, average=0.000810
Thread <10251>: total time=94 millisecs, average=0.000940
Thread <7176>: total time=166 millisecs, average=0.001660
Thread <8201>: total time=195 millisecs, average=0.001950
Thread <3076>: Creating/destroying 100000 strings...
Thread <3076>: total time=60 millisecs, average=0.000600
Thread <2051>: Creating/destroying 100000 strings...
Thread <2051>: total time=60 millisecs, average=0.000600

Example 3: (a) The results of running teststring3.cpp; (b) results of running teststring4.cpp.

Moving to the faster Mode 2 strings (using automatic string variables so a buffer for every string is on the stack: no heap allocations, just copying), teststring5.cpp and teststring6.cpp (both available electronically) are the same tests as before—but using CStackString100.

Example 4(a) shows the results of running teststring5, while Example 4(b) shows the results of running teststring6. By eliminating the need to allocate on the heap, you get significantly faster performance: for one thread, 23 versus 59 (Mode 3) versus 108 (std::string), and for 10 threads, ~40 versus 100 (Mode 3) versus 10,000 (std::string).

(a)
Thread <1024>: Creating/destroying 100000 strings...
Thread <1024>: total time=23 millisecs, average=0.000230

(b)
Thread <1026>: Creating/destroying 100000 strings...
Thread <1026>: total time=23 millisecs, average=0.000230
Thread <3076>: Creating/destroying 100000 strings...
Thread <4101>: Creating/destroying 100000 strings...
Thread <3076>: total time=35 millisecs, average=0.000350
Thread <5126>: Creating/destroying 100000 strings...
Thread <5126>: total time=23 millisecs, average=0.000230
Thread <4101>: total time=71 millisecs, average=0.000710
Thread <6151>: Creating/destroying 100000 strings...
Thread <6151>: total time=24 millisecs, average=0.000240
Thread <7176>: Creating/destroying 100000 strings...
Thread <8201>: Creating/destroying 100000 strings...
Thread <9226>: Creating/destroying 100000 strings...
Thread <9226>: total time=23 millisecs, average=0.000230
Thread <10251>: Creating/destroying 100000 strings...
Thread <10251>: total time=23 millisecs, average=0.000230
Thread <7176>: total time=80 millisecs, average=0.000800
Thread <8201>: total time=80 millisecs, average=0.000800
Thread <2051>: Creating/destroying 100000 strings...
Thread <2051>: total time=23 millisecs, average=0.000230

Example 4: (a) The results of running teststring5.cpp; (b) results of teststring6.cpp.


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.