<p dir="ltr"><br>
On 12 Aug 2014 11:21, "Chris Barker - NOAA Federal" <<a href="mailto:chris.barker@noaa.gov">chris.barker@noaa.gov</a>> wrote:<br>
><br>
> Sorry for the bike shedding here, but:<br>
><br>
>> The quadratic behaviour of repeated str summation is a subtle, silent error.<br>
><br>
> OK, fair enough. I suppose it would be hard and ugly to catch those instances and raise an exception pointing users to "".join.<br>
>><br>
>> *is* controversial that CPython silently optimises some cases of it away, since it can cause problems when porting affected code to other interpreters that don't use refcounting and thus have a harder time implementing such a trick.<br>

><br>
> Is there anything in the language spec that says string concatenation is O(n^2)? Or for that matter any of the performs characteristics of build in types? Those striker as implementation details that SHOULD be particular to the implementation.</p>

<p dir="ltr">If you implement strings so they have multiple data segments internally (as is the case for StringIO these days), yes, you can avoid quadratic time concatenation behaviour. Doing so makes it harder to meet other complexity expectations (like O(1) access to arbitrary code points), and isn't going to happen in CPython regardless due to C API backwards compatibility constraints.</p>

<p dir="ltr">For the explicit loop with repeated concatenation, we can't say "this is slow, don't do it". People do it anyway, so we've opted for the "fine, make it as fast as we can" option as being preferable to an obscure and relatively hard to debug performance problem.</p>

<p dir="ltr">For sum(), we have the option of being more direct and just telling people Python's answer to the string concatenation problem (i.e. str.join). That is decidedly *not* the series of operations described in sum's documentation as "Sums start and the items of an iterable from left to right and returns the total."</p>

<p dir="ltr">Regards,<br>
Nick.</p>