Skip to content
New issue

Have a 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

Collapse f_and/f_or for better performance? #320

Open
rohanpm opened this issue Feb 25, 2022 · 2 comments · May be fixed by #325
Open

Collapse f_and/f_or for better performance? #320

rohanpm opened this issue Feb 25, 2022 · 2 comments · May be fixed by #325

Comments

@rohanpm
Copy link
Owner

rohanpm commented Feb 25, 2022

Consider the following:

f = f_and(f1, f2)
f = f_and(f, something)
f = f_and(f, other)
f = f_and(f, foo)
f = f_and(f, bar)
# ...

That will create various chained objects (AndOperation under the hood). In practice code might be written in a way such that the chain ends up thousands of items deep.

Consider if it's practical & useful to collapse the objects in this case. e.g. is it possible to arrange it so that, in f_and(a, f_and(b, c)), the outermost f_and could generate an object equally as efficient as f_and(a, b, c) ?
@rohanpm
Copy link
Owner Author

rohanpm commented Feb 27, 2022

I looked into it and don't think there's much that can be done.

  • In the case where futures have already completed by the time f_and is called, 100,000 chained calls already seem to be about as efficient as a single call with 100,000 futures.
  • In the case where futures haven't completed, there doesn't seem to be any reasonable way to avoid needing O(N) frames on the stack where N is the number of futures.

@rohanpm rohanpm closed this as completed Feb 27, 2022
@rohanpm
Copy link
Owner Author

rohanpm commented Mar 8, 2022

Reopened after changing my mind about it. I think it should be possible to do something about this after all.

@rohanpm rohanpm reopened this Mar 8, 2022
rohanpm added a commit that referenced this issue Mar 8, 2022
@rohanpm
Flatten outputs for chained boolean operations where possible
d8a8bc0 
Add special-case handling to flatten the data structure when chaining
multiple AND/OR together; for example, make f_and(f_and(x, y), z)
work approximately in the same way as f_and(x, y, z).

The goal here is to avoid a stack overflow when using a pattern which
can chain a large number of futures. Previously, an overflow could start
to happen if the chain was a few hundred futures deep, since each
future's completion callback would set the result on the next future
which would invoke another completion callback and so on throughout the
chain.

Fixes #320
@rohanpm rohanpm linked a pull request Mar 8, 2022 that will close this issue
Draft
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

Successfully merging a pull request may close this issue.

Flatten outputs for chained boolean operations where possible rohanpm/more-executors
1 participant
@rohanpm