# HG changeset patch
# User Gregory Szorc <gregory.szorc@gmail.com>
# Date 1516583491 28800
# Node ID eefabd9ed3e1c8ed8ea023a0a76a76335185e2b3
# Parent  128dd940bedc36cc7d43e86604e5e2077f0fdb42
convert: use a collections.deque

This function was doing a list.pop(0) on a list whose length
was the number of revisions to convert. Popping an early element
from long lists is not an efficient operation.

collections.deque supports efficient inserts and pops at both
ends. So we switch to that data structure.

When converting the mozilla-unified repository, which has 445,748
revisions, this change makes the "sorting..." step of
`hg convert --sourcesort` significantly faster:

before: ~59.2s
after:   ~1.3s

Differential Revision: https://phab.mercurial-scm.org/D1934

diff -r 128dd940bedc -r eefabd9ed3e1 hgext/convert/convcmd.py
--- a/hgext/convert/convcmd.py	Sat Jan 20 23:21:59 2018 -0800
+++ b/hgext/convert/convcmd.py	Sun Jan 21 17:11:31 2018 -0800
@@ -6,6 +6,7 @@
 # GNU General Public License version 2 or any later version.
 from __future__ import absolute_import
 
+import collections
 import os
 import shlex
 import shutil
@@ -290,13 +291,13 @@
             revisions without parents. 'parents' must be a mapping of revision
             identifier to its parents ones.
             """
-            visit = sorted(parents)
+            visit = collections.deque(sorted(parents))
             seen = set()
             children = {}
             roots = []
 
             while visit:
-                n = visit.pop(0)
+                n = visit.popleft()
                 if n in seen:
                     continue
                 seen.add(n)