std::vector push_back is bottleneck

Question

Here is what my algorithm does: It takes a long std::string and divides it into words and sub words based on if it's greater than a width:

inline void extractWords(std::vector<std::string> &words, std::string &text,const AguiFont &font, int maxWidth)
{


    words.clear();

    int searchStart = 0;
    int curSearchPos = 0;
    char right;
    for(size_t i = 0; i < text.length(); ++i)
    {
        curSearchPos = i;

        //check if a space is to the right
        if( i == text.length() - 1)
            right = 'a';
        else
            right = text[i + 1];

        //sub divide the string if it;s too big
        int subStrWidth = 0;
        int subStrLen = 0;
        for(int x = searchStart; x < (curSearchPos - searchStart) + 1; ++x)
        {
            subStrWidth += font.getTextWidth(&text[x]);
            subStrLen ++;
        }
        if(subStrLen > maxWidth && subStrLen > 1)
        {
            for(int k = 2; k <= subStrLen; ++k)
            {
                subStrWidth = 0;
                for(int p = 0; p < k; ++p)
                {
                    subStrWidth += font.getTextWidth(&text[searchStart + p]);
                }
                if(subStrWidth > maxWidth)
                {
                    searchStart += k - 1;

                    words.push_back(text.substr(searchStart,k - 1));
                    break;

                }
            }
        }

        //add the word
        if((text[i] == ' ' && right != ' ' ) || i == text.length() - 1)
        {

                if(searchStart > 0)
                {
                    words.push_back(text.substr(searchStart ,(curSearchPos - searchStart) + 1));

                }
                else
                {
                    words.push_back(text.substr(0 ,(curSearchPos - searchStart) ));
                    words.back() += text[curSearchPos];

                }

            searchStart = i + 1 ;
        }
    }


}

As you can see, I use std::vectors to push in my words. The vector is given by reference. That std::vector is static and its in the proc that calls extractWord. Oddly enough, making it static caused far more cpu consumption. After profiling, I saw that I'm making lots of heap allocations but I don't know why since a std::vector is supposed to retain its items even after the vector is cleared. Is there maybe a less intensive way of doing this? The string length is unknown, nor is the number of resulting strings which is why I chose a std::vector, however is there possibly a better way?

Thanks

*actually I think my substring generation is what is slow

Answer 1

Generally, if adding elements to a vector is a bottleneck, you should use std::vector<T>::reserve to reserve some space in advance. This should reduce the likelihood that a call to push_back will trigger a memory reallocation.

That said, string processing in general can be pretty CPU intensive, and reallocating a vector of string objects requires a lot of copying. Every time the vector reallocates memory, each string object needs to be copied to another location in memory. (Fortunately, this will be mitigated substantially once C++0x move constructors are in place.)

Also, the fact that you are clearing the vector each time doesn't change the fact that every call to push_back results in copying a string object into the vector, which is probably the cause of all the heap allocations you're seeing. Don't forget that every instance of std::string needs to allocate memory on the heap to store the string.

Answer 2

vector would be the best if you know the number of resulting strings and not if you don't know it. deque or list will do better. but maybe you can check what's the capacity of the vector at the beginning and what's the size in the end.

Answer 3

You could switch to a vector that indirectly holds the strings. Then the strings aren't copied on every resize of the storage, only the "handles" are copied. So instead of std::vector<std::string> &words, something more like std::vector< counted_ptr<std::string> > &words. Then see this Dr. Dobb's article for more about counted_ptr<>.

Also, to avoid a potential Heisenbug chase, auto_ptr<> is not what you want to use for this sort of thing in an STL container.

Answer 4

Firstly, you should consider passing an output iterator instead of a vector&. This would result in a cleaner and more flexible design.

The definition of clear() makes no guarantees about memory utilisation. The implementation is perfectly entitled to free all used memory when you call clear. It could quite reasonably be implemented like so:

void clear() { vector tmp; swap(tmp); }

You might get lucky calling resize(0) instead of clear(), but even that isn't required to preserve the vector's capacity.

If you really want to squash all those memory allocations:

1. Define the function as a template function with an output iterator, as I suggest above, also passing in a count limit.
2. Pass in a plain-old C-array big enough to hold the maximum number of words you expect to see.
3. Use std::pair<const char*, const char*> instead of std::string to hold the words found.

Answer 5

The code looks like it works well but the devil is always in the details when it comes to performance. Here are a few thoughts:

1. Consider changing the vector declaration from :

   from: std::vector< std::string > &words
   to : std::vector< std::string* > &words

   This will create a pointer and assign it an address of the string as opposed to copying the contents of each string into the vector.

2. Try to use vector::reserve to pre-allocate the memory needed to process the string. A rough estimate might be text.length() / maxWidth.

3. Pay close attention to the string operations that are being used. It's very possible that there are alot of temporary strings being generated and immediately thrown away. The best way to find out if this is happening is to step through your string manipulation lines and see if there are extra string constructors and copy constructors ocurring.