[Tutor] a little loop

[Steven D'Aprano]

On 30/05/13 02:51, boB Stepp wrote:
> On Wed, May 29, 2013 at 11:07 AM, Oscar Benjamin
> <oscar.j.benjamin at 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