Subject: Re: [PATCH 11/16] rev-list: add bitmap mode to speed up lists

From: Thomas Rast <[email-masked]>
Date: Tue, 25 Jun 2013 09:22:28 -0700

Vicent Marti <[email-masked]> writes:

> Calling `git rev-list --use-bitmaps [committish]` is the equivalent
> of `git rev-list --objects`, but the rev list is performed based on
> a bitmap result instead of using a manual counting objects phase.

Why would we ever want to not --use-bitmaps, once it actually works?
I.e., shouldn't this be the default if pack.usebitmaps is set (or
possibly even core.usebitmaps for these things)?

> These are some example timings for `torvalds/linux`:
>
> 	$ time ../git/git rev-list --objects master > /dev/null
>
> 	real    0m25.567s
> 	user    0m25.148s
> 	sys     0m0.384s
>
> 	$ time ../git/git rev-list --use-bitmaps master > /dev/null
>
> 	real    0m0.393s
> 	user    0m0.356s
> 	sys     0m0.036s

I see your badass numbers, and raise you a critical issue:

  $ time git rev-list --use-bitmaps --count --left-right origin/pu...origin/next
  Segmentation fault

  real    0m0.408s
  user    0m0.383s
  sys     0m0.022s

It actually seems to be related solely to having negated commits in the
walk:

  thomas@linux-k42r:~/g(next u+65)$ time git rev-list --use-bitmaps --count origin/pu
  32315

  real    0m0.041s
  user    0m0.034s
  sys     0m0.006s
  thomas@linux-k42r:~/g(next u+65)$ time git rev-list --use-bitmaps --count origin/pu ^origin/next
  Segmentation fault

  real    0m0.460s
  user    0m0.214s
  sys     0m0.244s

I also can't help noticing that the time spent generating the segfault
would have sufficed to generate the answer "the old way" as well:

  $ time git rev-list --count --left-right origin/pu...origin/next
  189     125

  real    0m0.409s
  user    0m0.386s
  sys     0m0.022s

Can we use the same trick to speed up merge base computation and then
--left-right?  The latter is a component of __git_ps1 and can get
somewhat slow in some cases, so it would be nice to make it really fast,
too.

-- 
Thomas Rast
trast@{inf,student}.ethz.ch