Given a commit and a path, efficiently determine the most recent ancestor commit where the path was touched.

In Git and Mercurial, log operations with a path are relatively slow. For example:

git log -n1 <commit> -- <path>

...routinely takes several hundred milliseconds, and equivalent requests often take longer in Mercurial.

Unfortunately, this operation is fundamental to rendering a repository for the web, and essentially everything else that's slow can be reduced to this plus some trivial work afterward. Making this fast is desirable and powerful, and allows us to make other things fast by expressing them in terms of this query.

Because the query is fundamentally a graph query, it isn't easy to express in a reasonable way in MySQL, and we can't do round trips to the server to walk the graph without incurring huge performance penalties.

However, the total amount of data in the graph is relatively small. By caching it in chunks and keeping it in APC, we can reasonably load and walk the graph in PHP quickly.

For more context, see T2683.

Structure of the Cache

The cache divides commits into buckets (see getBucketSize()). To walk the graph, we pull a commit's bucket. The bucket is a map from commit IDs to a list of parents and changed paths, separated by null. For example, a bucket might look like this:

array(
  1 => array(0, null, 17, 18),
  2 => array(1, null, 4),
  // ...
)

This means that commit ID 1 has parent commit 0 (a special value meaning no parents) and affected path IDs 17 and 18. Commit ID 2 has parent commit 1, and affected path 4.

This data structure attempts to balance compactness, ease of construction, simplicity of cache semantics, and lookup performance. In the average case, it appears to do a reasonable job at this.