Tips for Geeks. Part 2

Suppose we need to build a long string out of some number of small constant strings. For example, these could be options, defines, queries, and so on.

As an example, let’s say it looks like this:

void initString(int i, string & str)
{
    str.clear();
    str += "SOME_TEST_DATA";
    if (i % 2)
        str += ",DATA_MOD_02";
    if (i % 3)
        str += ",DATA_MOD_03";
    if (i % 5)
        str += ",DATA_MOD_05";
    if (i % 7)
        str += ",DATA_MOD_07";
    if (i % 11)
        str += ",DATA_MOD_11";
    if (i % 13)
        str += ",DATA_MOD_13";
    if (i % 15)
        str += ",MOD_15_EXTRA_DATA";
    if (i % 16)
        str += ",MOD_16_EXTRA_DATA";
    if (i % 21)
        str += ",MOD_21_EXTRA_DATA";
    if (i % 24)
        str += ",MOD_24_EXTRA_DATA";
    if (i % 25)
        str += ",MOD_25_EXTRA_DATA";
}

We’ll run this operation in a loop, increasing i from 0 to 1000000:

string paramString;
paramString.reserve(1000);
int result = 0;
for(int i=0; i<1000000;i++)
{
    initString(i, paramString);
    result += paramString.size();
}

Let’s also add timing measurements here. I should warn you up front that the results depend heavily on the compiler, the CPU, and the system as a whole. They’re only interesting for comparing different approaches.
Using std::string on an Athlon 4200 with MS VC++ 2008, we get ~600ms of execution time. Is that a lot or a little? As far as I’m concerned, that’s plenty for a million iterations. But this series isn’t called Tips for Geeks for nothing 🙂

What happens when “SOME_TEST_DATA” gets appended to the str variable? If there’s enough room in the buffer, only three things happen: measuring the length of the string being appended, copying the data, and shifting the index in the str variable. We can’t optimize the copy or the index update, but do we really need to measure string lengths in this case (i.e., scan all their characters looking for ‘\0’)? After all, the compiler already knows the length of a constant string at compile time.

Let’s build our own custom_string class for these experiments:

class custom_string
{
 char * m_data;
 int m_allocated;
 int m_size;
public:

 void reserve(int size)
 {
 ...
 }

 custom_string & operator += (const char * str)
 {  
  int size = strlen(str);
  reserve(size);
  memcpy(m_data + m_size, str, size + 1);
  m_size += size;
  return *this;
 }
};

The reserve method checks whether there’s enough room in the buffer and allocates a new one if needed. I’ve omitted the code for that method, as well as the constructor and destructor, so they don’t distract from the main point.

Our test with this class runs in the same ~600ms as with std::string. There are at least two ways to “kick” its performance up.
The first method is very simple, but it might refuse to work under certain additional conditions, compiler flags, and so on. It consists of making the operator’s code more appealing to the inliner. Let’s do this:

 void append(const char * str, int size)
 {
  reserve(size);
  memcpy(m_data + m_size, str, size + 1);
  m_size += size;
 }

 custom_string & operator += (const char * str)
 {  
  append(str, strlen(str));
  return *this;
 }

Even though the code has barely changed visually, its execution time on my machine is now ~100ms. I didn’t look at the generated assembly or dig into the reasons, but the first thing that comes to mind is that operator += gets inlined, its calls get replaced with calls to append, and the string length calculation happens right at compile time. Whether that’s actually what’s going on isn’t really the point, because the stability of this trick is questionable — the optimization could just as easily vanish for Unicode strings, when building for a different OS, and so on, regardless of __forceinline incantations and our best wishes.

A more universal method relies on the fact that a constant string in C++ can be represented as a fixed-length array of characters. This notation is perfectly valid:

 const char something [] = "something";

For this trick we use templates:

 template<int N>
 custom_string & operator += (const char (&str)[N])
 {
  reserve(N - 1);
  memcpy(m_data + m_size, str, N);
  m_size += N - 1;
  return *this;
 }

The compiler will put the length of the character array, including the trailing zero, into the N variable.
A test using this method runs on my machine in about 140ms, which is within the statistical margin of error of the previous method, but it’s guaranteed to work, since it conforms to the C++ standard. The only downside is that a new copy of the concatenation method gets generated for every distinct string length.

Can std::string be “improved” this way? My experiments showed the gain is insignificant, on the order of 50ms on the original test. This trick is better suited to your own string classes, and honestly it’s better not to use at all (much like homegrown classes for primitives in general). Don’t forget that concatenating millions of strings is an extraordinary situation, and when it does happen, it’s rarely that time-critical. Using your own strings — and especially methods with unusual constructs — noticeably hurts code readability, and with it the ability to maintain the code, both for the original author and for anyone else.