How efficient is std::string compared to null-term

Question

I've discovered that std::strings are very slow compared to old-fashioned null-terminated strings, so much slow that they significantly slow down my overall program by a factor of 2.

I expected STL to be slower, I didn't realise it was going to be this much slower.

I'm using Visual Studio 2008, release mode. It shows assignment of a string to be 100-1000 times slower than char* assignment (it's very difficult to test the run-time of a char* assignment). I know it's not a fair comparison, a pointer assignment versus string copy, but my program has lots of string assignments and I'm not sure I could use the "const reference" trick in all places. With a reference counting implementation my program would have been fine, but these implementations don't seem to exist anymore.

My real question is: why don't people use reference counting implementations anymore, and does this mean we all need to be much more careful about avoiding common performance pitfalls of std::string?

My full code is below.

#include <string>
#include <iostream>
#include <time.h>

using std::cout;

void stop()
{
}

int main(int argc, char* argv[])
{
    #define LIMIT 100000000
    clock_t start;
    std::string foo1 = "Hello there buddy";
    std::string foo2 = "Hello there buddy, yeah you too";
    std::string f;
    start = clock();
    for (int i=0; i < LIMIT; i++) {
        stop();
        f = foo1;
        foo1 = foo2;
        foo2 = f;
    }
    double stl = double(clock() - start) / CLOCKS\_PER\_SEC;

    start = clock();
    for (int i=0; i < LIMIT; i++) {
        stop();
    }
    double emptyLoop = double(clock() - start) / CLOCKS_PER_SEC;

    char* goo1 = "Hello there buddy";
    char* goo2 = "Hello there buddy, yeah you too";
    char *g;
    start = clock();
    for (int i=0; i < LIMIT; i++) {
        stop();
        g = goo1;
        goo1 = goo2;
        goo2 = g;
    }
    double charLoop = double(clock() - start) / CLOCKS_PER_SEC;
    cout << "Empty loop = " << emptyLoop << "\n";
    cout << "char* loop = " << charLoop << "\n";
    cout << "std::string = " << stl << "\n";
    cout << "slowdown = " << (stl - emptyLoop) / (charLoop - emptyLoop) << "\n";
    std::string wait;
    std::cin >> wait;
    return 0;
}

Answer 1

When writing C++ code using any utility class (whether STL or your own) instead of eg. good old C null terminated strings, you need to rememeber a few things.

• If you benchmark without compiler optimisations on (esp. function inlining), classes will lose. They are not built-ins, even stl. They are implemented in terms of method calls.

• Do not create unnesessary objects.

• Do not copy objects if possible.

• Pass objects as references, not copies, if possible,

• Use more specialised method and functions and higher level algorithms. Eg.:

  std::string a = "String a"
  std::string b = "String b"
  
  // Use
  a.swap(b);
  
  // Instead of
  std::string tmp = a;
  a = b;
  b = tmp;
  

And a final note. When your C-like C++ code starts to get more complex, you need to implement more advanced data structures like automatically expanding arrays, dictionaries, efficient priority queues. And suddenly you realise that its a lot of work and your classes are not really faster then stl ones. Just more buggy.

Answer 2

std::string will always be slower than C-strings. C-strings are simply a linear array of memory. You cannot get any more efficient than that, simply as a data structure. The algorithms you use (like strcat() or strcpy()) are generally equivalent to the STL counterparts. The class instantiation and method calls will be, in relative terms, significantly slower than C-string operations (even worse if the implementation uses virtuals). The only way you could get equivalent performance is if the compiler does optimization.

Answer 3

You are most certainly doing something wrong, or at least not comparing "fairly" between STL and your own code. Of course, it's hard to be more specific without code to look at.

It could be that you're structuring your code using STL in a way that causes more constructors to run, or not re-using allocated objects in a way that matches what you do when you implement the operations yourself, and so on.

Answer 4

They didn't go wrong. STL implementation is generally speaking better than yours.

I'm sure that you can write something better for a very particular case, but a factor of 2 is too much... you really must be doing something wrong.

Answer 5

                        string  const string&   char*   Java string
---------------------------------------------------------------------------------------------------
Efficient               no **       yes         yes     yes
assignment                          

Thread-safe             yes         yes         yes     yes

memory management       yes         no          no      yes
done for you

** There are 2 implementations of std::string: reference counting or deep-copy. Reference counting introduces performance problems in multi-threaded programs, EVEN for just reading strings, and deep-copy is obviously slower as shown above. See: Why VC++ Strings are not reference counted?

As this table shows, 'string' is better than 'char*' in some ways and worse in others, and 'const string&' is similar in properties to 'char*'. Personally I'm going to continue using 'char*' in many places. The enormous amount of copying of std::string's that happens silently, with implicit copy constructors and temporaries makes me somewhat ambivalent about std::string.

Answer 6

Well there are definitely known problems regarding the performance of strings and other containers. Most of them have to do with temporaries and unnecessary copies.

It's not too hard to use it right, but it's also quite easy to Do It Wrong. For example, if you see your code accepting strings by value where you don't need a modifiable parameter, you Do It Wrong:

// you do it wrong
void setMember(string a) {
    this->a = a; // better: swap(this->a, a);
}

You better had taken that by const reference or done a swap operation inside, instead of yet another copy. Performance penalty increases for a vector or list in that case. However, you are right definitely that there are known problems. For example in this:

// let's add a Foo into the vector
v.push_back(Foo(a, b));

We are creating one temporary Foo just to add a new Foo into our vector. In a manual solution, that might create the Foo directly into the vector. And if the vector reaches its capacity limit, it has to reallocate a larger memory buffer for its elements. What does it do? It copies each element separately to their new place using their copy constructor. A manual solution might behave more intelligent if it knows the type of the elements before-hand.

Another common problem is introduced temporaries. Have a look at this

string a = b + c + e;

There are loads of temporaries created, which you might avoid in a custom solution that you actually optimize onto performance. Back then, the interface of std::string was designed to be copy-on-write friendly. However, with threads becoming more popular, transparent copy on write strings have problems keeping their state consistent. Recent implementations tend to avoid copy on write strings and instead apply other tricks where appropriate.

Most of those problems are solved however for the next version of the Standard. For example instead of push_back, you can use emplace_back to directly create a Foo into your vector

v.emplace_back(a, b);

And instead of creating copies in a concatenation above, std::string will recognize when it concatenates temporaries and optimize for those cases. Reallocation will also avoid making copies, but will move elements where appropriate to their new places.

For an excellent read, consider Move Constructors by Andrei Alexandrescu.

Sometimes, however, comparisons also tend to be unfair. Standard containers have to support the features they have to support. For example if your container does not keep map element references valid while adding/removing elements from your map, then comparing your "faster" map to the standard map can become unfair, because the standard map has to ensure that elements keep being valid. That was just an example, of course, and there are many such cases that you have to keep in mind when stating "my container is faster than standard ones!!!".