[PATCH 0/8] use merge-base for tag --contains

[Jeff King <peff@peff.net>]

Once upon a time we checked "tag --contains" by doing N merge-base
traversals, one per tag. That turned out to be really slow.

Later, I added a single traversal in ffc4b80 (tag: speed up --contains
calculation, 2011-06-11) that works in a depth-first way. That's fast
for the common case of tags spread throughout history, but slow when all
of the tags are close to the searched-for commit (which would be more
likely with branches, since they advance). That, plus the general
hacky-ness of the implementation, prevented it from being used for "git
branch" or in other places.

Over a year ago, Junio and I worked on the commit-slab code. The
original point of it[1] was to be able to do a merge-base traversal like
this, where we kept one bit per tip in each commit (so that we know not
only what the merge base is, but _which_ tip hit each commit). So now I
finally got around to it. :)

Timings are in the final patch, but the short of it is: it's about as
fast as the depth-first code for the normal tag case (tags spread out
through history), but way faster for the branch-like case (tags close to
the commit).

This series stops short of moving "git branch" over to it.  My next goal
once this is solid is to factor the logic out so that "tag -l", "branch
-l", and "for-each-ref" all use the same code. I got stuck on that
earlier because I just couldn't justify sharing the tag-contains
implementation with the others.

  [1/8]: tag: allow --sort with -n
  [2/8]: tag: factor out decision to stream tags
  [3/8]: paint_down_to_common: use prio_queue
  [4/8]: add functions for memory-efficient bitmaps
  [5/8]: string-list: add pos to iterator callback
  [6/8]: commit: provide a fast multi-tip contains function
  [7/8]: tag: use commit_contains
  [8/8]: perf: add tests for tag --contains

-Peff

[1] http://article.gmane.org/gmane.comp.version-control.git/220545