On Mon, 3 May 2010 00:50:40 +1000
Steven D'Aprano <st...@pearwood.info> wrote:
> On Sun, 2 May 2010 07:44:22 pm Lie Ryan wrote:
>
> > Python's 'list' is an array of pointers to `PyObject` ('object' in
> > Python) and the resizing algorithm keeps the list size such that
> > "allocated / 2 <= actual <= allocated". When list need to resize, it
> > overallocates the list slightly over 1.125 times than the requested
> > size "(newsize >> 3) + (newsize < 9 ? 3 : 6) + newsize".
> >
> > If you're interested in more precise details (since I do omit some,
> > especially those that seems to be micro-optimization-related), you
> > need to read the source at
> > http://code.python.org/hg/trunk/file/e9d930f8b8ff/Objects/listobject.c
>
> Thanks for the correction Lie. However, I don't understand what is going
> on in the code. I'm not a C programmer, so I'm struggling to read it,
> but as far as I can tell the comment in the code and the code itself
> are not the same.
>
> The code calculates an amount to over-allocate the list:
>
> new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);
>
> Some experiments in Python shows that the right hand expression varies
> like this:
>
> >>> for i in range(30):
> ... print ((i >> 3) + (3 if i < 9 else 6)),
> ...
> 3 3 3 3 3 3 3 3 4 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 9 9 9 9 9 9
Right, I don't understand neither. Since i>>8 <=> i/8, the above code is
finally a (fast, because of bit-level op) version of:
if size < 8:
return 3
else:
return size/8 + (3 if size < 9 else 6),
> But the comment in the code says:
>
> /* This over-allocates proportional to the list size, making room
> * for additional growth. The over-allocation is mild, but is
> * enough to give linear-time amortized behavior over a long
> * sequence of appends() in the presence of a poorly-performing
> * system realloc().
> * The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
> */
>
> which doesn't look anything like the numbers above. I don't understand
> what this growth pattern refers to. What have I misunderstood?
I first thought "growth pattern" is to be interpreted as "how the array size
grows when it is progressively fed with new items", like when feeding a list in
a loop.
But I tried to simulate this, and the size sticks at 3. finally, I think what
is called in source "new_allocated" is not the new array memory size, but the
_difference_. When writing "size = size + new_allocated" instead of "size =
new_allocated", It get a growth pattern of:
0 3 6 9 16 24 33 43 54 66 80 96 114
Which is not exactly what is stated in code, but rather similar...
def grow():
size = 0 ; count = 0
for count in range(100):
if count > size:
size = size + (size >> 3) + (3 if size < 9 else 6)
print size,
Denis
________________________________
vit esse estrany ☣
spir.wikidot.com
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor
