socket send O(N**2) complexity

Jack Diederich jackdied at gmail.com
Wed Sep 23 01:45:43 CEST 2009


On Tue, Sep 22, 2009 at 7:25 PM, Nobody <nobody at nowhere.com> wrote:
> On Mon, 21 Sep 2009 16:33:08 -0400, Jack Diederich wrote:
>
>>> AIUI, as a python string is imutable, a slice of a string is a
>>> new string which points (C char *) to the start of the slice data
>>> and with a length that is the length of the slice, about 8 bytes
>>> on 32 bit machine.
>>
>> Not in CPython.  While some special strings are re-used (empty string,
>> single letters) if you take a slice of an existing string a new buffer
>> is allocated and the slice memcpy'd into it.
>
> Er, why?
>
> I can understand doing this for mutable sequences, but it doesn't seem
> to make much sense for strings.

Because it adds large amounts of complexity.  If you have a string
that points to 8 bytes in a 1Gig string and the giant string goes out
of scope, what do you do?  You can keep it alive, you can copy out 8
bytes; you can do one of those things now or you can wait until later
when some kind of garbage collection happens.   Once you have that
system why not pile ropes on top of it?  and once you have ropes why
not just make strings mutable ...

If you want much longer mailing list threads about the topic search
the python-dev archives.

-Jack



More information about the Python-list mailing list