Pop a list from beginning ? and memory saving...

Aahz aahz at pythoncraft.com
Wed Jun 19 22:25:54 CEST 2002


In article <aeqne9$4h1$1 at news.idiom.com>,
James T. Dennis <jadestar at idiom.com> wrote:
>Aahz <aahz at pythoncraft.com> wrote:
>> In article <aep4jb$1q8h$1 at news.idiom.com>,
>> James T. Dennis <jadestar at idiom.com> wrote:
>>>
>>> It might be better to have a hack to the implementation of the
>>> list primitives --- so they defer the shift of remaining elements
>>> until GC.  The head of the list could point at the first none 
>>> deleted item.  Then pop(0) could be implemented in O(1) time and
>>> the garbage collector would eventually come along to do it's 
>>> job.
>>
>> While this might be a worthwhile optimization, it has absolutely nothing
>> to do with GC.  Each time an element were popped off the front, its
>> object would be decreffed and possibly deleted.  GC runs completely
>> independently of individual objects.
>
> Sorry, I was speaking abstractly about garbage collection, I know
> nothing about Python's GC implementation.  Perhaps it would be an 
> opportunity to augment Python's GC.  Some containers (and even 
> some classes) could implement their own compaction routines that 
> could be called by the GC. 

That wouldn't work too well.  It's really only vectors that need
compaction, and it's only Python lists that are mutable vectors.
Python's dict structure already has its own compaction algorithm, and
it's not compatible with GC.

(Dict compaction is based on the proportion of free entries; it's a
simple test, and there's no gain to be made by adding GC on top of it.)

Keep in mind that Python's (CPython's, to be precise; Jython does use GC
because that's what Java provides) base memory management semantics is
built on refcounting.  GC only handles cycles.
-- 
Aahz (aahz at pythoncraft.com)           <*>         http://www.pythoncraft.com/

Project Vote Smart: http://www.vote-smart.org/



More information about the Python-list mailing list