Почему моя программа не ускоряется после использования резерва?

Question

Я написал две функции. Во втором я использовал «резерв», чтобы не было перераспределения памяти, но, к сожалению, вторая функция не быстрее первой. Я записал строковые адреса, и в первой функции происходит перераспределение несколько раз, но обе функции выполняются одновременно.

Я думаю, что это должно быть намного быстрее, я не прав?

    string commpres2(string str)
    {
        string strOut;
        int count = 0;
        //int adress = 0;
        for (int i = 0; i < str.length(); ++i)
        {
            ++count;
            if (i < str.length() - 1)
            {
                if (str[i + 1] != str[i])
                {
                    strOut += str[i];
                    strOut += to_string(count);
                    /*if (adress != (int)&strOut[0])
                    {
                        adress = (int)&strOut[0];
                        cout << adress << endl;
                    }*/
                    count = 0;
                }
            }
            else
            {
                strOut += str[i] + to_string(count);
            }
        }
        return strOut.length() < str.length() ? strOut : str;
    }

    string commpres3(string str)
    {
        string strOut;
        strOut.reserve(7000000);
        int count = 0;
        //int adress = 0;
        for (int i = 0; i < str.length(); ++i)
        {
            ++count;
            if (i < str.length() - 1)
            {
                if (str[i + 1] != str[i])
                {
                    strOut += str[i];
                    strOut += to_string(count);
                    /*if (adress != (int)&strOut[0])
                    {
                        adress = (int)&strOut[0];
                        cout << adress << endl;
                    }*/
                    count = 0;
                }
            }
            else
            {
                strOut += str[i] + to_string(count);
            }
        }
        return strOut;
    }

    int main()
    {
        str = "aabcccccaaa";
        //str.size ~= 11000000;
        for (int i = 0; i < 20; ++i)
            str += str;
        commpres2(str); //8 543ms
        commpres3(str); //8 534ms
    }

Вы близки к ответу на мой вопрос, но что-то все еще не хватает. Ниже приведена полная версия моей функции commpres3:

    string commpres3(string str)
    {
        int compressedLength = 0;
        int countConsecutive = 0;
        for (int i = 0; i < str.length(); ++i)
        {
            ++countConsecutive;
            if (i + 1 >= str.length() || str[i] != str[i + 1]) 
            {
                compressedLength += 1 + 
                    to_string(countConsecutive).length();
                countConsecutive = 0;
            }
        }
        if (compressedLength >= str.length())
            return str;
        string strOut;
        strOut.reserve(compressedLength);
        //strOut.reserve(7000000);
        int count = 0;
        //int adress = 0;
        for (int i = 0; i < str.length(); ++i)
        {
            ++count;
            if (i < str.length() - 1)
            {
                if (str[i + 1] != str[i])
                {
                    strOut += str[i];
                    strOut += to_string(count);
                    /*if (adress != (int)&strOut[0])
                    {
                        adress = (int)&strOut[0];
                        cout << adress << endl;
                    }*/
                    count = 0;
                }
            }
            else
            {
                strOut += str[i] + to_string(count);
            }
        }
        return strOut;
    }

    int main()
    {
        str = "aabcccccaaa";
        //str.size ~= 11000000;
        for (int i = 0; i < 20; ++i)
            str += str;
        commpres2(str); //107ms //30,32% CPU
        commpres3(str); //147ms //42,58% CPU
    }

Теперь я использовал режим выпуска и этот профилировщик процессора. Итак, мой вопрос: на самом деле? Выполнение одной строки для подсчета длины занимает больше времени, чем перемещение этой строки пару раз в памяти?

Answer 1

Ваше предположение, что уменьшение количества выделений увеличивает производительность, является верным. Чтобы понять какой-либо выигрыш в производительности, нам нужно увидеть, сколько распределений commpres3 экономит по сравнению с commpres2.

. Мы можем использовать strOut.capacity() для проверки выделенного количества байтов. Когда емкость увеличивается, произошло распределение (или перераспределение):

// Counting number of allocations of compress 2
string commpres2(string str)
{
    string strOut;
    string::size_type capacity = strOut.capacity();
    int allocations = 0;
    int count = 0;

    for (...) {
        // your loop body

        if (capacity < strOut.capacity()) {
            capacity = strOut.capacity();
            ++allocations;
        }
    }

    std::cout << allocations << std::endl;
    return ...;
}

Используя этот код, я получаю результат только из 19 распределений! Это может произойти из-за (пере) стратегии распределения std::string. На моей машине std::string удваивает память каждый раз, когда ей нужно больше. Что делает 19 выделений достаточным для хранения всей строки результата.

С compress3, сохраняющим только 19 выделений, мы можем видеть, насколько разумно увеличение производительности на 7 миллисекунд.

Answer 2

Я не профессионал в этой концепции, но использую «i

, чтобы предотвратить это, в вашей функции «compress3» вместо вызова «str.length () каждый раз, когда вам это нужно, просто сохраните его в целочисленном виде, как« int len ​​= str.length (); "и в вашем l oop используйте" i

ваш код должен выглядеть следующим образом:

string commpres3(string str)
{
    string strOut;
    strOut.reserve(7000000);
    int count = 0;
    //int adress = 0;
    int len = str.length();
    for (int i = 0; i < len; ++i)
    {
        ++count;
        if (i < len - 1)
        {
            if (str[i + 1] != str[i])
            {
                strOut += str[i];
                strOut += to_string(count);
                /*if (adress != (int)&strOut[0])
                {
                    adress = (int)&strOut[0];
                    cout << adress << endl;
                }*/
                count = 0;
            }
        }
        else
        {
            strOut += str[i] + to_string(count);
        }
    }
    return strOut;
}