std::string::erase is stupidly slow when erasing to the end, which impacts std::string::resize

std::string::erase is stupidly slow when erasing to the end, which impacts std::string::resize by Ben Voigt

Closed

as Fixed

Type:	Suggestion
ID:	628197
Opened:	12/3/2010 4:04:10 PM
Access Restriction:	Public

Workaround(s)

view

Here is the code from VC++2010 implementation of std::string::erase (xstring header file), which is used by std::string::resize() when reducing the size:

    _Myt& erase(size_type _Off = 0,
        size_type _Count = npos)
        {    // erase elements [_Off, _Off + _Count)
        if (this->_Mysize < _Off)
            _Xran();    // _Off off end
        if (this->_Mysize - _Off < _Count)
            _Count = this->_Mysize - _Off;    // trim _Count
        if (0 < _Count)
            {    // move elements down
            _Traits::move(_Myptr() + _Off, _Myptr() + _Off + _Count,
                this->_Mysize - _Off - _Count);
            size_type _Newsize = this->_Mysize - _Count;
            _Eos(_Newsize);
            }
        return (*this);
        }

When the line "trim _Count" is reached, the code falls through to "move elements down" and a lot of extra useless code executes.

Is there any difference in behavior if that were changed to (note the insertion of an "else" to prevent the "move elements down" branch from running when there are no elements after the erased region):

    _Myt& erase(size_type _Off = 0,
        size_type _Count = npos)
        {    // erase elements [_Off, _Off + _Count)
        if (this->_Mysize < _Off)
            _Xran();    // _Off off end
        if (this->_Mysize - _Off < _Count)
            _Eos(_Off);    // truncate
        else if (0 < _Count)
            {    // move elements down
            _Traits::move(_Myptr() + _Off, _Myptr() + _Off + _Count,
                this->_Mysize - _Off - _Count);
            size_type _Newsize = this->_Mysize - _Count;
            _Eos(_Newsize);
            }
        return (*this);
        }

In fact, it looks like resize could skip calling erase and simply be:

    void resize(size_type _Newsize, _Elem _Ch)
        {    // determine new length, padding with _Ch elements as needed
        if (_Newsize <= this->_Mysize)
            _Eos(_Newsize); // was erase(_Newsize);
        else
            append(_Newsize - this->_Mysize, _Ch);
        }

But I suppose it would be best to make the change in erase to provide the benefit to both erase and resize.

Details (expand)

Visual Studio 2010

Performance

Code to efficiently convert an 8-bit integer to a std::string, or it would be, if retval.resize didn't take so long:

    static std::string cvt(char val)
    {
        std::string retval(5, '\0');
        int i = 0;
        char ch = 0;

        if (val < 0) {
            retval[i] = '-';
            ++i;
            if (val <= -100) {
                    ch = '1';
                    val += 100;
                }
                val = -val;
        }
        else if (val >= 100) {
            ch |= '1';
            val -= 100;
        }
        if (ch) {
            retval[i] = ch;
            ++i;
            ch = '0';
        }

        if (val >= 80) {
            ch |= '8';
            val -= 80;
        }
        else if (val >= 40) {
            ch |= '4';
            val -= 40;
        }
        if (val >= 20) {
            ch |= '2';
            val -= 20;
        }
        if (val >= 10) {
            ch |= '1';
            val -= 10;
        }
        if (ch) {
            retval[i] = ch;
            ++i;
        }

        retval[i] = '0' + val;
        retval.resize(i+1);

        return retval;
    }

English

Windows 7

English

40% of time spent in std::string::resize is spent inside a useless call to memmove with length == 0

More time is spent calculating the parameters to memmove. It appears that parameter setup and the actual call to memmove together account for >90% of the time in std::string::resize.

std::string::resize should not call memmove when the size is being reduced, it should just adjust the internal size field.

0 attachments

Hi,

Thanks for reporting this bug. We've fixed it, and the fix will be available in VC11. We believe that our new implementations of resize()-smaller, 0-arg erase(), and 1-arg erase(size_type) are optimal. Our new implementation of 2-arg erase(size_type, size_type) should be smaller and faster, although my experiments indicate that it's still too big to be an inlining candidate, so it doesn't exhibit dramatic improvements. (I could probably squeeze out a bit more performance, but I didn't want to overcomplicate the code in the pursuit of saving a few instructions.)

