[Python-Dev] PATCH submitted: Speed up + for string concatenation, now as fast as "".join(x) idiom

[Larry Hastings]

I've never liked the "".join([]) idiom for string concatenation; in my 
opinion it violates the principles "Beautiful is better than ugly." and 
"There should be one-- and preferably only one --obvious way to do it.". 
(And perhaps several others.)  To that end I've submitted patch #1569040 
to SourceForge:
    
http://sourceforge.net/tracker/index.php?func=detail&aid=1569040&group_id=5470&atid=305470
This patch speeds up using + for string concatenation.  It's been in 
discussion on c.l.p for about a week, here:
    
http://groups.google.com/group/comp.lang.python/browse_frm/thread/b8a8f20bc3c81bcf

I'm not a Python guru, and my initial benchmark had many mistakes. With 
help from the community correct benchmarks emerged: + for string 
concatenation is now roughly as fast as the usual "".join() idiom when 
appending.  (It appears to be *much* faster for prepending.)  The 
patched Python passes all the tests in regrtest.py for which I have 
source; I didn't install external packages such as bsddb and sqlite3.

My approach was to add a "string concatenation" object; I have since 
learned this is also called a "rope".  Internally, a 
PyStringConcatationObject is exactly like a PyStringObject but with a 
few extra members taking an additional thirty-six bytes of storage.  
When you add two PyStringObjects together, string_concat() returns a 
PyStringConcatationObject which contains references to the two strings.  
Concatenating any mixture of PyStringObjects and 
PyStringConcatationObjects works similarly, though there are some 
internal optimizations.

These changes are almost entirely contained within 
Objects/stringobject.c and Include/stringobject.h.  There is one major 
externally-visible change in this patch: PyStringObject.ob_sval is no 
longer a char[1] array, but a char *. Happily, this only requires a 
recompile, because the CPython source is *marvelously* consistent about 
using the macro PyString_AS_STRING().  (One hopes extension authors are 
as consistent.)  I only had to touch two other files (Python/ceval.c and 
Objects/codeobject.c) and those were one-line changes.  There is one 
remaining place that still needs fixing: the self-described "hack" in 
Mac/Modules/MacOS.c.  Fixing that is beyond my pay grade.

I changed the representation of ob_sval for two reasons: first, it is 
initially NULL for a string concatenation object, and second, because it 
may point to separately-allocated memory.  That's where the speedup came 
from--it doesn't render the string until someone asks for the string's 
value.  It is telling to see my new implementation of 
PyString_AS_STRING, as follows (casts and extra parentheses removed for 
legibility):
    #define PyString_AS_STRING(x) ( x->ob_sval ? x->ob_sval : 
PyString_AsString(x) )
This adds a layer of indirection for the string and a branch, adding a 
tiny (but measurable) slowdown to the general case.  Again, because the 
changes to PyStringObject are hidden by this macro, external users of 
these objects don't notice the difference.

The patch is posted, and I have donned the thickest skin I have handy.  
I look forward to your feedback.

Cheers,


/larry/