Patchwork D1934: convert: use a collections.deque

login
register
mail settings
Submitter phabricator
Date Jan. 22, 2018, 1:14 a.m.
Message ID <differential-rev-PHID-DREV-dj7qnxrfrfujpfuhjlwd-req@phab.mercurial-scm.org>
Download mbox | patch
Permalink /patch/27027/
State Superseded
Headers show

Comments

phabricator - Jan. 22, 2018, 1:14 a.m.
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




To: indygreg, #hg-reviewers
Cc: mercurial-devel
phabricator - Jan. 22, 2018, 4:23 a.m.
phillco accepted this revision.
phillco added a comment.


  Nice.

REPOSITORY
  rHG Mercurial

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

To: indygreg, #hg-reviewers, phillco
Cc: phillco, mercurial-devel
phabricator - Jan. 22, 2018, 12:50 p.m.
yuja accepted this revision.
yuja added a comment.
This revision is now accepted and ready to land.


  Simple and huge improvement enough to push into the release.
  Queued, thanks.

REPOSITORY
  rHG Mercurial

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

To: indygreg, #hg-reviewers, phillco, yuja
Cc: yuja, phillco, mercurial-devel
phabricator - Jan. 22, 2018, 5:36 p.m.
martinvonz added inline comments.

INLINE COMMENTS

> convcmd.py:242
>          while visit:
>              n = visit.pop(0)
>              if n in known:

Can this `visit` also get large?

REPOSITORY
  rHG Mercurial

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

To: indygreg, #hg-reviewers, phillco, yuja
Cc: martinvonz, yuja, phillco, mercurial-devel
phabricator - Jan. 22, 2018, 8:04 p.m.
indygreg added inline comments.

INLINE COMMENTS

> martinvonz wrote in convcmd.py:242
> Can this `visit` also get large?

Probably. All uses of `list.pop(0)` should be viewed with skepticism.

REPOSITORY
  rHG Mercurial

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

To: indygreg, #hg-reviewers, phillco, yuja
Cc: martinvonz, yuja, phillco, mercurial-devel

Patch

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)