--- On Tue, 1/26/10, Guido van Rossum <gu...@python.org> wrote: > From: Guido van Rossum <gu...@python.org> > Subject: Re: [Python-Dev] patch to make list.pop(0) work in O(1) time > To: "Steve Howell" <showel...@yahoo.com> > Cc: "Nick Coghlan" <ncogh...@gmail.com>, python-dev@python.org > Date: Tuesday, January 26, 2010, 12:57 PM > On Tue, Jan 26, 2010 at 12:46 PM, > Steve Howell <showel...@yahoo.com> > wrote: > > It seems to me that the goal of keeping lists > super-compact from a memory standpoint is contradicted by > the code in list_resize that optimistically preallocates > extra memory on appends. > > Ah, but that applies for *large* lists. Adding 8 bytes to > each list > object applies to *all* lists. I betcha that many programs > use many > tiny lists. >
I think that some of the large programs that you mention with many tiny lists have some subset of lists still in memory only due to the fact that they cannot be garbage collected due to dangling references. One of the ways to eliminate dangling references is to aggressively delete objects after you are done processing them. Right now the Python programmer looking to aggressively delete elements from the top of a list has to consider the tradeoff that the operation takes O(N) time and would possibly churn his memory caches with the O(N) memmove operation. In some cases, the Python programmer would only have himself to blame for not using a deque in the first place. But maybe he's a maintenance programmer, so it's not his fault, and maybe the code he inherits uses lists in a pervasive way that makes it hard to swap in deque after the fact. What advice do you give him? Of course, this scenario is mostly speculative. A concrete example of a large Python program that keeps lots of tiny lists around would probably shed more light on the matter. _______________________________________________ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
