id	summary	reporter	owner	description	type	status	component	version	severity	resolution	keywords	cc	stage	has_patch	needs_docs	needs_tests	needs_better_patch	easy	ui_ux
24366	Improve migration dependency graph speed	Markus Holtermann	Marten Kenbeek	"With a bout 750 migration files and a total of about 1250 dependency definitions I end up with the following cProfile stats when calling `executor.migrate_plan(targets)` in the migrate command:

{{{
   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000  929.770  929.770 <string>:1(<module>)
       38    0.001    0.000  229.709    6.045 __init__.py:41(__init__)
 63854649  100.666    0.000  101.193    0.000 __init__.py:58(__setitem__)
    16077    0.009    0.000    0.009    0.000 __init__.py:83(__iter__)
       38    0.000    0.000    0.000    0.000 _collections_abc.py:437(keys)
       38    0.000    0.000    0.000    0.000 _collections_abc.py:462(__init__)
    16077    0.007    0.000    0.016    0.000 _collections_abc.py:481(__iter__)
       38  103.342    2.720  229.708    6.045 _collections_abc.py:581(update)
       76    0.000    0.000    0.000    0.000 _weakrefset.py:70(__contains__)
       38    0.000    0.000    0.001    0.000 abc.py:178(__instancecheck__)
       38    0.001    0.000  229.710    6.045 datastructures.py:13(__init__)
 63854687   25.172    0.000   25.172    0.000 datastructures.py:14(<genexpr>)
       38    0.000    0.000    0.001    0.000 datastructures.py:28(__iter__)
        1    0.051    0.051  929.770  929.770 executor.py:23(migration_plan)
       12    0.000    0.000    0.000    0.000 executor.py:49(<genexpr>)
       38    0.350    0.009    0.504    0.013 graph.py:109(ensure_not_cyclic)
       38  251.357    6.615  929.097   24.450 graph.py:129(dfs)
       38    0.622    0.016  929.719   24.466 graph.py:58(forwards_plan)
 63909407  102.207    0.000  141.411    0.000 graph.py:67(<lambda>)
        1    0.000    0.000  929.770  929.770 {built-in method exec}
       38    0.000    0.000    0.000    0.000 {built-in method hasattr}
       38    0.000    0.000    0.001    0.000 {built-in method isinstance}
       38    0.000    0.000    0.000    0.000 {built-in method iter}
      114    0.000    0.000    0.000    0.000 {built-in method len}
    16077    0.527    0.000    0.527    0.000 {built-in method proxy}
 63854661  259.600    0.000  259.600    0.000 {built-in method sorted}
      408    0.000    0.000    0.000    0.000 {method 'add' of 'set' objects}
       38    0.000    0.000    0.000    0.000 {method 'append' of 'collections.deque' objects}
    26476    0.006    0.000    0.006    0.000 {method 'append' of 'list' objects}
 63854611   10.834    0.000   10.834    0.000 {method 'appendleft' of 'collections.deque' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
 63854611   26.316    0.000   26.316    0.000 {method 'extendleft' of 'collections.deque' objects}
 63909419   39.204    0.000   39.204    0.000 {method 'get' of 'dict' objects}
       38    0.000    0.000    0.000    0.000 {method 'items' of 'dict' objects}
       38    0.000    0.000    0.000    0.000 {method 'keys' of 'dict' objects}
    28690    0.010    0.000    0.010    0.000 {method 'pop' of 'list' objects}
     2622    0.001    0.000    0.001    0.000 {method 'pop' of 'set' objects}
 63854611    9.471    0.000    9.471    0.000 {method 'popleft' of 'collections.deque' objects}
    26068    0.014    0.000    0.014    0.000 {method 'remove' of 'set' objects}
}}}

I think this applies to 1.7+, though I only tested it on the current master"	Cleanup/optimization	closed	Migrations	dev	Normal	fixed		Markus Holtermann Marten Kenbeek	Ready for checkin	1	0	0	0	0	0