Hello, The SF patch http://www.python.org/sf/980695 about making repeated string concatenations efficient has been reviewed and is acceptable on technical grounds. This is about avoiding the quadratic behavior of s = '' for x in y: s += some_string(x) This leaves open the policy questions: * first, is that an implementation detail or a published feature? The question is important because the difference in performance is enormous -- we are not talking about 2x or even 10x faster but roughly Nx faster where N is the size of the input data set. * if it is a published feature, what about Jython? * The patch would encourage a coding style that gives program that essentially don't scale with Jython -- nor, for that matter, with 2.3 or older -- and worse, the programs would *appear* to work on Jython or 2.3 when tested with small or medium-sized data sets, but just appear to hang when run on larger data sets. Obviously, this is problem that has always been here, but if we fix it in 2.4 we can be sure that people will develop and test with 2.4, and less thoroughly on 2.3, and when they deploy on 2.3 platforms it will unexpectedly not scale. * discussed on SF too is whether we should remove the 'a=a+b' acceleration from the patch, keeping only 'a+=b'; see the SF tracker. This seems overkill, but should the acceleration be there but disabled by default? from __future__ import string_concatenate? A bientôt, Armin.
The SF patch http://www.python.org/sf/980695 about making repeated string concatenations efficient has been reviewed and is acceptable on technical grounds. This is about avoiding the quadratic behavior of
s = '' for x in y: s += some_string(x)
FWIW, I didn't approve it, Raymond did, IMO prematurely. :-( In the past similar schemes based on refcount were rejected because we couldn't be sure that there wasn't C code with an uncounted reference. Is that ruled out in this scheme? Also, I believe that even Java doesn't optimize this case in general -- only the much simpler case where you concatenate a number of strings in a single expression.
This leaves open the policy questions:
* first, is that an implementation detail or a published feature? The question is important because the difference in performance is enormous -- we are not talking about 2x or even 10x faster but roughly Nx faster where N is the size of the input data set.
Like tail recursion, it will change the way people write code. I am going to make up a new rule here, and state that implementation features that affect not just the running speed but the O() rate for certain algorithms should be considered language features, because any implementation will be required to implement them in order to ensure code portability.
* if it is a published feature, what about Jython?
* The patch would encourage a coding style that gives program that essentially don't scale with Jython -- nor, for that matter, with 2.3 or older -- and worse, the programs would *appear* to work on Jython or 2.3 when tested with small or medium-sized data sets, but just appear to hang when run on larger data sets. Obviously, this is problem that has always been here, but if we fix it in 2.4 we can be sure that people will develop and test with 2.4, and less thoroughly on 2.3, and when they deploy on 2.3 platforms it will unexpectedly not scale.
* discussed on SF too is whether we should remove the 'a=a+b' acceleration from the patch, keeping only 'a+=b'; see the SF tracker.
This seems overkill, but should the acceleration be there but disabled by default?
from __future__ import string_concatenate?
Why do people want this so badly? Please leave well enough alone. --Guido van Rossum (home page: http://www.python.org/~guido/)
The SF patch http://www.python.org/sf/980695 about making repeated string concatenations efficient has been reviewed and is acceptable on technical grounds. This is about avoiding the quadratic behavior of
s = '' for x in y: s += some_string(x)
FWIW, I didn't approve it, Raymond did, IMO prematurely. :-(
In the past similar schemes based on refcount were rejected because we couldn't be sure that there wasn't C code with an uncounted reference. Is that ruled out in this scheme?
Yes it is. Unlike the refcount check proposed for PyList_Sort, Armin's patch only applies to the eval loop and cannot be called directly. I spent a *long* time reviewing and testing this patch. The code is clean. The concept works. It delivers significant, measurable benefits. The standard library itself has existing use cases. Every benchmark I tried showed results. The patch was not approved prematurely! On the off chance that Armin, Michael, and I missed a case, then including the patch in the second alpha is the best way to find it.
I am going to make up a new rule here, and state that implementation features that affect not just the running speed but the O() rate for certain algorithms should be considered language features, because any implementation will be required to implement them in order to ensure code portability.
Even list.sort() does not guarantee specific O() rates. Currently, the fastest way to write a merge(a,b) is sort(a+b). That relies on the current implementation recognizing that a and b are already sorted and doing a linear time concatenation.
Why do people want this so badly?
Because the a=a+b form occurs everywhere, not just in newbie code. It is in the standard library, it shows up naturally in SAX, and it is often the most clear way to express an idea. Raymond
I spent a *long* time reviewing and testing this patch. The code is clean. The concept works. It delivers significant, measurable benefits. The standard library itself has existing use cases. Every benchmark I tried showed results. The patch was not approved prematurely!
Yes it was. You know I am interested in this kind of decision (otherwise you'd have just checked it in) so you should have left the honor to me.
I am going to make up a new rule here, and state that implementation features that affect not just the running speed but the O() rate for certain algorithms should be considered language features, because any implementation will be required to implement them in order to ensure code portability.
Even list.sort() does not guarantee specific O() rates. Currently, the fastest way to write a merge(a,b) is sort(a+b). That relies on the current implementation recognizing that a and b are already sorted and doing a linear time concatenation.
That's a much more obscure case. The string concatenation hack will affect a significant fraction of all code.
Why do people want this so badly?
Because the a=a+b form occurs everywhere, not just in newbie code. It is in the standard library, it shows up naturally in SAX, and it is often the most clear way to express an idea.
And in 99% of those cases nobody cares about performance. --Guido van Rossum (home page: http://www.python.org/~guido/)
Why do people want this so badly?
As someone relatively new to python, it struck me as a language wart that i had to learn the form '"".join() as the proper way to do string concatenation. It violates the principles of OOWTI and its certainly not the obvious way to do string concatenation. This patch does not cover all the cases so we're still stuck with join(), but as long as it is not a documentated "feature" it will harmlessly improve the performance of countless lines of code where the coder is either untrained or too lazy to use join(). If its documented it'd just muddy the waters vis a vis join(), besides the issues with other Python implementation mentioned here. -- adam On Tue, 03 Aug 2004 08:27:26 -0700, Guido van Rossum <guido@python.org> wrote:
I spent a *long* time reviewing and testing this patch. The code is clean. The concept works. It delivers significant, measurable benefits. The standard library itself has existing use cases. Every benchmark I tried showed results. The patch was not approved prematurely!
Yes it was. You know I am interested in this kind of decision (otherwise you'd have just checked it in) so you should have left the honor to me.
I am going to make up a new rule here, and state that implementation features that affect not just the running speed but the O() rate for certain algorithms should be considered language features, because any implementation will be required to implement them in order to ensure code portability.
Even list.sort() does not guarantee specific O() rates. Currently, the fastest way to write a merge(a,b) is sort(a+b). That relies on the current implementation recognizing that a and b are already sorted and doing a linear time concatenation.
That's a much more obscure case. The string concatenation hack will affect a significant fraction of all code.
Why do people want this so badly?
Because the a=a+b form occurs everywhere, not just in newbie code. It is in the standard library, it shows up naturally in SAX, and it is often the most clear way to express an idea.
And in 99% of those cases nobody cares about performance.
--Guido van Rossum (home page: http://www.python.org/~guido/) _______________________________________________ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/adamsz%40gmail.com
Adam Souzis wrote:
As someone relatively new to python, it struck me as a language wart that i had to learn the form '"".join() as the proper way to do string concatenation. It violates the principles of OOWTI and its certainly not the obvious way to do string concatenation. This patch does not cover all the cases so we're still stuck with join(), but as long as it is not a documentated "feature" it will harmlessly improve the performance of countless lines of code where the coder is either untrained or too lazy to use join(). If its documented it'd just muddy the waters vis a vis join(), besides the issues with other Python implementation mentioned here.
If I understand correctly, you're suggesting that ''.join(strings) continue to be the recommended, portable, non-quadratic method for concatenating strings. And this patch be seen merely as a CPython optimisation for code which doesn't use the recommended string concatenation hack. . . Seems like a sensible way of looking at it to me. Cheers, Nick. -- Nick Coghlan | Brisbane, Australia Email: ncoghlan@email.com | Mobile: +61 409 573 268
Nick Coghlan wrote:
Adam Souzis wrote:
As someone relatively new to python, it struck me as a language wart that i had to learn the form '"".join() as the proper way to do string concatenation. It violates the principles of OOWTI and its certainly not the obvious way to do string concatenation. This patch does not cover all the cases so we're still stuck with join(), but as long as it is not a documentated "feature" it will harmlessly improve the performance of countless lines of code where the coder is either untrained or too lazy to use join(). If its documented it'd just muddy the waters vis a vis join(), besides the issues with other Python implementation mentioned here.
If I understand correctly, you're suggesting that ''.join(strings) continue to be the recommended, portable, non-quadratic method for concatenating strings.
I think the "portable" label is a little misleading. It isn't like using string concatenation now is non-portable, it's just slow. The other labels are correct, though. -Brett
participants (6)
-
Adam Souzis -
Armin Rigo -
Brett C. -
Guido van Rossum -
Nick Coghlan -
Raymond Hettinger