String Concatenation O(n^2) (was: Re: Explaining Implementing a Binary Search Tree.)

[Jean-Paul Calderone]

On Mon, 16 Jun 2008 11:30:19 -0600, Ian Kelly <ian.g.kelly at gmail.com> wrote:
>On Mon, Jun 16, 2008 at 11:09 AM, Jean-Paul Calderone
><exarkun at divmod.com> wrote:
>> It will depend what version of Python you're using and the *exact* details
>> of the code in question.  An optimization was introduced where, if the
>> string being concatenated to is not referred to anywhere else, it will be
>> re-sized in place.  This means you'll probably see sub-quadratic behavior,
>> but only with a version of Python where this optimization exists and only
>> if the code can manage to trigger it.
>
>AFAICT, PyString_Concat never calls _PyString_Resize.  Am I looking in
>the wrong place?

Yep.  The optimization is done directly from the eval loop.  Take a look at
ceval.c, if you search for _PyString_Resize you should see it.

Jean-Paul