std::vector push_back 是瓶颈 [英] std::vector push_back is bottleneck

问题描述

这是我的算法的作用:它需要一个长 std::string 并根据它是否大于宽度将其分为单词和子单词:

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 ;
        }
    }


}

如您所见，我使用 std::vectors 来表达我的意思.向量通过引用给出.std::vector 是静态的，它在调用extractWord 的过程中.奇怪的是，将其设为静态会导致更多的 CPU 消耗.分析后，我看到我进行了大量的堆分配，但我不知道为什么，因为即使在清除向量之后 std::vector 也应该保留其项目.是否有一种不那么密集的方式来做到这一点?字符串长度未知，结果字符串的数量也未知，这就是我选择 std::vector 的原因，但是可能有更好的方法吗?

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?

谢谢

*实际上我认为我的子串生成很慢

*actually I think my substring generation is what is slow

推荐答案

一般来说，如果向 vector 添加元素是一个瓶颈，你应该使用 std::vector::reserve提前预留一些空间.这应该会降低调用 push_back 触发内存重新分配的可能性.

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.

也就是说，字符串处理通常会占用大量 CPU，并且重新分配字符串对象的向量需要大量的复制.每次向量重新分配内存时，每个字符串对象都需要复制到内存中的另一个位置.(幸运的是，一旦 C++0x 移动构造函数就位，这将大大减轻.)

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.)

此外，您每次都清除向量这一事实并不会改变每次调用 push_back 都会导致将字符串对象复制到向量中的事实，这可能是所有您看到的堆分配.不要忘记 std::string 的每个实例都需要在堆上分配内存来存储字符串.

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.

这篇关于std::vector push_back 是瓶颈的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！