unshelve is slow

[Aliaksei Vasileuski]

I removed files.
I shelved the change (the removal).
Whole unshelve operation takes 14-15 seconds, and "Merge phase 0/3" is taking 10+ seconds.

I have 3000+ revisions and ~10 branches in the repository.

[Aliaksei Vasileuski (sagara1337)]

It is taking a lot of time for any shelved changes, not just file removal/recreation.

[Robert Collins (lifeless)]

Hi, please tell us:
 - how many files are in your tree - (bzr inventory | wc -l) will show that.
 - what your working configuration is - (bzr info -v) will show that.
 - get an lsprof of the problem (add --lsprof-file trace.callgrind before the command name - e.g. 'bzr --lsprof-file trace.callgrind unshelve'). Please attach the lsprof to this bug. The only personal data it has is the path to the bzr program.

[Aliaksei Vasileuski (sagara1337)]

BTW I imported the project from SVN.

1. I'm on Windows, so I counted "wc -l" using text editor:
15988

2. "bzr info -v":
Repository tree (format: 2a)
Location:
  shared repository: C:/foo
  repository branch: .

Related branches:
  parent branch: C:/foo/devel
  submit branch: C:/foo/bar

Format:
       control: Meta directory format 1
  working tree: Working tree format 6
        branch: Branch format 7
    repository: Repository format 2a - rich roots, group compression and chk inventories

In the working tree:
     15987 unchanged
         0 modified
         0 added
         0 removed
         0 renamed
         1 unknown
      1023 ignored
      1411 versioned subdirectories

Branch history:
      3557 revisions
       486 days old
   first revision: Fri 2009-02-27 07:58:05 +0000
  latest revision: Mon 2010-06-28 15:14:11 +0300

Repository:
      5033 revisions

3. attached

[John A Meinel (jameinel)]

So I believe the callgrind file shows that it took 17s, which fits with your
description. (running under profiling goes a bit slower, and you said 14-15s.)

Looking at the graph, I see:
  12.6s under _entries3, which is running iter_changes over ~17k files + dirs.
    IterChanges is running the generic comparison path (not the optimized
    workingtree vs disk-state version).
    This is for *unshelve* so that may be reasonable. (it needs to compare the
    state that was shelved versus the state that it was based upon, both of
    which are repository-level operations, and don't touch the workingtree.)

  Of that 12.6s 5.2s is in 'PreviewTree.iter_entries_by_dir()'

My basic guess is that the shelve/unshelve code is using its own disk format,
which means that it needs to regenerate the entire state of the tree to do
unshelve.

Shelve is fast because it does:
 1) run the fast WT.iter_changes() code, and aggregate the result.
 2) Create a logical inventory delta (tree tranform serialization) which
    applies against the current basis of the working tree.

(1) has to stat every file in your working tree, but otherwise operates on just
the changes, as does (2).

Unshelve is slow because it does:
 1) Read the serialized delta (this is fast)
 2) Extract the entire logical basis tree from disk and apply the few deltas to
 it. This is slow because it has to create entries for all of those files that
 weren't actually modified.
 3) Compare the new whole-tree versus some other tree, and determine what is
 actually changed. This is also a whole-tree operation. (I may be wrong on this
 part).

Basically, I don't have any quick fixes but I think the issue is that
PreviewTree.iter_changes() is using the generic whole-tree comparison path,
when it already has a delta avaliable. That delta may not always be against the
ideal base, though. But if it is, it certainly seems like it could be fast.

[Aliaksei Vasileuski (sagara1337)]

Please, update status of the issue.