On 30/05/13 02:51, boB Stepp wrote:
On Wed, May 29, 2013 at 11:07 AM, Oscar Benjamin
<oscar.j.benja...@gmail.com> wrote:
I don't know exactly how str.join is implemented but it does not use
this quadratic algorithm. For example if str.join would first compute
the length of the resulting string first then it can allocate memory
for exactly one string of that length and copy each substring to the
appropriate place (actually I imagine it uses an exponentially
resizing buffer but this isn't important).
I have not actually read the str.join source code, but what I understand is
that it has two cases:
1) If you pass a sequence of sub-strings to join, say, a list, it can look at
each sub-string, calculate the total space required, and allocate a string
buffer of exactly that amount of memory, and only then copy the characters into
the buffer.
2) If you pass an iterator, join cannot go over the sub-strings twice, it has
to do so in one pass. It probably over-allocates the buffer, then when
finished, shrinks it back down again.
Sure enough, ''.join(list-of-substrings) is measurably faster than
''.join(iterator-of-substrings).
...str.join gets around these issues? In the linked article it was
discussing increasing memory allocation by powers of two instead of
trying to determine the exact length of the strings involved,
mentioning that the maximum wasted memory would be 50% of what was
actually needed. Is Python more clever in its implementation?
In the case of lists, CPython will over-allocate. I believe that up to some
relatively small size, lists are initially quadrupled in size, after which time
they are doubled. The exact cut-off size is subject to change, but as an
illustration, we can pretend that it looks like this:
- An empty list is created with, say, 20 slots, all blank.
- When all 20 slots are filled, the next append or insert will increase the
size of the list to 80 slots, 21 of which are used and 59 are blank.
- When those 80 slots are filled, the next append or insert will increase to
320 slots.
- When those are filled, the number of slots is doubled to 640.
- Then 1280, and so forth.
So small lists "waste" more memory, up to 75% of the total size, but who cares,
because they're small. Having more slots available, they require even fewer resizes, so
they're fast.
However, I emphasis that the exact memory allocation scheme is not guaranteed,
and is subject to change without notice. The only promise made, and this is
*implicit* and not documented anywhere, is that appending to a list will be
amortised to constant time, on average.
(Guido van Rossum, Python's creator, has said that he would not look kindly on
anything that changed the basic performance characteristics of lists.)
When creating a string, Python may be able to determine the exact size
required, in which case no over-allocation is needed. But when it can't, it may
use a similar over-allocation strategy as for lists, except that the very last
thing done before returning the string is to shrink it down so there's no
wasted space.
* CPython actually has an optimisation that can append strings in
precisely this situation. However it is an implementation detail of
CPython that may change and it does not work in other interpreters
e.g. Jython. Using this kind of code can damage portability since your
program may run fine in CPython but fail in other interpreters.
You are speaking of "appending" and not "concatenation" here?
Yes. Because strings are immutable, under normal circumstances, concatenating
two strings requires creating a third. Suppose you say:
A = "Hello "
B = "World!"
C = A + B
So Python can see that string A has 6 characters, and B has 6 characters, so C
requires space for 12 characters:
C = "------------"
which can then be filled in:
C = "Hello World!"
and now string C is ready to be used.
But, suppose we have this instead:
A = A + B # or A += B
The *old* A is used, then immediately discarded, and replaced with the new
string. This leads to a potential optimization: instead of having to create a
new string, Python can resize A in place:
A = "Hello ------"
B = "World!"
then copy B into A:
A = "Hello World!"
But note that Python can only do this if A is the one and only reference to the
string. If any other name, list, or other object is pointing to the string,
this cannot be done. Also, you can't do it for the reverse:
B = A + B
since memory blocks can generally only grow from one side, not the other.
Finally, it also depends on whether the operating system allows you to grow
memory blocks in the fashion. It may not. So the end result is that you cannot
really rely on this optimization. It's nice when it is there, but it may not
always be there.
And just a reminder, none of this is important for one or two string
concatenations. It's only when you build up a string from repeated
concatenations that this becomes an issue.
--
Steven
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor
