D1934: convert: use a collections.deque

indygreg (Gregory Szorc) phabricator at mercurial-scm.org
Mon Jan 22 01:14:39 UTC 2018


indygreg created this revision.
Herald added a subscriber: mercurial-devel.
Herald added a reviewer: hg-reviewers.

REVISION SUMMARY
  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

REPOSITORY
  rHG Mercurial

REVISION DETAIL
  https://phab.mercurial-scm.org/D1934

AFFECTED FILES
  hgext/convert/convcmd.py

CHANGE DETAILS

diff --git a/hgext/convert/convcmd.py b/hgext/convert/convcmd.py
--- a/hgext/convert/convcmd.py
+++ b/hgext/convert/convcmd.py
@@ -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)



To: indygreg, #hg-reviewers
Cc: mercurial-devel


More information about the Mercurial-devel mailing list