Optimising tail recursion

I implemented the solution described by Kelsey in this last commit, and while it does seem to work (it no longer crashes and memory usage seems bounded), it appears to be less than optimal. This is particularly obvious when running the original reference code that triggered the bug, which while it doesn’t crash or cause memory usage to increase rapidly, pauses embarrassingly every 7000 or so iterations and then proceeds. This appears to happen because the solution also causes large numbers of garbage environments to proliferate in the heap, which creates more work for the garbage collector. It ought to perhaps be possible to reuse a heap environment when it appears in a tail recursive call, just as stack environments are reused, but how this can be done is not exactly clear. Perhaps the env instruction can be changed somewhat to make it do this. On a tail recursive call, what we can do is perhaps check if the environment is on the stack or the heap. If the former is true, then we need not do anything different from what we do today. If the environment is on the heap, we can move the required arguments which are on the stack into the heap, clear out the values of the other elements (to CUNBOUND), and then allow the instructions subsequent to the env instruction to take care of filling in the remaining environment values.

This needs some careful consideration.


~ by stormwyrm on 2014-04-05.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: