[Python-Dev] Wild Idea for the Year

[Phillip J. Eby]

At 02:38 PM 6/27/04 +0100, Armin Rigo wrote:
>Hello,
>
>On Sat, Jun 19, 2004 at 03:40:07PM -0400, Raymond Hettinger wrote:
> >         s = ""
> >         for e in iterable:
> >             s = s + e
>
>Hum, it may not be impossible after all.
>
>http://www.python.org/sf/980695 -> an idea that seems to work and only
>involves 3 pages of obfuscated code in new well-isolated functions of 
>ceval.c.
>stringobject.c is unmodified.

Looks interesting.  It appears the cost is added to cases that are likely 
to have longer execution times anyway.  (i.e. the slow_add and slow_iadd 
cases.)

I notice that string_concatenate() doesn't cover the STORE_DEREF case, 
however.  Was that intentional?

Last question: is this actually faster when 'e' is replaced by an 
expression that causes memory allocation?  That is, isn't this *still* 
going to be an O(n**2) operation if the string has to be relocated on each 
addition?