What does Python fix?

[Alex Martelli]

On Monday 21 January 2002 18:27, François Pinard wrote:
> [Alex Martelli]
>
> > class listshare:
> >     def __init__(self, offset, alist):
> >         self._alist = alist
> >         self._offset = offset
> >     def __getitem__(self, index):
> >         return self._alist[index+offset]
> >     # etc, etc
>
> Clever! :-)

Well, not very, admittedly.  But still, reasonably simple.


> > In which case, you can choose to use the referenced extension (where an
> > object takes, I believe, three "words" -- a type-pointer, car, and
> > cdr).
>
> Plus, surely, a reference count, and the overhead required by the memory
> allocator.  Presumably, Python has its own allocator for small
> structures, and the allocator overhead thus becomes insignificant.

Right, so the size must be at least 4 "words".  I'm not sure about the
space overhead of the Python allocator, either.


> > On the other hand, memory overhead for a very long Python list can be
> > much lower (in the same sense, i.e., just for the structuring part)
> > than an equivalently-long Lisp list, because the Python list is in
> > fact implemented as a contiguous array of single pointers
>
> I got myself into Python two years ago.  Some time before, I worked on
> the prototype of the GNU music project (which, by a strange set of
> circumstances, became the marvelous Lilypond -- this would be a long
> story).  The core team was torn between a Lisp or Scheme implementation,
> C++, and others. I finally wrote the thing in plain portable C.  Knowing
> I would handle many lists, I tried a representation similar to the above,

I.e., contiguously allocated vectors as opposed to actual linked-lists
of some kind?

> feeling a bit deviant, but convinced there were many virtues to this
> approach.  So, it was part of my pleasure, later discovering Python, to
> see that it made the same choices.

I've noticed that at least 9 times out of 10 the right sequence container
in C++ is std::vector as opposed to std::list, std::queue or std::slist 
(from STL).  I guess this must be a common case indeed.

Common Lisp does have vectors/array/however they're named, right?


> > I doubt that saving memory will be the dominating issue in any such
> > "bigger application" -- issues of O(N) vs O(N log N) performance, and
> > so on, would appear to be more likely to dominate, I think.
>
> We should always have an idea on how resources are consumed by
> algorithms. Best is to develop some background culture about how Python
> does things... But yes, we agree!

We seem to be agreeing very verbosely:-).  A further point may be, what if
Python starts doing things differently tomorrow?-)  Many cases where one
would automatically use a list quite recently may be handled with iterators
today (in theory, that should save quite a bit of memory, although I think 
it may still slow things down -- unless it's really a case of saving you 
from thrashing phenomena or thereabouts).


Alex