Home Dashboard Directory Help
Search

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


Status: 

Closed
 as Fixed Help for as Fixed


5
0
Sign in
to vote
Type: Suggestion
ID: 628197
Opened: 12/3/2010 4:04:10 PM
Access Restriction: Public
0
Workaround(s)
view

Description

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
Sign in to post a comment.
Posted by Microsoft on 2/9/2011 at 5:18 PM
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
Posted by Microsoft on 12/3/2010 at 4:22 PM
Thank you for your feedback, we are currently reviewing the issue you have submitted. If this issue is urgent, please contact support directly(http://support.microsoft.com)
Sign in to post a workaround.