[Tutor] python list, right! but concretely?

[Lie Ryan]

On 05/02/10 15:49, spir ☣ wrote:
> Hello,
> 
> Is there anywhere some introduction material to the implementation of python lists
> (or to fully dynamic and flexible sequences, in general)?


> More precisely, I'd like to know what kind of base data-structure is used
> (linked list, dynamic array, something else -- and in case of array,
how is
> resizing computed). Also, how is "generics" (element are of free type, and
> even heterogeneous) managed?

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

> Denis
> 
> PS: The reason is I'm trying to understand better the underlying layers of
> magic facilities we use everyday. Starting from about no computer science
> knowledge. I have a working implementation of linked lists in primitive
> langguages ;-) (namely C & Pascal), but rather complicated to my taste;
> and I'm probably overlooking commonly known and used tricks that could
> make the algorithm simpler or more efficient.

Real life implementation is always hairy, especially as the programmer
cut corners to drench some speed benefit and include many error
checkings. Today is the first time I actually looked at list's
implementation, now I know why people hated C, for every line of real
code, there's three or four lines of error checking code, e.g. to ensure
malloc successfully allocated enough memory or that index access is in
range.