This is an archive of the discontinued Mercurial Phabricator instance.

convert: use a collections.deque

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



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

rHG Mercurial
Automatic diff as part of commit; lint not applicable.
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.


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
This revision was automatically updated to reflect the committed changes.
martinvonz added inline comments.

Can this visit also get large?

indygreg added inline comments.Jan 22 2018, 3:04 PM

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