OperationType::FilterByTouchedPaths during git sync is slow on large repo

[bryango]

Possibly related:

• Speeding up performance #1269

Prior arts:

• patch id #76
• RepoPool abstraction for better parallel performance #265

I use git-branchless to work on https://github.com/NixOS/nixpkgs, which is a somewhat high volume repo. It's usual for me git sync thousands of commits (and once in a while, 10k commits). The in-memory rebase is much more enjoyable than the pristine git rebase. However, the whole process is often bottlenecked by the OperationType::FilterByTouchedPaths step in filter_path_to_merge_base_commits:

Going through the source code and git history I found that this step has already been optimized before in #76 and #265; in particular, the filtering is already parallelized. I wonder if there is anything more we can do to speed things up, since it still often takes up to minutes (for 10k commits) to finish (on my old laptop). Thank you!

[arxanas]

[topic: implementation] This pass implements commit deduplication to detect when you've merged commits upstream and hide them locally. There's a few main steps:

• for each upstream commit, calculate the set of changed paths (parallelizable)
• for each rebased commit, find upstream commits that touch any of the same paths
• compute patch IDs for each rebased commit and compare against matched upstream commits

Comments:

• it's possible that one of those steps is algorithmically or practically inefficient.
• it's possible that timing is being attributed to the wrong step
• nixpkgs may have some pessimizing behavior (like if most commits touch a lockfile or something like that)
• I'm surprised that it takes a while to only index ~2k commits by path (should be simple tree object comparison)
  • what are the specs on your computer?

[topic: practical solutions]

• There should be a --no-deduplicate flag or similar to opt out of this behavior.
• If you successfully sync, then the next sync should examine a much smaller upstream set.
  • If you can't successfully sync certain draft work, you could restrict the set of synced commits (oftentimes I do only git sync -pm 'stack()').

[bryango]

I'm surprised that it takes a while to only index ~2k commits by path (should be simple tree object comparison)

* what are the specs on your computer?

Ah the image shows a small sync which only takes a few seconds. But I frequently need to do several 10k syncs which can take up to minutes (I have amended the original post to be more precise). And git-branchless is already much easier than pristine git, for which I am very grateful! 😆 As reported by hwinfo --short, I have an 8-core i5-8250U CPU @ 1.60GHz, 2600 MHz with 8G RAM.

[bryango]

I will try to look at the implementation and see if there is anything we can squeeze out of it 😆 Thank you!

[arxanas]

Btw I believe there is still room to improve the algorithms because it's slower than git cherry IIRC

[arxanas]

Btw I believe there is still room to improve the algorithms because it's slower than git cherry IIRC