fork()

[Guido van Rossum]

Christian Tismer <tismer at appliedbiometrics.com> writes:

> If we have knowlegde of the internals of every Python structure,
> and if there were no hidden internal references to Python
> objects, then we could quite easily build a non-pessimistic
> GC, without the need to be hardware specific, scan the stack
> and so on.
> You know that I have an (early) Python with no stack.
> Would this help?

I don't see how: the roots you are looking for are all in the frame
objects anyway.  (There are a few variables in the C stack of
eval_code() but they point to objects that are also in the frame's list
of local variables or on the eval stack in the frame.)

[Christian, please don't call eval_code() "the interpreter" -- there
are already two or three other concepts that bear that name: the
interpreter state objects defined in pystate.[ch], the interactive
read-eval-print loop, and the entire Python executable.  We don't need
a fourth one!]

But here's another dumb idea based on the same premise (since this
thread won't die anyway, I might as well join in :-).

The idea is to add mark-and-sweep on top of refcounting, and only
invoke it on relatively rare occasions.  Perl does a mark-and-sweep at
certain moments to destroy cycles; I believe when a thread dies or
when an interpreter state object dies.  Something like this (plus a
way to force it) might be enough for Python, too.

Some hunches:

- Almost all cycles involve a dictionary, in practice (probably also
an instance, but those cycles involving an instance always also
involve a dictionary, since all references from instances go through
dictionaries).  Why does this matter?  Because now I only need to put
a mark bit in dioctionary objects, and I can maintain a list of all
dictionaries instead of a list of all objects, and apply
mark-and-sweep to it, without occurring overhead for all objects.

(You can create a cycle using only lists, but I bet that happens only
for demonstration purposes, as in ``a = []; a.append(a)''.  So I can
live with not freeing such cycles.)

- As roots should suffice the objects referenced by the threadstates
of all the interpreterstates.  (From there you can find all stack
frames, in particular.)  And perhaps a small number of global
variables at the C level.  Maybe we have to mark "freshly created"
dictionaries as live, to allow for C code that creates a dictionary,
then calls other parts of Python that will eventually fill the
dictionary and which might trigger a mark-and-sweep.  But other than
that I doubt that the C stack is needed to find roots.

- We can easily add a "mark" function to the list of function pointers
in the type object.  The mark() for a dictionary returns immediately
if the dictionary is already marked; otherwise, it marks it and then
calls the mark() function for all values in the dictionary.  The
mark() function for other container functions (tuples, lists,
instances, classes, frames, tracebacks, modules, function objects)
simply calls mark() for all objects contained in it.  Non-containers
(e.g. numbers, strings, most extension types) have a null mark()
function.  (I think code objects don't need a mark() function either,
they never contribute cycles -- unless one uses the bytecodehacks! :-)

(Hm, heavily shared containers, especially lists, might be traversed
many time by this algorithm, and that would be expensive if were
large.  Maybe it would pay to also have a mark bit in all lists.)

- The only tricky part is extension modules that might have additional
roots.  For example, _tkinter keeps references to callback functions
alive that might in some circumstances be methods of class instances
that have no other references to keep them alive.  We could invent a
convention whereby an extension (or any!) module can define a
__mark__() function which is called to provide additional roots.

(Extension types that participate in cycles should simply define a
mark() function in their type object.)


Why this compromise instead of "true GC" like Java?  Because one of
Python's main reasons of existence is its good integration with
external C code -- in a glue language, you can't set the rules for
management of all memory!

Then why not Boehm-Weiser?  It's been tried, and with disappointing
results.

May this thread spurn some code,

--Guido van Rossum (home page: http://www.python.org/~guido/)