Garbage collection

[skip at pobox.com]

    Tom> True, but why does Python hang on to the memory at all?  As I
    Tom> understand it, it's keeping a big lump of memory on the int free
    Tom> list in order to make future allocations of large numbers of
    Tom> integers faster.  If that memory is about to be paged out, then
    Tom> surely future allocations of integers will be *slower*, as the
    Tom> system will have to:

    Tom> 1) page out something to make room for the new integers
    Tom> 2) page in the relevant chunk of the int free list
    Tom> 3) zero all of this memory and do any other formatting required by
    Tom>    Python 

If your program's behavior is:

    * allocate a list of 1e7 ints
    * delete that list

how does the Python interpreter know your next bit of execution won't be to
repeat the allocation?  In addition, checking to see that an arena in the
free list can be freed is itself not a free operation.  From the comments at
the top of intobject.c:

   free_list is a singly-linked list of available PyIntObjects, linked
   via abuse of their ob_type members.

Each time an int is allocated, the free list is checked to see if it's got a
spare object lying about sloughin off.  If so, it is plucked from the list
and reinitialized appropriately.  If not, a new block of memory sufficient
to hold about 250 ints is grabbed via a call to malloc, which *might* have
to grab more memory from the OS.  Once that block is allocated, it's strung
together into a free list via the above ob_type slot abuse.  Then the 250 or
so items are handed out one-by-one as needed and stitched back into the free
list as they are freed.

Now consider how difficult it is to decide if that block of 250 or so
objects is all unused so that we can free() it.  We have to walk through the
list and check to see if that chunk is in the free list.  That's complicated
by the fact that the ref count fields aren't initialized to zero until a
particular chunk is first used as an allocated int object and would have to
be to support this block free operation (=> more cost up front).  Still,
assume we can semi-efficiently determine that a particular block is composed
of all freed int-object-sized chunks.  We will then unstitch it from the
chain of blocks and call free() to free it.  Still, we are left with the
behavior of the operating system's malloc/free implementation.  It probably
won't sbrk() the block back to the OS, so after all that work your process
still holds the memory.

Okay, so malloc/free won't work.  We could boost the block size up to the
size of a page and use mmap() to map a page into memory.  I suspect that
would become still more complicated to implement, and the block size being
probably about eight times larger than the current block size would incur
even more cost to determine if it was full of nothing but freed objects.

    Tom> If Python freed (most of) the memory when it had finished with it,
    Tom> then all the system would have to do is:

That's the rub.  Figuring out when it is truly "finished" with the memory.

    Tom> Surely Python should free the memory if it's not been used for a
    Tom> certain amount of time (say a few seconds), as allocation times are
    Tom> not going to be the limiting factor if it's gone unused for that
    Tom> long.

This is generally the point in such discussions where I respond with
something like, "patches cheerfully accepted". ;-) If you're interested in
digging into this, have a look at the free list implementation in
Objects/intobject.c.  It might make for a good Google Summer of Code
project:

    http://code.google.com/soc/psf/open.html
    http://code.google.com/soc/psf/about.html

but I'm not the guy you want mentoring such a project.  There are a lot of
people who understand the ins and outs of Python's memory allocation code
much better than I do.

    Tom> I've also tested similar situations on Python under Windows XP, and
    Tom> it shows the same behaviour, so I think this is a Python and/or
    Tom> GCC/libc issue, rather than an OS issue (assuming Python for linux
    Tom> and Python for windows are both compiled with GCC).

Sure, my apologies.  The malloc/free implementation is strictly speaking not
part of the operating system.  I tend to mentally lump them together because
it's uncommon for people to use a malloc/free implementation different than
the one delivered with their computer.

Skip