This is an archive of the discontinued Mercurial Phabricator instance.

Differential D1934

convert: use a collections.deque
ClosedPublic

Authored by indygreg on Jan 21 2018, 8:14 PM.

Details

Reviewers
phillco
yuja
Group Reviewers
hg-reviewers
Commits
rHGeefabd9ed3e1: convert: use a collections.deque
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

Diff Detail

Repository
rHG Mercurial
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

indygreg created this revision.Jan 21 2018, 8:14 PM
phillco accepted this revision.Jan 21 2018, 11:23 PM
phillco added a subscriber: phillco.

Nice.

yuja accepted this revision.Jan 22 2018, 7:50 AM
yuja added a subscriber: yuja.

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

This revision is now accepted and ready to land.Jan 22 2018, 7:50 AM
Closed by commit rHGeefabd9ed3e1: convert: use a collections.deque (authored by indygreg). · Explain WhyJan 22 2018, 8:00 AM
This revision was automatically updated to reflect the committed changes.
martinvonz added a subscriber: martinvonz.Jan 22 2018, 12:36 PM
martinvonz added inline comments.
hgext/convert/convcmd.py
242

Can this visit also get large?

indygreg added inline comments.Jan 22 2018, 3:04 PM
hgext/convert/convcmd.py
242

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

Revision Contents
Changeset List

PathPackages
Mhgext/convert/convcmd.py (5 lines)

Diff 4976

hgext/convert/convcmd.py

# convcmd - convert extension commands definition # convcmd - convert extension commands definition
# #
# Copyright 2005-2007 Matt Mackall <mpm@selenic.com> # Copyright 2005-2007 Matt Mackall <mpm@selenic.com>
# #
# This software may be used and distributed according to the terms of the # This software may be used and distributed according to the terms of the
# GNU General Public License version 2 or any later version. # GNU General Public License version 2 or any later version.
from __future__ import absolute_import from __future__ import absolute_import
import collections
import os import os
import shlex import shlex
import shutil import shutil
from mercurial.i18n import _ from mercurial.i18n import _
from mercurial import ( from mercurial import (
encoding, encoding,
error, error,
def walktree(self, heads): def walktree(self, heads):
'''Return a mapping that identifies the uncommitted parents of every '''Return a mapping that identifies the uncommitted parents of every
uncommitted changeset.''' uncommitted changeset.'''
visit = heads visit = heads
known = set() known = set()
parents = {} parents = {}
numcommits = self.source.numcommits() numcommits = self.source.numcommits()
while visit: while visit:
n = visit.pop(0) n = visit.pop(0)
martinvonzUnsubmitted
Not Done

Can this visit also get large?

martinvonz: Can this `visit` also get large?
indygregAuthorUnsubmitted
Not Done

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

indygreg: Probably. All uses of `list.pop(0)` should be viewed with skepticism.
if n in known: if n in known:
continue continue
if n in self.map: if n in self.map:
m = self.map[n] m = self.map[n]
if m == SKIPREV or self.dest.hascommitfrommap(m): if m == SKIPREV or self.dest.hascommitfrommap(m):
continue continue
known.add(n) known.add(n)
self.ui.progress(_('scanning'), len(known), unit=_('revisions'), self.ui.progress(_('scanning'), len(known), unit=_('revisions'),
preceded by all its uncommitted ancestors.''' preceded by all its uncommitted ancestors.'''
def mapchildren(parents): def mapchildren(parents):
"""Return a (children, roots) tuple where 'children' maps parent """Return a (children, roots) tuple where 'children' maps parent
revision identifiers to children ones, and 'roots' is the list of revision identifiers to children ones, and 'roots' is the list of
revisions without parents. 'parents' must be a mapping of revision revisions without parents. 'parents' must be a mapping of revision
identifier to its parents ones. identifier to its parents ones.
""" """
visit = sorted(parents) visit = collections.deque(sorted(parents))
seen = set() seen = set()
children = {} children = {}
roots = [] roots = []
while visit: while visit:
n = visit.pop(0) n = visit.popleft()
if n in seen: if n in seen:
continue continue
seen.add(n) seen.add(n)
# Ensure that nodes without parents are present in the # Ensure that nodes without parents are present in the
# 'children' mapping. # 'children' mapping.
children.setdefault(n, []) children.setdefault(n, [])
hasparent = False hasparent = False
for p in parents[n]: for p in parents[n]: