From: Warren Young
Date: March 23 2011 2:11pm
Subject: Re: growth behavior of std::vector
List-Archive: http://lists.mysql.com/plusplus/9275
Message-Id: <4D89FF7F.30706@etr-usa.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

On 3/23/2011 6:09 AM, Tomalak Geret'kal wrote:
> On 23/03/2011 11:59, Warren Young wrote:
>> On 3/23/2011 4:07 AM, Tomalak Geret'kal wrote:
>>>
>>> It's not necessarily strictly doubled.
>>
>> Name an implementation of std::vector that doesn't do this.
>
> I'm in the process of attempting to compile a list of multipliers across
> toolchains. I'll post it when it's done if you're interested.

Sure, as long as you restrict the toolchains you report on to those 
currently supported by MySQL++.  Such a report would be relevant to the 
run-time behavior of MySQL++.

> That the multiplier is not
> standardised means that on any toolchain it could change at any time.

The mere fact that the C++ standard says a thing does not make it a 
legitimate topic here, just because MySQL++ is written in C++.  It 
doesn't become on-topic here until it affects one of the compilers 
supported by MySQL++ and also affects the actual behavior of MySQL++. 
Without such a case to ground the discussion, talking about it here is 
mere language lawyer wankery.

> doesn't really matter whether all your favourite implementations
> currently use a doubling-up technique if they could legally stop doing
> that at any time.

Some of the language in the Standard allows the implementation to cause 
monkeys to fly out the USB port.

One way to react to that possibility is to wrap all uses of unspecified 
library behavior with an infinite series of conditionals:

     if (monkeys_fly_out_of_the_usb_port()) {
        ...
     }
     else if (phase_of_the_moon_is_waxing_gibbous()) {
        ...
     }

A more reasonable reaction is to learn the actual behavior of our tools 
and make reasoned decisions about how likely those behaviors are to 
change.  If the likelihood is low, assume the behavior won't change.

> The phrasing "the number of records possible from the query" implied to
> me that no higher number would be possible, and reserving more space
> than is possible to fill is the "waste of space" I was talking about.

Obviously if you happen to know in advance exactly how many records your 
query will return, reserve() space for only that many records.  In all 
other cases, if you are able to guess, reserving that amount plus a 
small fudge factor is a sane strategy.

If you are wrong and your vector implementation's growth strategy is the 
common 2x one, you have only one reallocation and copy unless you are 
wrong by a factor of 2 * (1 + fudge_factor).  If the fudge factor is 
10%, that means you have to underestimate the number of returned records 
by more than 220% to get two or more reallocations and copies.