[Python-Dev] Re: Proper tail recursion (original) (raw)

Chris King colanderman at gmail.com
Fri Jul 16 20:11:24 CEST 2004

On Fri, 16 Jul 2004 10:45:38 -0700, Josiah Carlson <jcarlson at uci.edu> wrote:

On Fri, 16 Jul 2004 09:23:15 -0400, Chris King <colanderman at gmail.com> wrote: > I thought of doing RLE tracebacks, but compression fails in the case > of cooperative recursive calls. I think perhaps along with the > sys.setrecursionlimit(None) option you suggest, developers should be > allowed to turn recursive tracebacks off entirely in the case of > cooperative recursive calls. They already can by writing your own sys.excepthook callable. I think the following would be sufficient for removing tracebacks... def myexcepthook(type, value, traceback): print >>sys.stderr, "Exception:", type.name, ":", value

I wasn't clear enough -- by "turn off" I meant "throw out"; redefining sys.excepthook will still store them (and thus take up memory).

The problem isn't whether or not tracebacks should be cut -- it's whether huge lists of recursively entered stack frames should be kept around. If they are kept (a necessity for a proper traceback), optimizing tail calls is almost worthless; indeed, it would be entirely worthless in Stackless, which already allocates frames from the heap.

IMO it shouldn't be only about tail-call optimizations. Andrew Koenig suggested that frames be allocated from the heap, which if it is possible (is there anything that gets executed directly by the processor so we have to worry about processors supporting NX?), seems to remove the C stack limit.

The stack limit isn't the problem (it's very large, as far as I can tell). The memory used by holding onto stack frames that have no use other than in tracebacks is the problem.

In the case of tail-calls, more optimizations could be done (optionally), to remove the overhead on tail calls (also removing information containing tracebacks), but the user should be warned that while it would reduce memory usage, all they get from the traceback are lines are like so: recursive tail call frames removed as requested

This is exactly what the current patch does (minus the warning message): it removes the memory overhead by tossing out extraneous stack frames, at the cost of the availability of proper traceback information. Adding a warning would be trivial.

More information about the Python-Dev mailing list