My measurements indicate that:

Your cvt() function is 78.6% faster,
resize()-smaller is 2.70x faster,
0-arg erase() is 2.58x faster,
1-arg erase(size_type) is 2.30x faster, and
2-arg erase(size_type, size_type) is 1.6% faster.

Here's the raw data:

C:\Temp>type meow.cpp
#include <iostream>
#include <ostream>
#include <string>
#include <windows.h>
using namespace std;

long long counter() {
    LARGE_INTEGER li;
    QueryPerformanceCounter(&li);
    return li.QuadPart;
}

long long frequency() {
    LARGE_INTEGER li;
    QueryPerformanceFrequency(&li);
    return li.QuadPart;
}

void print_time(const long long start, const long long finish, const char * const s) {
    cout << s << ": " << (finish - start) * 1000.0 / frequency() << " ms" << endl;
}

string cvt(char val) {
    string retval(5, '\0');
    int i = 0;
    char ch = 0;
    if (val < 0) {
        retval[i] = '-';
        ++i;
        if (val <= -100) {
            ch = '1';
            val += 100;
        }
        val = -val;
    } else if (val >= 100) {
        ch |= '1';
        val -= 100;
    }
    if (ch) {
        retval[i] = ch;
        ++i;
        ch = '0';
    }
    if (val >= 80) {
        ch |= '8';
        val -= 80;
    } else if (val >= 40) {
        ch |= '4';
        val -= 40;
    }
    if (val >= 20) {
        ch |= '2';
        val -= 20;
    }
    if (val >= 10) {
        ch |= '1';
        val -= 10;
    }
    if (ch) {
        retval[i] = ch;
        ++i;
    }
    retval[i] = '0' + val;
    retval.resize(i+1);
    return retval;
}

int main() {
    cout << "_MSC_FULL_VER: " << _MSC_FULL_VER << endl;
    const int N = 100 * 1000 * 1000;
    size_t dummy = 0;

    long long start = counter();
    for (int i = 0; i < N; ++i) {
        dummy += cvt(i % 128).size();
    }
    long long finish = counter();
    print_time(start, finish, "cvt()");

    start = counter();
    for (int i = 0; i < N; ++i) {
        string s(5, 'x');
        s.resize(3);
        dummy += s.size();
    }
    finish = counter();
    print_time(start, finish, "resize()-smaller");

    start = counter();
    for (int i = 0; i < N; ++i) {
        string s(10, 'x');
        s.erase();
        dummy += s.size();
    }
    finish = counter();
    print_time(start, finish, "0-arg erase()");

    start = counter();
    for (int i = 0; i < N; ++i) {
        string s(10, 'x');
        s.erase(3);
        dummy += s.size();
    }
    finish = counter();
    print_time(start, finish, "1-arg erase(size_type)");

    start = counter();
    for (int i = 0; i < N; ++i) {
        string s(10, 'x');
        s.erase(3, 4);
        dummy += s.size();
    }
    finish = counter();
    print_time(start, finish, "2-arg erase(size_type, size_type)");

    cout << "dummy: " << dummy << endl;
}

C:\Temp>cl /EHsc /nologo /W4 /MT /O2 /GL meow.cpp
meow.cpp
Generating code
Finished generating code

[VC10 RTM]
C:\Temp>meow
_MSC_FULL_VER: 160030319
cvt(): 3082.99 ms
resize()-smaller: 1206.86 ms
0-arg erase(): 1204.36 ms
1-arg erase(size_type): 1162.47 ms
2-arg erase(size_type, size_type): 1322.73 ms
dummy: 1414062500

[VC11]
C:\Temp>meow
_MSC_FULL_VER: 170040203
cvt(): 1726.51 ms
resize()-smaller: 447.35 ms
0-arg erase(): 465.965 ms
1-arg erase(size_type): 505.477 ms
2-arg erase(size_type, size_type): 1301.71 ms
dummy: 1414062500

If you have any further questions, feel free to E-mail me at stl@microsoft.com .

Stephan T. Lavavej
Visual C++ Libraries Developer