PATCH: Speed up direct string concatenation by 20+%!

[Larry Hastings]

Re: PATCH: Speed up direct string concatenation by 20+%!

Istvan Albert wrote:

I remember a similar patch from some time ago:

http://mail.python.org/pipermail/pyt...st/046686.html

That patch addressed the same general problem, but took a completely
different approach. For the record, this patch (#980695) optimized "x
+= a" by examining the next instruction after the addition. If it's a
store instruction, and the object being stored to holds a reference to
the left side of the concatenation, it makes the object drop the
reference *before* doing the concatenation. In the case where there
was only one reference to the string on the left side (that being "x"),
this allows the string concatenation function to use a very fast
shortcut: resize the left side and concatenate the right side directly
to the end.

The patch was accepted in August of 2004, so it might have been folded
in to CPython during the 2.3 era; certainly it was part of CPython 2.4.

And, happily, that optimization is complimentary to mine. In my patch,
when the left side only has one reference and it's a "string
concatenation object", it will often have space left in its internal
array of strings objects. In that case I just append the string.
Speeds things up immensely.

Cheers,


/larry/

[Istvan Albert]

Re: PATCH: Speed up direct string concatenation by 20+%!

Larry Hastings wrote:

That patch addressed the same general problem, but took a completely
different approach. For the record, this patch (#980695) optimized "x

Larry,

Forgot to mention this, in case you haven't done so post your original
message/patch on the python-dev lists since that's where the decisions
are made. This group is more end-user oriented.

http://mail.python.org/pipermail/python-dev/2006-October/thread.html

i.

[Terry Reedy]

Re: PATCH: Speed up direct string concatenation by 20+%!


"Forgot to mention this, in case you haven't done so post your original

message/patch on the python-dev lists since that's where the decisions
are made. This group is more end-user oriented.
>
http://mail.python.org/pipermail/pyt...er/thread.html

It is often good to get community input first, as the OP has done. When he
wishes, the OP should submit his latest (not original) version of the patch
to SourceForge (not the list) and then optionally post a new message with a
link to the SF item for discussion.

tjr

[Nicko]

Re: PATCH: Speed up direct string concatenation by 20+%!

Larry Hastings wrote:

It's *slightly* slower for two:
>
def addTwoThings(a, b):
return a + b
for i in range(10000000) :
x = addTwoThings("a aa", "bbb")

....

But starts paying off already, even with three:
>
def addThreeThings( a, b, c):
return a + b + c
for i in range(10000000) :
x = addThreeThings( "aaa", "bbb", "ccc")

I note that in both of those tests you didn't actually ever realise the
concatenated string. Can you give us figures for these tests having
forced the concatenated string to be computed?

Cheers,
Nicko

[Larry Hastings]

Re: PATCH: Speed up direct string concatenation by 20+%!

Nicko wrote:

I note that in both of those tests you didn't actually ever realise the
concatenated string. Can you give us figures for these tests having
forced the concatenated string to be computed?

Sure, good call. And bad news.

All these benchmarks were with functions taking N arguments that just
added (concatenated) the arguments and returned the result. I only ran
each benchmark once.

| Python 2.5 | Python 2.5
arguments | release | concat
-------------+--------------+--------------
2 | 7718ms | 9078ms
3 | 9203ms | 10500ms
4 | 10656ms | 11656ms
5 | 12156ms | 13390ms
20 | 29359ms | 26703ms

Interpret as you see fit,


/larry/