[Bug libstdc++/51359] New: std::string::reserve inefficiency/possible accidental behavior with reserve()

[nacitar at gmail dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51359

             Bug #: 51359
           Summary: std::string::reserve inefficiency/possible accidental
                    behavior with reserve()
    Classification: Unclassified
           Product: gcc
           Version: 3.4.6
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: nacitar@gmail.com


Not entirely sure 3.4.6 is the right version, but I retrieved the sources via:

svn checkout svn://gcc.gnu.org/svn/gcc/trunk gcc

On 11/30/2011.


This may be a "bug" in that this behavior was not intended, though it doesn't
cause incorrect behavior; just not as efficient as it could be.

Anyhow, looking at the code for .reserve(), it lets you pass in how much to
reserve.  It then has an if statement that determines if it should reallocate,
which essentially says:

if (provided_reserve != current_capacity || is_shared)
{
    provided_reserve = max(current_size, provided_reserve);
    _M_clone();
}


This is bad for one reason...

Suppose you have any random string, and you call reserve with the same value
repeatedly.

        std::string strBloop = "bloop";
        strBloop.reserve(0); // this will reallocate, calling _M_clone()
        strBloop.reserve(0); // this will once again reallocate, calling
_M_clone()


Also note _M_clone() invokes _S_create()

The reason this happens, is that the reserve request is polished in a few ways:
- in reserve(): Ensured to be >= size()
- in S_create(): capacity is adjusted using some logic involving the page size
estimate, as well as some logic rounding it up to 2*old_capacity...

Point being, the capacity after these adjustments will most likely NOT be the
value you passed to reserve.  This is normally fine, because it's efficient.

However, it might make more sense to compare:
    if (adjusted_reserve(provided_reserve) != capacity())

Because every time you pass a given reserve, it gets adjusted using the same
math.  So hypothetically, say that calling reserve(0) results in capacity() ==
5.  Calling reserve(0) then causes another reallocation, because 0 != 5... but
after the reallocation, capacity() will once again == 5.

This might require moving the adjustment logic out of S_create, but it makes
far more sense to compare what the resultant capacity would be with the current
capacity than the provided reserve (prior to adjustment) to the current
capacity (which was adjusted).