[jira] [Commented] (AIRFLOW-3518) Toposort is very slow

["ASF GitHub Bot (JIRA)" <ji...@apache.org>]

    [ https://issues.apache.org/jira/browse/AIRFLOW-3518?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16721536#comment-16721536 ] 

ASF GitHub Bot commented on AIRFLOW-3518:
-----------------------------------------

NielsZeilemaker opened a new pull request #4322: [AIRFLOW-3518] Performance fixes for topological_sort
URL: https://github.com/apache/incubator-airflow/pull/4322
 
 
   For larger DAGs topological_sort was found to be very inefficient. Made
   some small changes to the code to improve the datastructures used in the
   method.
   
   Make sure you have checked _all_ steps below.
   
   ### Jira
   
   - [X] My PR addresses the following [Airflow Jira](https://issues.apache.org/jira/browse/AIRFLOW/) issues and references them in the PR title. For example, "\[AIRFLOW-XXX\] My Airflow PR"
     - https://issues.apache.org/jira/browse/AIRFLOW-3518
     - In case you are fixing a typo in the documentation you can prepend your commit with \[AIRFLOW-XXX\], code changes always need a Jira issue.
   
   ### Description
   
   - [X] Here are some details about my PR, including screenshots of any UI changes:
   While running a larger DAG, topological_sort was found to be very slow. This fixup improves the performance on my local machine from ~5-10 seconds to 0.01s.
   Moreover, i've modified the __eq__ operators to have a shortcut for dag_id/task_id. This should improve all other cases where equality is used.
   
   ### Tests
   
   - [X] My PR adds the following unit tests __OR__ does not need testing for this extremely good reason:
   No tests, as I would expect topological_sort to be covered already.
   
   ### Commits
   
   - [X] My commits all reference Jira issues in their subject lines, and I have squashed multiple commits if they address the same issue. In addition, my commits follow the guidelines from "[How to write a good git commit message](http://chris.beams.io/posts/git-commit/)":
     1. Subject is separated from body by a blank line
     1. Subject is limited to 50 characters (not including Jira issue reference)
     1. Subject does not end with a period
     1. Subject uses the imperative mood ("add", not "adding")
     1. Body wraps at 72 characters
     1. Body explains "what" and "why", not "how"
   
   ### Documentation
   
   - [ ] In case of new functionality, my PR adds documentation that describes how to use it.
     - When adding new operators/hooks/sensors, the autoclass documentation generation needs to be added.
     - All the public functions and the classes in the PR contain docstrings that explain what it does
   
   ### Code Quality
   
   - [X] Passes `flake8`
   

----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on GitHub and use the
URL above to go to the specific comment.
 
For queries about this service, please contact Infrastructure at:
users@infra.apache.org


> Toposort is very slow
> ---------------------
>
>                 Key: AIRFLOW-3518
>                 URL: https://issues.apache.org/jira/browse/AIRFLOW-3518
>             Project: Apache Airflow
>          Issue Type: New Feature
>          Components: scheduler
>            Reporter: Niels Zeilemaker
>            Assignee: Niels Zeilemaker
>            Priority: Major
>
> At a client we've discovered that for larger DAGs toposort is very slow.



--
This message was sent by Atlassian JIRA
(v7.6.3#76005)