Re: Creating a lua extension from a recursive C function

[Emmanuel Oga <emmanueloga@...>]

On Sun, May 8, 2011 at 1:13 AM, Sam Roberts <vieuxtech@gmail.com> wrote:
> On Sat, May 7, 2011 at 4:58 PM, Emmanuel Oga <emmanueloga@gmail.com> wrote:
>> This version though, like yours, just keeps making the stack grow with
>> each recursion.
>
> Your question was confusing, it sounded like you were concerned about
> the lua stack, but its the C stack you are concerned with.

Actually, it is the other way around: I'm worried about the lua stack.

>> About the stack, is there a hard limit on its size or can I grow it
>> until there are no longer any available system memory?
>
> C stack size is large, but limited, and hard to test how close to the
> end of it you are, at least portably.

Exactly, I'm not that worried about the C stack. I'm pretty sure the
stack won't blow up from walking my file system recursively.

The thing is I'm making the lua stack grow as I recurse. Imagine the
following situation:

long long n = 0;
static inline int l_tree(lua_State *L) {
  lua_newtable();
  printf("%d\n", ++n);
  l_tree();
};

static const struct luaL_Reg mwalker [] = {
  {"tree", l_tree},
  {NULL, NULL} /* sentinel */
};

int luaopen_mwalker(lua_State *L) {
  luaL_register(L, "mwalker", mwalker);
  return 1;
}

The question is, what will happen first when you call the tree func? C
stack overflow or lua stack overflow? I can answer that now... I tried
it :-).

For luajit, the lua stack dies when it reaches about 2**16 tables in
it (65485 precisely). For lua, in the other hand, the program just
halts at the iteration 876 without any error, and I need to kill it
with Ctrl+C (weird).

I'm guessing that's a hard limit (an inconvenient one) of my compiled
lua interpreter. Since the lua stack seems to be managed with
allocated memory, I'm not sure why it is limited like that and not by
memory constraints.

> You can trivially (though tediously) turn your recursive code into
> iterative code. Find all the local variables in fillTree(), and move
> them into a struct. For every current call to fillTree(),instead
> malloc() a new struct, push it onto a stack of the structs, and store
> your local variables into it so you can pop them later, and continue
> looping. You are essentially building your own stack in the heap.
> Malloc failure is detectable by your code, so you can recover in
> whatever sense you think is graceful.
>
> If you system allows, you'd be better off binding opendir()/readdir()
> into lua, and writing the whole thing in lua (or using luaposix of
> luafilesystem).
>
> Cheers,
> Sam
>
>