8000 Recursive generators · Issue #29 · Xudong-Huang/generator-rs · GitHub
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content

Recursive generators #29

New issue

Have a ADD3 question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Open
oersted opened this issue Jan 27, 2021 · 1 comment
Open

Recursive generators #29

oersted opened this issue Jan 27, 2021 · 1 comment

Comments

@oersted
Copy link
oersted commented Jan 27, 2021 •
edited
Loading

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
Copy link
Owner

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@oersted @Xudong-Huang
0