Merge pull request #3536 from Zweedeend/ticket_23837

Fixes #23837: Replace list with deque in migration-planner for improved performance.

1 files changed, 10 insertions, 7 deletions

diff --git a/django/db/migrations/graph.py b/django/db/migrations/graph.py
index b454d17f35..a2c14f2ba6 100644
--- a/django/db/migrations/graph.py
+++ b/django/db/migrations/graph.py
@@ -1,4 +1,5 @@
 from __future__ import unicode_literals
+from collections import deque
 
 from django.db.migrations.state import ProjectState
 from django.utils.datastructures import OrderedSet
@@ -100,26 +101,28 @@ class MigrationGraph(object):
 
     def dfs(self, start, get_children):
         """
-        Dynamic programming based depth first search, for finding dependencies.
+        Iterative depth first search, for finding dependencies.
         """
-        visited = []
+        visited = deque()
         visited.append(start)
         path = [start]
-        stack = sorted(get_children(start))
+        stack = deque(sorted(get_children(start)))
         while stack:
-            node = stack.pop(0)
+            node = stack.popleft()
 
             if node in path:
                 raise CircularDependencyError()
             path.append(node)
 
-            visited.insert(0, node)
-            children = sorted(get_children(node))
+            visited.appendleft(node)
+            children = sorted(get_children(node), reverse=True)
+            # reverse sorting is needed because prepending using deque.extendleft
+            # also effectively reverses values
 
             if path[-1] == node:
                 path.pop()
 
-            stack = children + stack
+            stack.extendleft(children)
 
         return list(OrderedSet(visited))