Here are two optimizations for git-prune that we've been running at GitHub for ages. No particular reason to share them now; they just finally floated to the top of my todo pile. Do note that I rebased and polished them (and the third one is brand new), so the concepts are proven, but it's possible I introduced a new bug. ;) [1/3]: prune: lazily perform reachability traversal [2/3]: prune: use bitmaps for reachability traversal [3/3]: prune: check SEEN flag for reachability builtin/prune.c | 44 +++++++++++++++++++++++++++++++------------ reachable.c | 42 +++++++++++++++++++++++++++++++++++++++++ t/perf/p5304-prune.sh | 35 ++++++++++++++++++++++++++++++++++ t/t5304-prune.sh | 12 ++++++++++++ 4 files changed, 121 insertions(+), 12 deletions(-) create mode 100755 t/perf/p5304-prune.sh -Peff
