std::vector push_back is bottleneck
c++, vector
Solution
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.
Problem
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