473,703 Members | 2,420 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Garbage collection of recursive inner function

Hi,

I encountered garbage collection behaviour that I didn't expect when
using a recursive function inside another function: the definition of
the inner function seems to contain a circular reference, which means
it is only collected by the mark-and-sweep collector, not by reference
counting. Here is some code that demonstrates it:

===
def outer():

def inner(n):
if n == 0:
return 1
else:
return n * inner(n - 1)

return 42

import gc
gc.set_debug(gc .DEBUG_SAVEALL)
print outer()
gc.collect()
print gc.garbage
===

Output when executed:
$ python internal_func_g c.py
42
[<cell at 0xb7dec3ec: function object at 0xb7dbd3ac>, (<cell at
0xb7dec3ec: function object at 0xb7dbd3ac>,), <function inner at
0xb7dbd3ac>]

Note that the inner function is not called at all, it is only defined.
If the inner function is moved outside the scope of the outer
function, gc.garbage will be empty. If the inner function is inside
but not recursive, gc.garbage will also be empty. If the outer
function is called twice, there will be twice as many objects in
gc.garbage.

Is this expected behaviour? Collecting an object when its refcount
reaches zero is preferable to collecting it with mark-and-sweep, but
maybe there is a reason that a circular reference must exist in this
situation. I want to check that first so I don't report a bug for
something that is not a bug.

Bye,
Maarten
Aug 4 '08 #1
3 4229
fr************* ***@gmail.com schrieb:
Hi,

I encountered garbage collection behaviour that I didn't expect when
using a recursive function inside another function: the definition of
the inner function seems to contain a circular reference, which means
it is only collected by the mark-and-sweep collector, not by reference
counting. Here is some code that demonstrates it:

===
def outer():

def inner(n):
if n == 0:
return 1
else:
return n * inner(n - 1)

return 42

import gc
gc.set_debug(gc .DEBUG_SAVEALL)
print outer()
gc.collect()
print gc.garbage
===

Output when executed:
$ python internal_func_g c.py
42
[<cell at 0xb7dec3ec: function object at 0xb7dbd3ac>, (<cell at
0xb7dec3ec: function object at 0xb7dbd3ac>,), <function inner at
0xb7dbd3ac>]

Note that the inner function is not called at all, it is only defined.
If the inner function is moved outside the scope of the outer
function, gc.garbage will be empty. If the inner function is inside
but not recursive, gc.garbage will also be empty. If the outer
function is called twice, there will be twice as many objects in
gc.garbage.

Is this expected behaviour? Collecting an object when its refcount
reaches zero is preferable to collecting it with mark-and-sweep, but
maybe there is a reason that a circular reference must exist in this
situation. I want to check that first so I don't report a bug for
something that is not a bug.
The reference comes from the closure of inner. And inner is part of the
closure, so there is a circular reference.

I don't see a way to overcome this - consider the following code:

def outer():

def inner():
inner()

if random.random() .5:
return inner
How is the GC/refcounting to know if it can create a reference or not?

Diez
Aug 4 '08 #2


fr************* ***@gmail.com wrote:
I encountered garbage collection behaviour that I didn't expect when
using a recursive function inside another function:
To understand this, it helps to realize that Python functions are not,
in themselves, recursive. Recursiveness at any time is a property of a
function in an environment, which latter can change. More specifically,
a function call is recursive if the expression indicating the function
to call happens to indicate the function containing the call at the time
of evaluation just before the evaluation of the argument expressions.
See examples below.
the definition of
the inner function seems to contain a circular reference, which means
it is only collected by the mark-and-sweep collector, not by reference
counting. Here is some code that demonstrates it:
The inner function is part of a circular reference that is originally
part of the outer function, but which may survive the call to outer
def outer():
def inner(n):
if n == 0:
return 1
else:
return n * inner(n - 1)
inner1 = inner
def inner(n): return 1
# original inner still exists but is no longer 'recursive'

def out2():
def inner1(n): return 1
def inner(n):
if n: return n*inner1(n-1)
else: return 1
# inner is obviously not recursive
inner1 = inner
# but now it is
If the inner function is moved outside the scope of the outer
function, gc.garbage will be empty.
With 'inner' in the global namespace, no (circular) closure is needed to
keep it alive past the outer lifetime.
If the inner function is inside
but not recursive, gc.garbage will also be empty.
Not necessarily so. What matters is that inner has a non-local
reference to outer's local name 'inner'. Try
def inner(): return inner
which contains no calls, recursive or otherwise.
If the outer function is called twice,
there will be twice as many objects in gc.garbage.
And so on, until gc happens.
Is this expected behaviour? Collecting an object when its refcount
reaches zero is preferable to collecting it with mark-and-sweep, but
Adding 'inner = None' at the end of an outer function will break the
cycle and with CPython, all will be collected when outer exits.
Jython and IronPython do not, I believe, do reference counting.

