--- On Mon, 1/25/10, Mike Klaas <mike.kl...@gmail.com> wrote: > From: Mike Klaas <mike.kl...@gmail.com> > > On Mon, Jan 25, 2010 at 1:22 PM, Steve Howell <showel...@yahoo.com> > wrote: > >> > >> I haven't completely worked out the best strategy > to eventually release > >> the memory taken up by the pointers of the > unreleased elements, but the > >> worst case scenario is that the unused memory only > gets wasted until the > >> time that the list itself gets garbage collected. > > > > FWIW, for a long-running FIFO queue, it's critical to > release some of the > > memory along the way, otherwise the amount of wasted > memory is unbounded. > > > > Good luck :) > > It seems to me that the best way to do this is invert > .append() logic: > leave at most X amount of wasted space at the beginning of > the list, > where X is a constant fraction of the list size.
That's roughly what I intend to do. The problems are not entirely symmetric. For appends, the wasted space exists in the sense that CPython optimistically get extra chunks of memory for future appends, to save CPU at the possible cost of needlessly allocating memory. For pops, the bargain would be that you optimistically defer releasing memory to save CPU cycles in the hope that memory is not scarce. Of course, if you have just popped an element off the list, then you have just made memory less scarce by virtue of removing the list elements themselves. > Whether it is worth adding a extra pointer to the data > stored by a > list is another story. That is definitely a point of contention. It would certainly bloat a program that had millions of empty lists. I think in most real-world programs, though, the amount of memory taken by PyListObjects will always be greatly exceeded by the amount of memory used by the list elements, or even just the pointers to the list elements. It's the difference between the number of elements in a list, O(N), and the number of structures that define a list's state, O(1). _______________________________________________ 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
