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

Speed up dependency checks for large numbers of outputs #3255

Closed
trwhitcomb opened this issue Jul 29, 2019 · 2 comments · Fixed by #3351
Closed

Speed up dependency checks for large numbers of outputs #3255

trwhitcomb opened this issue Jul 29, 2019 · 2 comments · Fixed by #3351
Assignees
@trwhitcomb
Labels
bug Something is wrong :( efficiency For notable efficiency improvements
Milestone
cylc-8.0a1

Comments

@trwhitcomb
Copy link
Collaborator

We ran into a case where suites were taking a very long time to validate. This was covered in #1776 and follow on tickets, but didn't quite solve the problem. We tracked the behavior down to an O(N**2) operation in the number of task outputs.

Steps to reproduce: Have a very large number of task outputs (~1000)? in the graph that will be loaded.

Our solution was to replace a list with a set in the taskdef initialization that allowed checking for membership to be done in O(1) time instead of O(N) time (PR to follow)
@trwhitcomb trwhitcomb added the bug Something is wrong :( label Jul 29, 2019
@hjoliver
Copy link
Member

Hi @trwhitcomb - that's great news, well done! Looking forward to the PR...

@trwhitcomb trwhitcomb mentioned this issue Jul 30, 2019
Open
trwhitcomb pushed a commit to trwhitcomb/cylc that referenced this issue Jul 30, 2019
Replace O(N) lookup with O(1) for task outputs.
339e2b4 
This speeds up suite validation significantly for tasks with
large numbers of outputs.  The list used required an O(N)
check for membership which, when combined with being run for
each output resulted in O(N**2) complexity.

Using the builtin set should bypass any deprecated libraries in
Python 2.

Closes cylc#3255
@trwhitcomb trwhitcomb mentioned this issue Jul 30, 2019
Merged
6 tasks
@trwhitcomb
Copy link
Collaborator Author

A few notes:

  1. (I found this while backporting this to our 6.11.4 install (I know)) - if the objects placed into a set are not hashable (as they were back then, with taskdef outputs as custom Python objects), even the set wasn't enough to avoid the O(N) test for membership. However, this went away once I defined a custom __hash__ function for the taskdef output object. In v7, these things are just tuples (IIRC) so no special treatment is necessary beyond the changes in this PR.

  2. The symptoms that sent us looking for this were exactly the behavior outlined in suite unresponsive while reload takes a long time #2306 - the first complaints is that suites were "unresponsive on startup/restart" and would not respond to any commands. We were able to isolate this to just the validate command taking forever, which led to identification of the problem. Hat tip to @alpacaxander for his debugging work.

  3. This addresses the underlying root cause of the behavior in suite unresponsive while reload takes a long time #2306, I would vote not to close that other ticket as hitting these large, expensive-to-validate suites shouldn't cause the suite server to go numb to the outside world.

@matthewrmshin matthewrmshin added this to the soon milestone Aug 1, 2019
matthewrmshin pushed a commit to matthewrmshin/cylc-flow that referenced this issue Aug 2, 2019
@matthewrmshin
Replace O(N) lookup with O(1) for task outputs.
7fa2300 
This speeds up suite validation significantly for tasks with
large numbers of outputs.  The list used required an O(N)
check for membership which, when combined with being run for
each output resulted in O(N**2) complexity.

Using the builtin set should bypass any deprecated libraries in
Python 2.

Closes cylc#3255
trwhitcomb pushed a commit to trwhitcomb/cylc that referenced this issue Aug 2, 2019
Replace O(N) lookup with O(1) for task outputs.
17fe225 
This speeds up suite validation significantly for tasks with
large numbers of outputs.  The list used required an O(N)
check for membership which, when combined with being run for
each output resulted in O(N**2) complexity.

Using the builtin set should bypass any deprecated libraries in
Python 2.

Closes cylc#3255
@trwhitcomb trwhitcomb mentioned this issue Aug 2, 2019
Closed
6 tasks
sadielbartholomew pushed a commit to sadielbartholomew/cylc-flow that referenced this issue Aug 8, 2019
@sadielbartholomew
Replace O(N) lookup with O(1) for task outputs.
3b74694 
This speeds up suite validation significantly for tasks with
large numbers of outputs.  The list used required an O(N)
check for membership which, when combined with being run for
each output resulted in O(N**2) complexity.

Using the builtin set should bypass any deprecated libraries in
Python 2.

Closes cylc#3255
@matthewrmshin matthewrmshin modified the milestones: soon, cylc-8.0a1 Aug 28, 2019
@matthewrmshin matthewrmshin added the efficiency For notable efficiency improvements label Aug 28, 2019
matthewrmshin pushed a commit to matthewrmshin/cylc-flow that referenced this issue Sep 6, 2019
@matthewrmshin
Replace O(N) lookup with O(1) for task outputs.
5a1aaf4 
This speeds up suite validation significantly for tasks with
large numbers of outputs.  The list used required an O(N)
check for membership which, when combined with being run for
each output resulted in O(N**2) complexity.

Using the builtin set should bypass any deprecated libraries in
Python 2.

Closes cylc#3255
@matthewrmshin matthewrmshin mentioned this issue Sep 6, 2019
Merged
6 tasks
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@trwhitcomb trwhitcomb

Labels
bug Something is wrong :( efficiency For notable efficiency improvements
Projects
None yet
Milestone
cylc-8.0a1
3 participants
@trwhitcomb @matthewrmshin @hjoliver