socket send O(N**2) complexity

Jack Diederich jackdied at gmail.com
Mon Sep 21 22:33:08 CEST 2009


On Mon, Sep 21, 2009 at 4:00 PM, Rob Williscroft <rtw at freenet.co.uk> 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.

> So even though a slice assignment new_s = s[:] appears to a python
> programmer to make a "copy" of s, its only the a few bytes of
> metadata (the pointer and the length) that is really copied, the
> strings character data stays where it is.

There is a special case for copy in CPython that avoids copying the
string bytes, BUT in that case it just INCREFs the existing object and
returns it.  There are no new allocations at all.

Be very careful recommending optimizations based on how you think the
underlying implementation works without double checking with the code
first.

-Jack



More information about the Python-list mailing list