Adding 'del inner' gives
SyntaxError: cannot delete variable 'inner' referenced in inner scope.
maybe there is a reason that a circular reference must exist in this
situation. I want to check that first so I don't report a bug for
something that is not a bug.
Not a bug, but an educational example and possibly useful to someone
running on CPython with gc turned off and making lots of calls to
functions with inner functions with recursive references. I learned a
bit answering this.

Terry Jan Reedy

Aug 5 '08 #3
On Aug 5, 5:23 am, Terry Reedy <tjre...@udel.e duwrote:
To understand this, it helps to realize that Python functions are not,
in themselves, recursive. Recursiveness at any time is a property of a
function in an environment, which latter can change. More specifically,
a function call is recursive if the expression indicating the function
to call happens to indicate the function containing the call at the time
of evaluation just before the evaluation of the argument expressions.
I didn't realize that the function looks up itself in the outer
environment when it makes the recursive call, instead of at definition
time.
Adding 'inner = None' at the end of an outer function will break the
cycle and with CPython, all will be collected when outer exits.
I think I'll use that for inner functions that do need to access the
outer environment, but do not need to live longer than the call to the
outer function.
Not a bug, but an educational example and possibly useful to someone
running on CPython with gc turned off and making lots of calls to
functions with inner functions with recursive references. I learned a
bit answering this.
That describes our application: in some cases, we have several
gigabytes of small objects, in which case mark-and-sweep garbage
collection takes quite a long time, especially if some of the objects
have been pushed into the swap. I have broken all cycles in our own
data structures a while ago, but got an unexpected memory leak because
of these cyclic references from inner functions.

Thanks for your clear explanation!

Bye,
Maarten
Aug 5 '08 #4

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

2
4971
by: Peter Kwan | last post by:
Hi, I believe I have discovered a bug in Python 2.3. Could anyone suggest a get around? When I tested my existing Python code with the newly released Python 2.3, I get the following warning: FutureWarning: hex/oct constants > sys.maxint will return positive values in Python 2.4 and up It is because I used some constants such as 0x80ff3366, so I change it to 0x80ff3366L, hoping to get rid of the warning.
2
1991
by: James S | last post by:
Hi, Basically I've been fighting with this code for a few days now and can't seem to work around this problem. Included is the output, the program I use to get this error and the source code for my wrapper. This is acually part of the project, libxmlconf on sourceforge. The newest working version isn't there yet, and cvs is lagged by 6 hours or so. So if you think you want to have a try at this I can tgz the source for you. My...
55
4160
by: jacob navia | last post by:
Tired of chasing free(tm) bugs? Get serious about C and use lcc-win32. The garbage collector designed by Boehm is the best of its class. Very simple: #define malloc GC_malloc #define free(a) (a=NULL) NICE isn't it?
4
12333
by: Chris | last post by:
Hi, I think I'm having some problems here with garbage collection. Currently, I have the following code: public struct Event { public int timestamp;
28
3174
by: Goalie_Ca | last post by:
I have been reading (or at least googling) about the potential addition of optional garbage collection to C++0x. There are numerous myths and whatnot with very little detailed information. Will this work be library based or language based and will it be based on that of managed C++? Then of course there are the finer technical questions raised (especially due to pointer abuse). Is a GC for C++ just a pipe dream or is there a lot of work...
3
2161
by: Fab | last post by:
Hi ! Maybe somebody has used a GC - I think to Hans Boehm's one, but other, if any, are welcome -. I need to use a GC in order to program an interpreter for a functional language. Memory handling would be otherwise difficult too much. I read that the use of Boehms'GC - well fit for C - was generally complicated enough and particularly for STL. I confess I considered to switch to Java for this reason... But what about SGI hash...
56
3693
by: Johnny E. Jensen | last post by:
Hellow I'am not sure what to think about the Garbage Collector. I have a Class OutlookObject, It have two private variables. Private Microsoft.Office.Interop.Outlook.Application _Application = null; Private Microsoft.Office.Interop.Outlook.NameSpace _Namespace = null; The Constructor: public OutlookObject()
2
2296
by: wgarner | last post by:
I am trying to implement a two-dimensional recursive formula, g(x,y). It is sort of like multiplication. g(x,y) = 0 if either x or y is 0. g(1, y) = y and g(x, 1) = x. Those are the base cases. In general, though, g(x, y) = h, where h is another function which I have already written a script for. (The XOR refers to binary addition and can be implemented via " ^ ", so that is all right.)
158
7812
by: pushpakulkar | last post by:
Hi all, Is garbage collection possible in C++. It doesn't come as part of language support. Is there any specific reason for the same due to the way the language is designed. Or it is discouraged due to some specific reason. If someone can give inputs on the same, it will be of great help. Regards, Pushpa
0
8740
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, weíll explore What is ONU, What Is Router, ONU & Routerís main usage, and What is the difference between ONU and Router. Letís take a closer look ! Part I. Meaning of...
0
9236
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
1
8988
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
8946
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
0
4415
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
0
4672
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
3108
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
2
2411
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
3
2044
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.