String Concatenation O(n^2)

[Hrvoje Niksic]

"Ian Kelly" <ian.g.kelly at gmail.com> writes:

> 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?

Take a look at ceval.c:string_concatenate.

As Jean-Paul says, note that the optimization doesn't work in many
circumstances.  For example, change local variable to instance
attribute, and it goes away.  Other python implementations don't have
it at all.