Python and STL efficiency

[Neil Cerutti]

On 2006-08-25, Ben Sizer <kylotan at gmail.com> wrote:
> Neil Cerutti wrote:
>> On 2006-08-24, JSprenkle at gmail.com <JSprenkle at gmail.com> wrote:
>> > It will run a lot faster if it doesn't have to keep resizing
>> > the array.
>>
>> I don't see why it should run a lot faster that way.
>>
>> Appending elements to a vector with push_back takes amortized
>> constant time. In the example above, preallocating 40000
>> strings saves (probably) math.log(40000, 2) reallocations of
>> the vector's storage along with the consequent
>> copy-construction and destruction of some fixed number of
>> strings. Most of those reallocations take place while the
>> vector is still proportionally quite small.
>
> Math.log(40000, 2) is not a small number when talking about a
> relatively expensive operation such as memory allocation and
> deallocation. And the superfluous copying amounts to probably
> an extra 2^16 copies in this case - not exactly trivial.

Actually, I misread the suggestion.

I thought I saw:

  vector<string> v;
  v.reserve(40000);

instead of:

  vector<string> v(40000);

The latter actually *slows* the program, according to my tests. I
think the poster meant to suggest the former, and that's what I
was discussing.

I increased the number of iterations from 10000 to 100000 for the
tests I'm reporting.

The best of five, with reserve, was 2363 clock ticks. Without
reserve, it was 3244. The suggestion to use an initial size
resulted in 3655 clocks.

So it appears you were more right (using reserve sped up the
program by 35%, just about as the numbers predict), although we
were both wrong. ;)

-- 
Neil Cerutti
8 new choir robes are currently needed, due to the addition of
several new members and to the deterioration of some of the
older ones. --Church Bulletin Blooper