search

Xudong-Huang / generator-rs

rust stackful generator library
Apache License 2.0
286 stars 35 forks source link

Recursive generators #29

Open oersted opened 3 years ago

oersted commented 3 years ago

I would like to ask if this implementation of generators is appropriate to be used recursively.

It is not an uncommon pattern to use recursive generator functions for certain problems. Any algorithm with the shape of a tree/graph search problem could benefit from this pattern for making it lazy (only return more results when the caller calls next()).

Even if we were not calling the same function recursively, it is also a useful pattern to have a deep stack of generator functions, such that a high-level function may pull results from it as needed in a lazy manner. A web API with pagination for example.

From my own research of the source code, it looks like each call to Gn::new_scoped will dynamically allocate a new stack using mmap (for unix), which by default is of 4KB (0x1000 bytes). This means that each recursive call of a generator function will consume quite a lot of memory. Is this correct?

The default size can be reduced, but exceeding the stack causes a hard SIGSEGV and it would be quite inconvenient to tune the stack size for each function so that it is just large enough. I'm also getting failed to alloc sys stack: IoError(Os { code: 12, kind: Other, message: "Cannot allocate memory" }) panics by just recursing 6 times, which seems unreasonable.

Is there a better way of doing this? I have considered passing the Scope object down the stack, but I believe that the yields in deeper function calls would emit at the top level, which is not the behaviour that you would expect from a generator stack.

Since you probably know the ecosystem better. Is there any other generator library more suited to this? Such as genawaiter for example? Or the native Rust generators, which are still unstable?

Thank you in advance. And apologies if this is a bit too abstract to understand. I don't have time right now to give code examples, but feel free to ask questions and I will clarify as best I can.

Xudong-Huang commented 3 years ago

If you are recursively creating new generator instances, it will consume your heap memory very quickly, but the stack memory is not increasing that too much.