limit "contains" traversals based on commit timestamp
authorJeff King <peff@peff.net>
Sat, 11 Jun 2011 19:04:09 +0000 (19:04 +0000)
committerJunio C Hamano <gitster@pobox.com>
Sun, 12 Jun 2011 05:32:30 +0000 (22:32 -0700)
commit0c811a7a6f93691604d48b1c13a6868c89971528
treed9988e04cd5a4b5643959c9d8baf76a87ee00b81
parentffc4b8012d9a4f92ef238ff72c0d15e9e1b402ed
limit "contains" traversals based on commit timestamp

When looking for commits that contain other commits (e.g.,
via "git tag --contains"), we can end up traversing useless
portions of the graph. For example, if I am looking for a
tag that contains a commit made last week, there is not much
point in traversing portions of the history graph made five
years ago.

This optimization can provide massive speedups. For example,
doing "git tag --contains HEAD~200" in the linux-2.6
repository goes from:

  real    0m5.302s
  user    0m5.116s
  sys     0m0.184s

to:

  real    0m0.030s
  user    0m0.020s
  sys     0m0.008s

The downside is that we will no longer find some answers in
the face of extreme clock skew, as we will stop the
traversal early when seeing commits skewed too far into the
past.

Name-rev already implements a similar optimization, using a
"slop" of one day to allow for a certain amount of clock
skew in commit timestamps. This patch introduces a
"core.clockskew" variable, which allows specifying the
allowable amount of clock skew in seconds.  For safety, it
defaults to "none", causing a full traversal (i.e., no
change in behavior from previous versions).

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
builtin/tag.c