What does Python fix?
aleax at aleax.it
Mon Jan 21 20:45:27 CET 2002
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).
More information about the Python-list