annotate comparison.txt @ 872:9a0af739cf55

dirstate walking optimizations

The repo walking code introduces a number of calls to dirstate.map.copy(),
significantly slowing down the walk on large trees.  When a list of
files is passed to the walking code, we should only look at map entries
relevant to the file list passed in.

dirstate.filterfiles() is added to return a subset of the dirstate map.
The subset includes in files passed in, and if one of the files requested
is actually a directory, it includes any files inside that directory tree.

This brings the time for hg diff Makefile down from 1.7s to .3s on
a linux kernel repo.

Also, the diff command was unconditionally calling makewalk, leading
to an extra pass through repo.changes.  This patch avoids the call
to makewalk when commands.diff isn't given a list of patterns, cutting
the time for hg diff (with no args) in half.

Index: mine/mercurial/hg.py
===================================================================

                    Mercurial      git                     BK (*)
storage             revlog delta   compressed revisions    SCCS weave
storage naming      by filename    by revision hash        by filename
merge               file DAGs      changeset DAG           file DAGs?
consistency         SHA1           SHA1                    CRC
signable?           yes            yes                     no       

retrieve file tip   O(1)           O(1)                    O(revs)
add rev             O(1)           O(1)                    O(revs)
find prev file rev  O(1)           O(changesets)           O(revs)
annotate file       O(revs)        O(changesets)           O(revs)
find file changeset O(1)           O(changesets)           ?

checkout            O(files)       O(files)                O(revs)?
commit              O(changes)     O(changes)              ?
                    6 patches/s    6 patches/s             slow
diff working dir    O(changes)     O(changes)              ?
                    < 1s           < 1s                    ?
tree diff revs      O(changes)     O(changes)              ?
                    < 1s           < 1s                    ?
hardlink clone      O(files)       O(revisions)            O(files)

find remote csets   O(log new)     rsync: O(revisions)     ?
                                   git-http: O(changesets)
pull remote csets   O(patch)       O(modified files)       O(patch)

repo growth         O(patch)       O(revisions)            O(patch)
 kernel history     300M           3.5G?                   250M?
lines of code       2500           6500 (+ cogito)         ??

* I've never used BK so this is just guesses