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

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