[Python-Dev] Socket timeout patch

Tim Peters tim.one@comcast.net
Mon, 03 Jun 2002 13:32:27 -0400

>>> - Maybe changing the write buffer to a list makes sense too?

>>  I could do this. Then just do a join before the flush. Is the append
>> /that/ much faster?

> Depends on how small the chunks are you write.  Roughly, repeated list
> append is O(N log N), while repeated string append is O(N**2).

Repeated list append is O(N) amortized (a single append may take O(N) time
all by itself, but if you do N of them in a row the time is still no worse
than O(N) overall; a possible conceptual difficulty may arise here because
the value of "N" changes over time, and while growing to a total of size N
may require O(log N) whole-list copies, each of the copies involves far
fewer elements than the final value of N -- if you add up all these smaller
values of N in the worst case, the sum is O(N) wrt the final value of N, and
so it's worst-case O(N) overall wrt the final value of N).