Git commit generation numbers

Ok, so I see that the old discussion about generation numbers has resurfaced.

And I have to say, with six years of git use, I think it's not a
coincidence that the notion of generation numbers has come up several
times over the years: I think the lack of them is literally the only
real design mistake we have.

And I absolutely *detest* the generation number cache thing I see on the list.

Maybe I missed the discussion that actually added them to the commits
(I don't read the git mailing list regularly any more) but I think
it's a mistake to add an external cache to work around the fact that I
didn't add the generation numbers originally.

So I think we should just add the generation numbers now. We can make
the rule be that if a commit doesn't have a generation number, we end
up having to compute it (with no real need for caching). Yes, it's
expensive. But it's going to be a *lot* less expensive over time as
people start using a git version that adds the generation numbers to
commits.

And we can easily mix this - there's no "flag-day" issues. Old
versions of git will ignore the generation number and generate new
commits that doesn't have it. New versions of git will generate them,
and use them. And once the project starts having generation numbers in
some commits, the "generating them" part will get cheaper over time.

I'll send out a patch that admittedly does not have much testing as a
reply to this one. It ends up being really simple. Of course, maybe
it's simple because I did something incredibly stupid, but please take
a look.

                                 Linus

On Thu, Jul 14, 2011 at 11:24:27AM -0700, Linus Torvalds wrote:

And I have to say, with six years of git use, I think it's not a
coincidence that the notion of generation numbers has come up several
times over the years: I think the lack of them is literally the only
real design mistake we have.

Agreed.

And I absolutely *detest* the generation number cache thing I see on
the list.

I'd love to have in-commit generation numbers. I'm just not sure we can
get the speeds we want without caching them for existing commits.

Maybe I missed the discussion that actually added them to the commits
(I don't read the git mailing list regularly any more) but I think
it's a mistake to add an external cache to work around the fact that I
didn't add the generation numbers originally.

So I think we should just add the generation numbers now. We can make
the rule be that if a commit doesn't have a generation number, we end
up having to compute it (with no real need for caching). Yes, it's
expensive. But it's going to be a *lot* less expensive over time as
people start using a git version that adds the generation numbers to
commits.

I'm not sure that is the best plan. Calculating generation numbers
involves going to all roots. So once you have to find any generation
number, it's going to be expensive, no matter how many recent commits
have generation numbers already in them (but it won't get _more_
expensive as more commits are added; you'll always be traversing from
the commit in question down to the roots).

As we add new commits with generation numbers, we won't need to do a
calculation to get their numbers. But if you are doing something like
"tag --contains", you are going to want to know the generation number of
old tags (otherwise, you can't know whether your cutoff might hit them
or not). IOW, even if we add generation numbers _today_, every "tag
--contains" in linux-2.6 is going to end up traversing from v3.0-rc7
down to the roots to get its generation number (v3.0-rc8 would get an
embedded generation, of course).

So if you aren't going to cache generation numbers, then you might as
well write your traversal algorithm to assume you don't know them for
old commits. Because calculating them needs to touch every ancestor, and
that's probably equivalent to the worst-case for your algorithm.


There's also one other issue with generation numbers. How do you handle
grafts and object-replacement refs?  If you graft history, your embedded
generation numbers will all be junk, and you can't trust them.

-Peff

On Thu, Jul 14, 2011 at 11:37 AM, Jeff King [off-list ref] wrote:

I'd love to have in-commit generation numbers. I'm just not sure we can
get the speeds we want without caching them for existing commits.

So my argument would be that we'd simply be much better off fixing the
fundamental data structure (which we can), and let it become the
long-term solution.

Now, if *may* turn out that we'd want to have some cache for
generation numbers in commits that don't have them, but I absolutely
think that that should be a "add-on" rather than anything fundamental.
For example, if we just merge the "add generation numbers to the
commit object" logic first, then the "cache" case never really needs
to care about us generating new commits. They simply won't need the
cache.

Also, I suspect that the cache could easily be done as a *small* and
*incomplete* cache, ie you don't need to cache all commits, it would
be sufficient to cache a few hundred spread-out commits, and just know
that "from any commit, the cached commit will be quickly reachable".

I'm not sure that is the best plan. Calculating generation numbers
involves going to all roots. So once you have to find any generation
number, it's going to be expensive, no matter how many recent commits
have generation numbers already in them (but it won't get _more_
expensive as more commits are added; you'll always be traversing from
the commit in question down to the roots).

It only ends up being expensive if the commit has parents that don't
have generation numbers.

That's a fairly short-term problem. For the kernel, for example,
basically no development happens on a base that is older than one or
two releases. So if I (and Greg, with the stable tree) start using my
patch, within a couple of weeks, pretty much all development would
have a generation number in its history.

Sure, sometimes I'd merge from people who based their tree on
something old, and I'd end up calculating it all. But it would get
progressively rarer.

As we add new commits with generation numbers, we won't need to do a
calculation to get their numbers. But if you are doing something like
"tag --contains", you are going to want to know the generation number of
old tags (otherwise, you can't know whether your cutoff might hit them
or not). IOW, even if we add generation numbers _today_, every "tag
--contains" in linux-2.6 is going to end up traversing from v3.0-rc7
down to the roots to get its generation number (v3.0-rc8 would get an
embedded generation, of course).

So that could easily be handled by caching. In fact, I suspect that
you could make the cache no associate with a commit ID, but be
associated with the tags and heads. But again, then the cache would be
a "secondary" issue, not something fundamental.

So if you aren't going to cache generation numbers, then you might as
well write your traversal algorithm to assume you don't know them for
old commits.

But that's how our algorithms are *already* written.

So why not have that as the fallback? You get the advantage of
generation numbers only with modern things, but those are the ones you
actually tend to use.

Merge bases are *very* seldom historical, for example.

                     Linus

On Thu, Jul 14, 2011 at 11:37 AM, Jeff King [off-list ref] wrote:

There's also one other issue with generation numbers. How do you handle
grafts and object-replacement refs?  If you graft history, your embedded
generation numbers will all be junk, and you can't trust them.

So I don't think this is a real problem in practice.

Grafts are already unreliable. You cannot sanely merge over a graft,
and it has nothing to do with generation numbers.

I'm actually sorry that we ever did grafting. It's fundamentally
broken, and can actually destroy your repository (by hiding real
parents and then causing the commits to get garbage collected). So I
don't think grafting should be used as an argument for or against
anything - it's a hack that breaks some fundamental git database
constraints.

                             Linus

On Thu, Jul 14, 2011 at 11:47 AM, Linus Torvalds
[off-list ref] wrote:

Also, I suspect that the cache could easily be done as a *small* and
*incomplete* cache, ie you don't need to cache all commits, it would
be sufficient to cache a few hundred spread-out commits, and just know
that "from any commit, the cached commit will be quickly reachable".

Put another way: we could do the cache not as a real dynamic entity,
but as something that gets generated at "git clone" time or when
re-packing.

I'm actually much more nervous about a cache being inconsistent than I
would be about having generation numbers in the tree. The latter we
can (and should - but my patch didn't) add a fsck test for, and then
you would never get into some situation where there's some really
subtle issue with merge base calculation due to a corrupt cache.

                    Linus

Linus Torvalds [off-list ref] writes:

On Thu, Jul 14, 2011 at 11:37 AM, Jeff King [off-list ref] wrote:

quoted

There's also one other issue with generation numbers. How do you handle
grafts and object-replacement refs?  If you graft history, your embedded
generation numbers will all be junk, and you can't trust them.

So I don't think this is a real problem in practice.

Grafts are already unreliable. You cannot sanely merge over a graft,
and it has nothing to do with generation numbers.

I'm actually sorry that we ever did grafting. It's fundamentally
broken, and can actually destroy your repository (by hiding real
parents and then causing the commits to get garbage collected). So I
don't think grafting should be used as an argument for or against
anything - it's a hack that breaks some fundamental git database
constraints.

What about object-replacement refs (i.e. "git replace" and refs/replace/)?

This is modern replacement for grafts mechanism, which is safe against
garbage collecting, and contrary to grafts it is transferable (as a ref).

With replacement objects (e.g. to repair some fragment of history to
make it bisectable - I think that was original idea behind introducing
git-replace, or instead of grafts to join with historical repository -
IIRC the reason why grafts mechanism was created) you can also have
invalid generation numbers if they are stored in commit headers.  With
generation cache we can simply invaliate it if grafts or replacements
change...

P.S. grafts are quite useful when doing history surgery.  Create
grafts, check history, use git-filter-branch to make new DAG
permanent, remove grafts.

P.P.S. What about "grafts lite", i.e. shallow clone?  With generation
cache we can invalidate it when depth changes...

-- 
Jakub Narębski
Poland

On Thu, Jul 14, 2011 at 11:47:45AM -0700, Linus Torvalds wrote:

On Thu, Jul 14, 2011 at 11:37 AM, Jeff King [off-list ref] wrote:

quoted

I'd love to have in-commit generation numbers. I'm just not sure we can
get the speeds we want without caching them for existing commits.

So my argument would be that we'd simply be much better off fixing the
fundamental data structure (which we can), and let it become the
long-term solution.

Now, if *may* turn out that we'd want to have some cache for
generation numbers in commits that don't have them, but I absolutely
think that that should be a "add-on" rather than anything fundamental.
For example, if we just merge the "add generation numbers to the
commit object" logic first, then the "cache" case never really needs
to care about us generating new commits. They simply won't need the
cache.

Sure, I'd be fine with that (modulo the graft issue, which you don't
seem to care about). I half-toyed with making an extra "add generation
numbers to commit header" on top of my series, but I wanted to first
prove that generation numbers actually could yield speedups.

Also, I suspect that the cache could easily be done as a *small* and
*incomplete* cache, ie you don't need to cache all commits, it would
be sufficient to cache a few hundred spread-out commits, and just know
that "from any commit, the cached commit will be quickly reachable".

Yeah, that would work. Is it worth the trouble? Your cache size is still
O(n). And you still have the complexity of _having_ a cache.  Yes, the
size is 1/100th of what it was (dropping from 6M to 600K on linux-2.6).
But you're also going to spend more time calculating. I think you'd have
to measure to see how it performs in practice.

It only ends up being expensive if the commit has parents that don't
have generation numbers.

That's a fairly short-term problem. For the kernel, for example,
basically no development happens on a base that is older than one or
two releases. So if I (and Greg, with the stable tree) start using my
patch, within a couple of weeks, pretty much all development would
have a generation number in its history.

Sure, that makes generation during commit-time cheaper, and eventually
the cost just goes away. I'm more concerned that it won't actually speed
up algorithms where you look at old commits, which was the whole point
in the first place.

quoted

As we add new commits with generation numbers, we won't need to do a
calculation to get their numbers. But if you are doing something like
"tag --contains", you are going to want to know the generation number of
old tags (otherwise, you can't know whether your cutoff might hit them
or not). IOW, even if we add generation numbers _today_, every "tag
--contains" in linux-2.6 is going to end up traversing from v3.0-rc7
down to the roots to get its generation number (v3.0-rc8 would get an
embedded generation, of course).

So that could easily be handled by caching. In fact, I suspect that
you could make the cache no associate with a commit ID, but be
associated with the tags and heads. But again, then the cache would be
a "secondary" issue, not something fundamental.

Yeah, you could do that. And it would handle "tag --contains" and
"branch --contains" (the latter doesn't even really need a cache; as the
branch tips move, they will get new commits with generation numbers). I
suspect we could get faster topo-sorting and possibly faster merge-base
calculation out of generation numbers, too.  But that won't happen if we
only have generation numbers for a handful of specific commits.

quoted

So if you aren't going to cache generation numbers, then you might as
well write your traversal algorithm to assume you don't know them for
old commits.

But that's how our algorithms are *already* written.

Sort of. We tend to rely on commit timestamps as a proxy for generation
numbers. But in the face of clock skew, git will give wrong answers
(e.g., Ted posted some examples of name-rev giving wrong answers near
some skew in linux-2.6).

If we aren't going to go whole-hog on generation numbers, I'm much more
tempted to simply keep using commit timestamps. It's easy to build a
cache of commits with bogus timestamps (which I've already posted a
patch for) if you want to better accuracy at the cost of more
complexity. And as time progresses, you tend to ask about commits near
the skewed ones less often (and hopefully lessons learned from seeing
how the skew occurred will help us prevent them from reocurring in new
commits).

-Peff

On Thu, Jul 14, 2011 at 11:55:39AM -0700, Linus Torvalds wrote:

I'm actually much more nervous about a cache being inconsistent than I
would be about having generation numbers in the tree. The latter we
can (and should - but my patch didn't) add a fsck test for, and then
you would never get into some situation where there's some really
subtle issue with merge base calculation due to a corrupt cache.

Interesting. I'm nervous about that, too, which is why I _favor_ the
cache. Because we calculate the cache ourselves, we know its accurate
according to the parent pointers. If we find a bug, we fix it and bump
the cache version, which forces it to regenerate.

Contrast that with a bogus generation number that makes its way into an
actual commit object. That's there for eternity, just like the commit
timestamp skew we already have. I find it much less likely to happen
than skew in the commit timestamp, if only because generations are a
dirt-simple concept. But it is a case where there is duplicated
information in the actual DAG, and if that information doesn't match up
we are screwed.

-Peff

On Thu, Jul 14, 2011 at 12:08 PM, Jeff King [off-list ref] wrote:

If we aren't going to go whole-hog on generation numbers, I'm much more
tempted to simply keep using commit timestamps.

Sure. I think it's entirely reasonable to say that the issue basically
boils down to one git question: "can commit X be an ancestor of commit
Y" (as a way to basically limit certain algorithms from having to walk
all the way down). We've used commit dates for it, and realistically
it really has worked very well. But it was always a broken heuristic.

So yes, I personally see generation counters as a way to do the commit
date comparisons right. And it would be perfectly fine to just say "if
there are no generation numbers, we'll use the datestamps instead, and
know that they could be incorrect".

That "use the datestamps" fallback thing may well involve all the
heuristics we already do (ie check for the stamps looking sane, and
not trusting just one individual one).

                           Linus

On Thu, Jul 14, 2011 at 11:55:39AM -0700, Linus Torvalds wrote:

On Thu, Jul 14, 2011 at 11:47 AM, Linus Torvalds
[off-list ref] wrote:

quoted

Also, I suspect that the cache could easily be done as a *small* and
*incomplete* cache, ie you don't need to cache all commits, it would
be sufficient to cache a few hundred spread-out commits, and just know
that "from any commit, the cached commit will be quickly reachable".

Put another way: we could do the cache not as a real dynamic entity,
but as something that gets generated at "git clone" time or when
re-packing.

Would it be considered evil if we put the generation number in the
pack, but not consider it part of the formal object (i.e., it would be
just a cache, but one that wouldn't change once the pack was created)?

       	      	      	   	    	   	- Ted

On Thu, Jul 14, 2011 at 12:46 PM, Ted Ts'o [off-list ref] wrote:

Would it be considered evil if we put the generation number in the
pack, but not consider it part of the formal object (i.e., it would be
just a cache, but one that wouldn't change once the pack was created)?

That would actually be a major change to data structures, and would
require some serious surgery and be hard to support in a
backwards-compatible way (think different git versions accessing the
same repository).

Much bigger patch than the one I did.

So it sounds like it would work - and it would probably be a simple
matter of just incrementing the pack version number if you just say
"cannot access the pack with old versions" - but I think it's a really
fragile approach.

                  Linus

On Thu, Jul 14, 2011 at 12:23:31PM -0700, Linus Torvalds wrote:

On Thu, Jul 14, 2011 at 12:08 PM, Jeff King [off-list ref] wrote:

quoted

If we aren't going to go whole-hog on generation numbers, I'm much more
tempted to simply keep using commit timestamps.

Sure. I think it's entirely reasonable to say that the issue basically
boils down to one git question: "can commit X be an ancestor of commit
Y" (as a way to basically limit certain algorithms from having to walk
all the way down). We've used commit dates for it, and realistically
it really has worked very well. But it was always a broken heuristic.

Yeah, I agree with that.

So yes, I personally see generation counters as a way to do the commit
date comparisons right. And it would be perfectly fine to just say "if
there are no generation numbers, we'll use the datestamps instead, and
know that they could be incorrect".

In that case, is it really worth adding generation numbers to the cache?
Because they _can_ be wrong, too. I suspect they will be wrong less
often than commit timestamps, if only because they're dirt simple to
calculate. But all it takes is some crappy porcelain doing:

  git cat-file commit $foo |
  munge_the_parents |
  git hash-object -t commit --stdin -w

to give us a bogus object. Sure, we can catch it via fsck. But we could
also catch commit timestamp skew via fsck just as easily.

That "use the datestamps" fallback thing may well involve all the
heuristics we already do (ie check for the stamps looking sane, and
not trusting just one individual one).

Those aren't foolproof, of course. I asked people a few months ago to
run my skew-detection program on various repos, and some repos have long
runs of skew (think somebody with a bad clock or a bogus program doing a
whole series). But they're fast and work OK in practice. We should apply
them more consistently (name-rev, for example, will tolerate a day of
skew, but will not look past a single commit).

And if people really want to be thorough, we can mark the skewed commits
in a cache during "git gc" for them (or they can just say "for this
traversal, I want to be thorough; turn off timestamp cutoffs").


Out of curiosity, what don't you like about the generation cache? The
idea of using external storage? Generating it on the fly? The particular
implementation is too slow or crappy?

-Peff

On Thu, Jul 14, 2011 at 12:51:39PM -0700, Linus Torvalds wrote:

On Thu, Jul 14, 2011 at 12:46 PM, Ted Ts'o [off-list ref] wrote:

quoted

Would it be considered evil if we put the generation number in the
pack, but not consider it part of the formal object (i.e., it would be
just a cache, but one that wouldn't change once the pack was created)?

That would actually be a major change to data structures, and would
require some serious surgery and be hard to support in a
backwards-compatible way (think different git versions accessing the
same repository).

If we put it in the index, but not the pack, then it wouldn't be any
more painful than pack index v2. I don't recall there being huge fallout
from that; we just gave a reasonable deprecation period before switching
it on as the default.

I'm not sure it is much less crappy than having the cache in a separate
file. It does take less space, since the pack index already contains all
of the sha1s. But if we don't like the on-the-fly writing of what was in
my series, it would not be hard to generate the same cache during
pack-index time. Not having it in a separate file makes it hard to
invalidate the cache when the graph changes (due to grafts or replace
refs). But maybe we don't care about that. Or maybe it's OK to tell the
user to manually rebuild the pack index if they tweak those features.

-Peff

On Thu, Jul 14, 2011 at 12:51:39PM -0700, Linus Torvalds wrote:

So it sounds like it would work - and it would probably be a simple
matter of just incrementing the pack version number if you just say
"cannot access the pack with old versions" - but I think it's a really
fragile approach.

So if we ever change the pack format again, it's something to think
about adding, but probably not worth it on its own...

What if we simply have a cache file per pack, which again is generated
when the pack is first received or generated, but is otherwise not
dynamic?  It's an extra file which is icky, but it would keep things
simpler.

							- Ted

Jeff King [off-list ref] wrote:

Out of curiosity, what don't you like about the generation cache?

The thing I hate about it is very fundamental: I think it's a hack around a basic git design mistake. And it's a mistake we have known about for a long time.

Now, I don't think it's a *fatal* mistake, but I do find it very broken to basically say "we made a mistake in the original commit design, and instead of fixing it we create a separate workaround for it".

THAT I find distasteful. My reaction is that if we're going to add generation numbers, then were should just do it the way we should have done them originally, rather than as some separate hack.

See? That's why I wouldn't have any problem with adding a separate cache on top of it, if it's really required, but I would hope that it isn't really needed.

So a cache in itself is not necessarily wrong. But leaving the original design mistake in place IS.

And fixing it really ended up being a very tiny patch, no?

     Linus

On Thu, Jul 14, 2011 at 01:19:51PM -0700, Linus Torvalds wrote:

quoted

Out of curiosity, what don't you like about the generation cache?

The thing I hate about it is very fundamental: I think it's a hack
around a basic git design mistake. And it's a mistake we have known
about for a long time.

Now, I don't think it's a *fatal* mistake, but I do find it very
broken to basically say "we made a mistake in the original commit
design, and instead of fixing it we create a separate workaround for
it".

THAT I find distasteful. My reaction is that if we're going to add
generation numbers, then were should just do it the way we should have
done them originally, rather than as some separate hack.

See? That's why I wouldn't have any problem with adding a separate
cache on top of it, if it's really required, but I would hope that it
isn't really needed.

So a cache in itself is not necessarily wrong. But leaving the
original design mistake in place IS.

Thanks, that makes some sense to me.

However, I'm not 100% convinced leaving generation numbers out was a
mistake. The git philosophy seems always to have been to keep the
minimal required information in the DAG. And I think that has served us
well, because we're not saddled with cruft that seemed like a good idea
early on, but isn't.

Generation numbers are _completely_ redundant with the actual structure
of history represented by the parent pointers. Having them in there is
not about giving git more information that it doesn't have, but about
being a cheap place to stuff a value that is a little expensive to
calculate.

And so that seems a bit hack-ish to me.

I liken it somewhat to the "don't store renames" debate. We don't want
to crystallize forever in the history whatever crappy rename-detection
algorithm is done at the time of commit. We put the minimum amount of
information in the DAG, and it's the runtime's responsibility to get the
answer.

I think the decision is a little more gray with generation numbers,
because it's not about "you got this information with a wrong and crappy
algorithm" like it might be with rename detection, but rather "we're
sticking this redundant number in the commit object, and we assume that
it will always be useful enough to future algorithms to merit being
here".

And fixing it really ended up being a very tiny patch, no?

Well, yes. But it also doesn't yield a 100-fold speedup in "git tag
--contains" for existing repositories. So it's not quite a full
solution.

-Peff

On Thu, Jul 14, 2011 at 1:31 PM, Jeff King [off-list ref] wrote:

However, I'm not 100% convinced leaving generation numbers out was a
mistake. The git philosophy seems always to have been to keep the
minimal required information in the DAG.

Yes.

And until I saw the patches trying to add generation numbers, I didn't
really try to push adding generation numbers to commits (although it
actually came up as early as July 2005, so the "let's use generation
numbers in commits" thing is *really* old).

In other words, I do agree that we should strive for minimal required
information.

But dammit, if you start using generation numbers, then they *are*
required information. The fact that you then hide them in some
unarchitected random file doesn't change anything! It just makes it
ugly and random, for chrissake!

I really don't understand your logic that says that the cache is
somehow cleaner. It's a random hack! It's saying "we don't have it in
the main data structure, so let's add it to some other one instead,
and now we have a consistency and cache generation problem instead".

Just look at the size of the patches in question. Your caching patches
are bigger and more complicated. Sure, part of it is that your series
adds the code to _use_ the generation number, but look purely at the
code to maintain them.

Why do you think the odd separate cache is somehow better than just
doing it right? Seriously? If we require the generation numbers, then
they have *become* that minimal information that we should save!

 And I think that has served us

well, because we're not saddled with cruft that seemed like a good idea
early on, but isn't.

Again - we discussed adding generation numbers about 6 years ago. We
clearly *should* have done it. Instead, we went with the hacky "let's
use commit time", that everybody really knew was technically wrong,
and was a hack, but avoided the need.

Now, six years later, you clearly are saying that we need the
generation numbers, but then you go off and try to say that they
should be in some secondary non-architected random collection of data
structures that isn't covered by the security and maintenance
guarantees that the core git objects are.

Dammit, one of the things that makes git special is that the data
structures are NOT random odd ad-hoc files. There is a design to them.

Generation numbers are _completely_ redundant with the actual structure
of history represented by the parent pointers.

Not true. That's only true if you add ".. if you parse the whole
history" to that statement.

And we've *never* parsed the whole history, because it's just too
expensive and doesn't scale. So right now we depend on commit dates
with a few hacks.

So no, generation numbers are not at all redundant. They are
fundamental. It's why we had this discussion six years ago.

And so that seems a bit hack-ish to me.

Um? If you feel that way, then why the hell are you pushing your EVEN
MORE HACKISH CACHE PATCHES?

That's what this really boils down to. I think that if we have a value
that we need, then it should be recorded. In the data structures. Not
in some random other location that isn't part of the real git data
structures.

We don't do caches in git, because we don't NEED to. Sure, gitk has
it's hacky cache, but that's not core functionality.

I think it's a sign of good design that we can do a "find .git" and
explain every single file, and show that it's all core functionality
(again, with the exception of "gitk.cache", and I suspect that's
because gitk is a script, not because of any really fundamental data
issues), and explain it.

I think the *cache* is a hell of a lot more hacky than just doing it right.

I liken it somewhat to the "don't store renames" debate.

That's total and utter bullshit.

Storing renames is *wrong*. I've explained a million times why it's
wrong. Doing it is a disaster. I know. I've used systems that did it.
It's crap. It's fundamentally information that is actively misleading
and WRONG. It's not even that you can do rename detection at run-time,
it's that you *HAVE* to do rename detection at run-time, because doing
it at commit time is simply utterly and fundamentally *wrong*.

Just look at "git blame -C" to remind yourself why rename information is wrong.

But even more importantly, look at git merges. Look at how git has
gotten merging right since pretty much day #1, and has absolutely no
issues with files that got generated two different ways. Look at every
SCM that tries to do rename detection, and look at how THEY CANNOT DO
MERGES RIGHT.

It's that simple. Rename detection is not about avoiding "redundant
data". It's about doing the right thing.

                          Linus

On Jul 14, 2011, at 21:19, Linus Torvalds wrote:

But dammit, if you start using generation numbers, then they *are*
required information. The fact that you then hide them in some
unarchitected random file doesn't change anything! It just makes it
ugly and random, for chrissake!

Generation numbers never will be required information, because we
can always compute them. These numbers are really much more similar 
to other pack index information than anything else.

<aside>
Sometimes I wish we'd have general "depth" information for each
SHA1, which would be the maximum number of steps in the DAG to reach
a leaf. This way, if we want to do something like "git log
drivers/net/slip.c", we don't have to bother reading the majority
of trees that have a depth less than two. The depth can also be used
as a limiter for "contains" operations, where we want to see if
commit X contains commit Y: depth (X) has to be at least depth (Y).

However, any such notion, wether generation or depth or whatever
else we'll think of tomorrow, is something particular to a certain
implementation of git. It does not add anything to the information
we stored.
</aside>

I don't think my commit should have a different SHA1 from yours,
because your tree has a more generation numbers than mine.

The beauty and genius of GIT is that it just takes the minimum
amount of data needed to uniquely identify the information to be
stored, and stores that in a UNIQUE format. By allowing generation
numbers to either be present or absent, that's all broken.

It's like computing the SHA1 of compressed data: it doesn't depend
on the data we store, just about the particular representation we
choose. Fortunately we have done away with the first mistake.

So, if you're going to add generation numbers, there has to be a
flag day, after which generation numbers are required everywhere. 
Of course it would be possible to recognize "old style" commits 
and convert them on the fly, but that is true for pretty much 
any format change. However, adding redundant information seems 
like a poor excuse for having a flag day.

Storing generation data in pack indices on the other hand makes
perfect sense: when we generate these indices, we do complete
traversals and have all required information trivially at hand.  We
can never have that many loose objects, so lack of generation
information there isn't a big deal. By storing generation information
in the index, we can be sure it is consistent with the data contained
in the pack, so there are no cache invalidation issues.

I know I must have missed some stupid and obvious reason why
this is all wrong, I just don't quite see it yet.

  -Geert

On Thu, Jul 14, 2011 at 06:19:30PM -0700, Linus Torvalds wrote:

Yes.

And until I saw the patches trying to add generation numbers, I didn't
really try to push adding generation numbers to commits (although it
actually came up as early as July 2005, so the "let's use generation
numbers in commits" thing is *really* old).

In other words, I do agree that we should strive for minimal required
information.

But dammit, if you start using generation numbers, then they *are*
required information. The fact that you then hide them in some
unarchitected random file doesn't change anything! It just makes it
ugly and random, for chrissake!

So you don't see a difference between storing the information directly
in the commit object, where it affects the sha1 of the commit, and
calculating and storing it somewhere else? That is what seems ungit to
me. You aren't adding new information to the DAG (note I said "DAG" and
not commit) that is not already there, but you are changing the ids of
commits in the DAG.

I'm not saying that's a reason to ultimately reject the idea of putting
generation numbers in commit objects. But it is a reason to give us
pause and figure out if there are other solutions, because it will be
the first time such redundant information has been added. And that's
what I've been trying to do during this discussion with you: work out
what the options are and evaluate them.

I really don't understand your logic that says that the cache is
somehow cleaner. It's a random hack! It's saying "we don't have it in
the main data structure, so let's add it to some other one instead,
and now we have a consistency and cache generation problem instead".

Are packfiles unclean, or a random hack? How about pack indices? What
about Nico's and Shawn's ideas for a packv4 that would gain efficiency
by storing objects not in their whole format, but in a way that would
make tree examination faster (but would be able to restore the whole
objects byte for byte)?

Those things rely on the idea that the git DAG is a data model that we
present to the user, but that we're allowed to do things behind the
scenes to make things faster. We're allowed to make an index of offsets
of objects in the packfile for faster lookup. Why are we not allowed to
use an index for other object data if it will speed up our local
algorithms?

Again, I'm not saying that the patches I posted are necessarily the
answer. Maybe my cache implementation sucks. Maybe the value should go
into a pack index instead. Maybe the whole idea is stupid. But I don't
think it's worth rejecting out-of-hand the idea that the generation
number might be stored outside of the commit object. I do think it's
worth talking about what the actual downsides are, as compared to other
options.

For example, you mentioned there a consistency problem in the paragraph
above. What is it?

If you mean the problem with refs/replace, then yes, that is an open
problem to be solved (though not a hard one, as I already mentioned a
solution elsewhere). But is that problem better or worse with this
solution versus an embedded generation number? It seems to me that an
embedded generation number is even worse.

Just look at the size of the patches in question. Your caching patches
are bigger and more complicated. Sure, part of it is that your series
adds the code to _use_ the generation number, but look purely at the
code to maintain them.

It's 300 lines of code. That can also be used to store arbitrary
meta-information for commits. I've already achieved significant speedups
in some workflows by caching patch-id calculations, which would reuse
this code.  And I certainly don't think _that_ should go into the commit
object.

Yes, it's more complex than simply adding a generation number to the
commit header. But simply adding a generation number does not actually
give the 100-fold speedup I'm seeing. So again, I'm not interested in
rejecting solutions out of hand; I'm interested in things like: is the
complexity of the cache worth this speedup? What other options do we
have, and what speedup do they provide? Do we care enough about this
speedup to even bother?

Why do you think the odd separate cache is somehow better than just
doing it right? Seriously? If we require the generation numbers, then
they have *become* that minimal information that we should save!

What do you do when generation numbers don't match the DAG represented
by the parent pointers? Are you proposing to just ignore it? I'm not
asking that question adversarially; ignoring may be the sane thing to
do, and we say "generation numbers are to be trusted, even if they don't
match parent pointers".

Now, six years later, you clearly are saying that we need the
generation numbers, but then you go off and try to say that they
should be in some secondary non-architected random collection of data
structures that isn't covered by the security and maintenance
guarantees that the core git objects are.

I don't think I said we clearly need them. I said we can get speedups by
using them, and I showed some patches. I _also_ posted patches showing
how to accomplish similar speedups using timestamps. Note that all of my
patches started with "RFC". I am trying to figure out which is the best
way to proceed.

And why _would_ they need to be covered by the security and maintenance
guarantees of core objects? You can trivially calculate them from the
core objects. Are pack indices also a "secondary non-architected random
collection of data structures"?

Dammit, one of the things that makes git special is that the data
structures are NOT random odd ad-hoc files. There is a design to them.

There is just as much documentation and design for the new file format I
added as there is for pack indices (in fact, they're quite similar in
design). I really see them at the same level: something we calculate to
speed up some algorithms, but something we could regenerate at any time
if we felt like.

quoted

And so that seems a bit hack-ish to me.

Um? If you feel that way, then why the hell are you pushing your EVEN
MORE HACKISH CACHE PATCHES?

Please, there is really no need to shout. And I find it quite silly that
you would refer to me as "pushing" these patches when they have been
clearly listed as RFC, and everything I have posted in the nearby
threads has been about comparing different strategies (with patches and
timings for some of those other strategies!).

We don't do caches in git, because we don't NEED to. Sure, gitk has
it's hacky cache, but that's not core functionality.

I'm sorry to tell you that there is already a cache for external
conversion of diffs for blobs. And that I have a patch series which
makes "git cherry" much more pleasant to use by caching patch ids.

Do we "need" those? No, of course not. Git works just fine without them,
albeit a bit slower. But is it sometimes worth making a space-time
tradeoff to make some algorithms faster? I think it sometimes is,
depending on the space and time factors, and the complexity of the
storage (e.g., consistency problems with caching).

I think it's a sign of good design that we can do a "find .git" and
explain every single file, and show that it's all core functionality
(again, with the exception of "gitk.cache", and I suspect that's
because gitk is a script, not because of any really fundamental data
issues), and explain it.

Would it make you happier if we stored the generation data in the pack
index when we index the packs?

I think the *cache* is a hell of a lot more hacky than just doing it right.

You still haven't explained how we would "do it right" and get the same
speedups. When I responded to your initial email, your answers were
along the lines of "we could cache fewer things". If your position is to
damn the speedup, the cache is not worth the complexity, I can buy that.
If your position is that the complexity is not worth it, and we are
better off to keep using timestamps, I can buy that. If your position is
that you can find a clever way, using only the generation numbers in
newly created commits, to get similar speedups in "git {tag,branch}
--contains", I'd love to hear it.

quoted

I liken it somewhat to the "don't store renames" debate.

That's total and utter bullshit.

Storing renames is *wrong*. I've explained a million times why it's
wrong. Doing it is a disaster. I know. I've used systems that did it.
It's crap. It's fundamentally information that is actively misleading
and WRONG. It's not even that you can do rename detection at run-time,
it's that you *HAVE* to do rename detection at run-time, because doing
it at commit time is simply utterly and fundamentally *wrong*.

Yes, I am well aware that stored renames are wrong for merging. The
problem is that they not a function of a tree state (which is what a
commit stores), but rather of the difference between two states. So when
you diff the commit's state with some other arbitrary merge-base, any
renames recorded at commit time would be worthless.

But consider another case. Each time I run "git log -M --raw", I compute
the same renames over and over. Let's say I have a case in which this is
annoyingly slow, and want to speed it up. The state of a particular
commit and the state of its parents are invariants for a particular sha1
commit id; this is a fundamental property of git, as you well know. So
for a given rename-detection algorithm (and any parameters it has), the
set of renames between the states will also be an invariant.

Now imagine I create a persistent cache mapping the commit sha1 for some
sane default set of rename algorithm parameters to a set of rename
pairs. My annoyingly slow "log -M" is now faster, and I'm happier.

I think you encounter a similar set of questions here as you do with the
concept of a generation header. If the information is an invariant for a
particular commit sha1, can we and should we store it in the commit
object? Is the speedup worth the complexity of a cache? What are the
circumstances under which the cache is not applicable, and how often do
they come up? Can we accurately detect when the cache is not applicable?

And that is why I compared it to the idea of storing renames. Please
note that I did _not_ say they were exactly the same situation, or that
the answers to one set of questions were the same as the answers to
another.

-Peff

Linus Torvalds [off-list ref] writes:

On Thu, Jul 14, 2011 at 1:31 PM, Jeff King [off-list ref] wrote:

quoted

However, I'm not 100% convinced leaving generation numbers out was a
mistake. The git philosophy seems always to have been to keep the
minimal required information in the DAG.

Yes.

And until I saw the patches trying to add generation numbers, I didn't
really try to push adding generation numbers to commits (although it
actually came up as early as July 2005, so the "let's use generation
numbers in commits" thing is *really* old).

In other words, I do agree that we should strive for minimal required
information.

But dammit, if you start using generation numbers, then they *are*
required information. The fact that you then hide them in some
unarchitected random file doesn't change anything! It just makes it
ugly and random, for chrissake!

I really don't understand your logic that says that the cache is
somehow cleaner. It's a random hack! It's saying "we don't have it in
the main data structure, so let's add it to some other one instead,
and now we have a consistency and cache generation problem instead".

You store redundant information, one that is used to speed up
calculations, in a cache.
 
[...]

quoted

Generation numbers are _completely_ redundant with the actual structure
of history represented by the parent pointers.

What is more important the perceived structure of history can change
by three mechanisms:

 * grafts
 * replace objects
 * shallow clone

I can understand that you don't want to worry about grafts - they are
a terrible hack.  We can simply turn off using generation numbers
stored in commit if they are present.

The problem with shallow clones is only at beginning, when some of
commits in shallow repository does not have generation numbers.  You
cannot simply calculate generation number for a new commit in such
case.

But what about REPLACE OBJECTS?  If one for example use "git replace"
on root commit to join contemporary repository with historical
repository... this is not addressed in your emails.


And let's not forget the fact that we need cache for old commits which
don't have yet generation number in a commit.


BTW. you are not fair comparing size of code.  

First, some of Peff code is about _using_ generation numbers, which
will be needed regardless of whether generation numbers are stored in
cache or packfile index, or whether they are embedded in commit
objects.

Second, with generation number commit header you need to write fsck
code, and have to consider size of this yet-to-be-written code.

[...]

quoted

I liken it somewhat to the "don't store renames" debate.

That's total and utter bullshit.

I think Peff meant here that if you make mistakes in calculating
rename info or generation number, and have incorrect information
stored in commit object, you are f**ked.
 

Storing renames is *wrong*. I've explained a million times why it's
wrong. Doing it is a disaster. I know. I've used systems that did it.
It's crap. It's fundamentally information that is actively misleading
and WRONG. It's not even that you can do rename detection at run-time,
it's that you *HAVE* to do rename detection at run-time, because doing
it at commit time is simply utterly and fundamentally *wrong*.

Just look at "git blame -C" to remind yourself why rename information is wrong.

Also doing full code movement and copying detection (that is what "git
blame -C" does) rather than simplistic whole-file rename detection is
pretty much impossible at commit time.

Nb. most SCMs that use path-id based rename tracking require that user
explicitly marks renames using "scm move" or "scm rename" (well,
Mercurial has a tool for rename detection before commit, "hg
addremove").  But asking user to mark code movements is simply
infeasible.
 

But even more importantly, look at git merges. Look at how git has
gotten merging right since pretty much day #1, and has absolutely no
issues with files that got generated two different ways. Look at every
SCM that tries to do rename detection, and look at how THEY CANNOT DO
MERGES RIGHT.

It's that simple. Rename detection is not about avoiding "redundant
data". It's about doing the right thing.

Well, rename tracking supporters say that heuristic rename detection
can be wrong.


By the way, what happened to "wholesame directory rename detection"
patches?  Without them in the situation where one side renamed
directory, and other created new file in said directory git on merge
creates file in re-created old name of directory...

-- 
Jakub Narebski
Poland

I strongly agree with Linus that the cache should not form part of the
solution to this problem, but could maybe be a later add-on, which
improved performance.

There is a possible improvement, which may remove the need for the
cache. It doesn't solve the issue of broken numbers, but I think the
key to that is just to ensure the traversal algorithm is
deterministic, stable, and immutable.

Firstly, I presume the generation number would not form part of the
SHA1 calculation? No? Cool.

When calculating a generation number by doing a traversal, would it
not be possible to update some, or all, commit objects touched, with
their generation numbers. Again, this would be expensive, but there
would possibly be even quicker gains than Linus's original proposal to
just add numbers to the new commit.

A compromise might be to only update some commits - notably those with
2 or more parents, so that both parents don't need to be traversed,
and possibly every nth commit (to give regular checkpoints that can be
utilised when traversing a branch). I would suggest commits with 2
children for the latter, but with my limited knowledge of the
implementation, I understand that Is more difficult to find.
Obviously, these numbers would only be pegged locally, and wouldn't by
synced on push, as they already exist on the far end. However, it
could be possible to run a process on a bare repo to shoot through and
peg commits, then at least new clones will be "well pegged"

Martin Long
UK

Firstly, I presume the generation number would not form part of the
SHA1 calculation? No? Cool.

I suspect this may be where my suggestion falls down. Though I suspect
there is a case for object metadata which doesn't form part of the
SHA. Would generation number tampering be a concern?

Caching offers the ability to store that metadata, to provide the same
performance gain, but maintain the integrity of the SHA chain.
However, it does still leave the generation number liable to
tampering, meaning a generic non-SHA metadata solution might be
better.

TBH, there are few situations where historical generations are useful
- finding gen numbers of tags is one of them. Most cases are going to
be for new commits, and in that case, a few new commits at the tip of
each branch will very quickly reduce the number of traversals. What
use case would really create enough traversals that it should be a
performance concern?

On Fri, Jul 15, 2011 at 12:46 AM, Jeff King [off-list ref] wrote:

So you don't see a difference between storing the information directly
in the commit object, where it affects the sha1 of the commit, and
calculating and storing it somewhere else?

Sure, I see the difference. And I think it's uglier to have two
different places for required information.

 That is what seems ungit to
me. You aren't adding new information to the DAG (note I said "DAG" and
not commit) that is not already there, but you are changing the ids of
commits in the DAG.

Umm. It's redundant, but so what? We have tons of redundant
information in there already. Those commits are very explicitly using
a 40-byte ASCII representation of the 20-byte SHA1 names. The very
original deeper object structure is also redundant: we repeat the
object size in the object itself, even though it's part of the
implicit object format itself.

We also very purposefully repeat the type of the object there, even
though the type is basically always redundant (in fact, the core git
functions require you to give the type of the object as part of the
lookup, and will error out if the SHA1 points to the wrong type). That
was one of my original design decisions, exactly because I wanted the
redundancy for verification.

Redundancy isn't a problem. It's a source of sanity checking.

I'm not seeing why you are harping on it.

I think it's much worse to have the same information in two different
places where it can cause inconsistencies that are hard to see and may
not be repeatable. If git ever finds the wrong merge base (because,
say, the generation numbers are wrong), I want it to be a *repeatable*
thing. I want to be able to repeat on the git mailing list "hey, guys,
look at what happens when I try to merge commits ABC and XYZ". If you
go "yeah, it works for me", then that is bad.

What I tried very hard to do in the git data structures is to make
them (a) immutable (so the DAG could never have two-way links, for
example) and (b) "simple".

Right now, we do *have* a "generation number". It's just that it's
very easy to corrupt even by mistake. It's called "committer date". We
could improve on it.

Are packfiles unclean, or a random hack? How about pack indices?

No. Neither of them are unclean or random. The original git design was
very much about thinking of the object space as a "filesystem". Now,
the original object layout actually used the native OS filesystem, and
I naively thought that would be ok. Using  aspecialized filesystem
instead doesn't really change anything. It's not fundamentally
different from the difference between running git on ext3 or btrfs or
nfs or whatever. In fact, I think we've had more filesystem-related
bugs wrt NFS than we've had with pack-files.

The pack indices are actually kind of ugly - and I would have
preferred having them in the same file instead of having the worry of
consistency across two different files. They *are* the kind of thing
that could cause local inconsistency, but they are fairly simple, and
they have some serious protection in them (ie they aren't just SHA1'd
in themselves, they contain a SHA1 of the pack-file they index in them
to make sure that any inconsistency is findable). Again, that's
"redundancy". But I consider the packfile/index to be just a
filesystem. It really fundamentally *is* that.

Partly for that reason, I do think that if the generation count was
embedded in the pack-file, that would not be an "ugly" decision. The
pack-files have definitely become "core git data structures", and are
more than just a local filesystem representation of the objects:
they're obviously also the data transport method, even if the rules
there are slightly different (no index, thank god, and incomplete
"thin" packs).

That said, I don't think a generation count necessarily "fits" in the
pack-file. They are designed to be incremental, so it's not very
natural there. But I do think it would be conceptually prettier to
have the "depth of commit" be part of the "filesystem" data than to
have it as a separate ad-hoc cache.

Those things rely on the idea that the git DAG is a data model that we
present to the user, but that we're allowed to do things behind the
scenes to make things faster.

.. and that is relevant to this discussion exactly *how*?

It's not. It's totally irrelevant. I certainly would never walk away
from the DAG model. It's a fundamental git decision, and it's the
correct one.

But it all boils down to one simple issue: we should have added
generation counts back in 2005. It's likely the *one* data format
decision that I regret. Using commit dates was wrong. Everybody knew
it was wrong, but we ended up going with it just to keep the format
constant.

If I had realized how small the patch was to add generation counters,
and that it wouldn't have broken backwards compatibility (ie fsck
doesn't start complaining). I would have done it originally, instead
of all the crazy hacks we did for commit date verification.

And that is what this discussion fundamentally boils down to for me.

If we should have fixed it in the original specification, we damn well
should fix it today. It's been "ignorable" because it's just not been
important enough. But if git now adds a fundamental cache for them,
then that information is clearly no longer "not important enough".

                               Linus

On Fri, 2011-07-15 at 16:33 +0100, Long, Martin wrote:

quoted

Firstly, I presume the generation number would not form part of the
SHA1 calculation? No? Cool.

I suspect this may be where my suggestion falls down. Though I suspect
there is a case for object metadata which doesn't form part of the
SHA. Would generation number tampering be a concern?

If you take Jeff's perspective on the purpose of generation numbers
(representing metadata about the DAG in a more readily-available format)
then "tampering" is not really a concern as the metadata is merely local
(to the running instance of Git) ephemera that we can cache between runs
for the sake of efficiency. Linus' perspective on generation numbers
seems to be of a more hard and fast type of data.

So, are we really talking about [corpus] generation numbers (used to
describe the state of the DAG in the way one describes his known family
tree) or are we talking about _revision_numbers_ (used to describe the
commit, as Subversion does)? I think we've got two (or more) groups
talking about different things (and aims) and trying to use the same
words to do so.

Caching offers the ability to store that metadata, to provide the same
performance gain, but maintain the integrity of the SHA chain.
However, it does still leave the generation number liable to
tampering, meaning a generic non-SHA metadata solution might be
better.

I'm not sure where you are going with this. I wouldn't think "tampering"
with _current_DAG-based ephemera would do much other than create a
performance hit. If you are really talking about a static
_revision_number_ then that belongs in the commit, where it cannot be
changed (and may be completely meaningless when taken out of context, as
SVN revision numbers are). What such a number may entail is probably up
for discussion, but perhaps in a different thread.

TBH, there are few situations where historical generations are useful
- finding gen numbers of tags is one of them. Most cases are going to
be for new commits, and in that case, a few new commits at the tip of
each branch will very quickly reduce the number of traversals. What
use case would really create enough traversals that it should be a
performance concern?

The answer to this is found in a previous thread
http://article.gmane.org/gmane.comp.version-control.git/176807

(remember, generation number vs. revision number...)

Also, please don't cull the CC list! (Added Geert Bosch)

-- 
-Drew Northup
________________________________________________
"As opposed to vegetable or mineral error?"
-John Pescatore, SANS NewsBites Vol. 12 Num. 59

On Fri, Jul 15, 2011 at 09:10, Linus Torvalds
[off-list ref] wrote:

Right now, we do *have* a "generation number". It's just that it's
very easy to corrupt even by mistake. It's called "committer date". We
could improve on it.

...

If I had realized how small the patch was to add generation counters,
and that it wouldn't have broken backwards compatibility (ie fsck
doesn't start complaining). I would have done it originally, instead
of all the crazy hacks we did for commit date verification.

What about going forward making the requirement that a new commit must
have a committer date whose date is >= the maximum date of its
parents?

We could also add a check during fast-forward merges to refuse to
perform the merge if the incoming commit has a committer date too far
forward in the future (e.g. more than 5 minutes). If you pull from a
moron whose system clock is set such that the committer date isn't a
proxy for generation number, Git would just refuse the merge, and you
could ask them to fix their objects.

-- 
Shawn.

On Fri, Jul 15, 2011 at 9:18 AM, Shawn Pearce [off-list ref] wrote:

What about going forward making the requirement that a new commit must
have a committer date whose date is >= the maximum date of its
parents?

So you suggest just making commit dates be the generation number.

I'd be ok with that. It's basically what we've been doing for the last
six years.

But in that case, we shouldn't be doing the generation count cache either.

Btw, I do agree that we probably should add a warning for the case
("your clock is wrong - your commit date is before the commit date of
your parents") and maybe require the use of "-f" or something to
override it. That would certainly be a good thing quite independently
of anything else. So regardless of generation counts, it's probably
worth it.

But if you think commit date is good enough for generation counts -
and I'm not arguing against it - then please tell me why you would
then want to have a separate generation count cache.

So I would like to repeat: I think our commit-date based hack has been
pretty successful. We've lived with it for years and years. Even the
"let's try to fix it by adding slop" code is from three years ago
(commit 7d004199d1), which means that for three years we never really
saw any serious problems. I forget what problem we actually did see -
I have this dim memory of it being Ted that had problems with a merge
because git picked a crap merge base, but that may just be my
Alzheimer's speaking.

Obviously there are cases where we miss some merge base and it doesn't
really end up mattering, so we may well have a *ton* of commits that
have bad dates, but they just haven't affected us enough for us to
care. That's fine too - I dislike how our algorithm isn't truly
reliable, but at the same time I think we're so robust that it all
works regardless.

So I think it's ugly and fairly hacky, but it has worked well enough
in practice. I dislike our commit dates, but I don't _hate_ them. I do
think it was a mistake, but not one I'm especially ashamed of.

So why do I dislike the generation count cache so much? I dislike it
exactly because

  "if the commit date isn't good enough, then dammit, we should have
just added a generation count".

And if we should have added it six years ago, then we should add it
today. Not say "oh, we made a mistake six years ago, let's work around
the mistake instead of fixing it".

That's really what it boils down to. Let's not paper over a mistake.
Either we need the generation depth or we don't. And if we do need it,
we should replace the date-based hackery with it (where "replace" may
well be "still fall back on our traditional date-based hackery in the
absense of generation counters").

But if we decide that we don't really need generation counters AT ALL,
and can just continue with the commit date hack, then I'm personally
ok with that too.

So to me, it's a "either or" situation. Either the commit dates are
good enough, or we should add generation counts to the commits.

But in *neither* case is it ok to do some external cache to work around it.

                          Linus

On Fri, Jul 15, 2011 at 09:44:21AM -0700, Linus Torvalds wrote:

So I would like to repeat: I think our commit-date based hack has been
pretty successful. We've lived with it for years and years. Even the
"let's try to fix it by adding slop" code is from three years ago
(commit 7d004199d1), which means that for three years we never really
saw any serious problems. I forget what problem we actually did see -
I have this dim memory of it being Ted that had problems with a merge
because git picked a crap merge base, but that may just be my
Alzheimer's speaking.

My original main issue was simply that "git tag --contains" and "git
branch --contains" was either (a) incorrect, or (b) slower than
popping up gitk and pulling the information out of the GUI.  The
reason for (b) is because of gitk.cache.

Maybe the answer then is creating a command-line tool (it doesn't have to
be in "core" of git) which just pulls the dammned information out of
gitk.cache....

(Yes, it's gross, but I'm not worrying about the long-term
architecture of git or anything high-falutin' like that.  I'm just a
poor dumb user who just wants git tag --contains and git branch
--contains to be fast and accurate...)

						- Ted

On Fri, Jul 15, 2011 at 9:44 AM, Linus Torvalds
[off-list ref] wrote:

Btw, I do agree that we probably should add a warning for the case
("your clock is wrong - your commit date is before the commit date of
your parents") and maybe require the use of "-f" or something to
override it. That would certainly be a good thing quite independently
of anything else. So regardless of generation counts, it's probably
worth it.

What if my clock is wrong in the opposite direction - set to some time
out in 2025.
It would pass the check you propose and let the commit go in - but would
cause problems for everyone if that tree was pulled into upstream.

You'd also want a check in pull(merge) that none of the commits being
added were in the future (as defined by the time on your machine).

-Tony

On Fri, Jul 15, 2011 at 11:46 AM, Tony Luck [off-list ref] wrote:

What if my clock is wrong in the opposite direction - set to some time
out in 2025.
It would pass the check you propose and let the commit go in - but would
cause problems for everyone if that tree was pulled into upstream.

I think Shawn suggested that we just notice it at merge time.

But yes, it's why (a) I'd suggest we have a "-f" to override and (b) I
do think that generation counts are a better idea. You could still
screw them up, but it would be due to an outright bug or malicious
behavior, rather than simple incompetence on the part of a user.

Incompetent users (where "date on the machine set to the wrong
century" is just _one_ sign of incompetence) are something git should
pretty much take for granted. It may not be the common case, but it's
certainly something we should design for and take into account.

In contrast, if somebody *wants* to screw his repository up by
re-writing objects with "git hash-object" etc, be my guest. We should
just make sure fsck catches anything serious.

So I would suggest checking the date regardless of any generation
count issues, because it would possibly find badly configured machines
that should be fixed. The same way we complain when we find no name.

Whether it should then be a correctness issue or not is kind of separate.

You'd also want a check in pull(merge) that none of the commits being
added were in the future (as defined by the time on your machine).

I don't think you need to care about "none of the commits", just
making sure the tip is reasonable. That would not only be expensive,
and not what we normally do (we show the diff against endpoints, not
all changes, etc). It would also cause problems for "fixed"
repositories (ie anything that has historical dates that are wrong,
but are ok now).

                  Linus

On Fri, Jul 15, 2011 at 11:42 AM, Ted Ts'o [off-list ref] wrote:

My original main issue was simply that "git tag --contains" and "git
branch --contains" was either (a) incorrect, or (b) slower than
popping up gitk and pulling the information out of the GUI.  The
reason for (b) is because of gitk.cache.

With "original issue" I actually meant the case that caused us to add
the "slop" commit (7d004199d1). But I was too lazy to try to find the
archives from March 2008..

                  Linus

On Fri, Jul 15, 2011 at 09:10:48AM -0700, Linus Torvalds wrote:

I think it's much worse to have the same information in two different
places where it can cause inconsistencies that are hard to see and may
not be repeatable. If git ever finds the wrong merge base (because,
say, the generation numbers are wrong), I want it to be a *repeatable*
thing. I want to be able to repeat on the git mailing list "hey, guys,
look at what happens when I try to merge commits ABC and XYZ". If you
go "yeah, it works for me", then that is bad.

Having the information in two different places is my concern, too. And I
think the fundamental difference between putting it inside or outside
the commit sha1 (where outside encompasses putting it in a cache, in the
pack-index, or whatever), is that I see the commit sha1 as somehow more
"definitive". That is, it is the sole data we pass from repo to repo
during pushes and pulls, and it is the thing that is consistency-checked
by hashes.

So if there is an inconsistency between what the parent pointers
represent, and what the generation number in "outside" storage says,
then the outside storage is wrong, and the parent pointers are the right
answer. It becomes a lot more fuzzy to me if there is an inconsistency
between what the parent pointers represent, and what the generation
number says.

How should that situation be handled? Should fsck check for it and
complain? Should we just ignore it, even though it may cause our
traversal algorithms to be inaccurate? Like clock skew, there's not much
that can be done if the commits are published.

Those are serious questions that I think should be considered if we are
going to put a generation header into the commit object, and I haven't
seen answers for them yet.

Partly for that reason, I do think that if the generation count was
embedded in the pack-file, that would not be an "ugly" decision. The
pack-files have definitely become "core git data structures", and are
more than just a local filesystem representation of the objects:
they're obviously also the data transport method, even if the rules
there are slightly different (no index, thank god, and incomplete
"thin" packs).

That said, I don't think a generation count necessarily "fits" in the
pack-file. They are designed to be incremental, so it's not very
natural there. But I do think it would be conceptually prettier to
have the "depth of commit" be part of the "filesystem" data than to
have it as a separate ad-hoc cache.

Sure, I would be fine with that. When you say "packfile", do you mean
the the general concept, as in it could go in the pack index as opposed
to the packfile itself? Or specifically in the packfile? The latter
seems a lot more problematic to me in terms of implementation.

quoted

Those things rely on the idea that the git DAG is a data model that we
present to the user, but that we're allowed to do things behind the
scenes to make things faster.

.. and that is relevant to this discussion exactly *how*?

Because keeping the generation information outside of the DAG keeps the
model we present to the user simple (and not just the user; the
information that we present to other programs), but lets git still use
the information without calculating it from scratch each time. Just like
we present the data as a DAG of loose objects via things like "git
cat-file", even though the underlying storage inside a packfile may be
very different. I just don't see those two ideas as fundamentally
different.

It's not. It's totally irrelevant. I certainly would never walk away
from the DAG model. It's a fundamental git decision, and it's the
correct one.

Of course not. I never suggested we should.

And that is what this discussion fundamentally boils down to for me.

If we should have fixed it in the original specification, we damn well
should fix it today. It's been "ignorable" because it's just not been
important enough. But if git now adds a fundamental cache for them,
then that information is clearly no longer "not important enough".

OK, so let's say we add generation headers to each commit. What happens
next? Are we going to convert algorithms that use timestamps to use
commit generations? How are we going to handle performance issues when
dealing with older parts of history that don't have generations?

Again, those are serious questions that need answered. I respect that
you think the lack of a generation header is a design decision that
should be corrected. As I said before, I'm not 100% sure I agree, but
nor do I completely disagree (and I think it largely boils down to a
philosophical distinction, which I think you will agree should take a
backseat to real, practical concerns). But it's not 2005, and we have a
ton of history without generation numbers. So adding them now is only
one piece of the puzzle.

What's your solution for the rest of it?

-Peff

On Fri, Jul 15, 2011 at 03:48:07PM -0400, Jeff King wrote:

OK, so let's say we add generation headers to each commit. What happens
next? Are we going to convert algorithms that use timestamps to use
commit generations? How are we going to handle performance issues when
dealing with older parts of history that don't have generations?

Again, those are serious questions that need answered. I respect that
you think the lack of a generation header is a design decision that
should be corrected. As I said before, I'm not 100% sure I agree, but
nor do I completely disagree (and I think it largely boils down to a
philosophical distinction, which I think you will agree should take a
backseat to real, practical concerns). But it's not 2005, and we have a
ton of history without generation numbers. So adding them now is only
one piece of the puzzle.

What's your solution for the rest of it?

I just read some of your later emails to others in the thread. It seems
like your answer is "assume the timestamp-based limiting is good enough
for old history".

I'm OK with that. It obviously falls down in a few specific situations,
but certainly has not been an unbearable problem for the past 5 years.

-Peff

On Fri, Jul 15, 2011 at 12:48 PM, Jeff King [off-list ref] wrote:

Having the information in two different places is my concern, too. And I
think the fundamental difference between putting it inside or outside
the commit sha1 (where outside encompasses putting it in a cache, in the
pack-index, or whatever), is that I see the commit sha1 as somehow more
"definitive". That is, it is the sole data we pass from repo to repo
during pushes and pulls, and it is the thing that is consistency-checked
by hashes.

Sure. That is also the data that is the same for everybody.

That's a big deal, in the sense that it's the only thing we should
rely on if we want consistent behavior. Immediately if core
functionality starts using any other data, behavior becomes "local".
And I think that's really *really* dangerous.

Sure, we have "local behavior" in a lot of small details. We very much
intentionally have it in the ref-logs, and since branches and tags are
local we also have it in things like "--decorate", which obviously
depends on exactly which local refs you have.

We also have local behavior in things like .git/config etc files, so
git can behave very differently for different people even with what is
otherwise an identical repository.

So local behavior is good and expected for some things. We *want* it
for things like colorization decisions, we want it for aliases, and we
want it for branch naming.

But really core behavior shouldn't depend on local information. I
think it would be wrong if something like a merge base decision would
be based on any local information.

For example, should it matter whether something is packed or not? I
really don't think so. That's a pretty random implementation detail,
and if we get different end results because some commit happens to be
packed, vs not packed (because, say, we'd be hiding generation
information in the pack) that would be wrong.

Now, we do have things like merge resolution caches etc (which
obviously do save and use local information again), but I think that's
pretty well clarified.

So if there is an inconsistency between what the parent pointers
represent, and what the generation number in "outside" storage says,
then the outside storage is wrong, and the parent pointers are the right
answer. It becomes a lot more fuzzy to me if there is an inconsistency
between what the parent pointers represent, and what the generation
number says.

So I really don't see why you harp on that. If the generation counters
are in the objects THEY BY DEFINITION CANNOT BE INCONSISTENT.

That's a big issue.

Sure, they may be LYING, but that's a different thing entirely. They
will be lying to everybody consistently. There would never be any
question about what the generation number of a commit is.

See what I'm trying to say? There's no way that they would cause
different behavior for different people. Everything is 100%
consistent.

The exact same thing is true of commit dates, btw. They may be
confused as hell, and they may cause us to do bad things when we
traverse the history, but different clocks on different machines will
still not cause git to act differently on different machines. There's
no possibility of inconsistency.

(Of course, different *versions* of git may traverse the history
differently, since we've changed the heuristics over time. So we do
have that kind of inconsistent behavior, where we give different
results from different versions of git).

And btw, having "incorrect" data in the git objects is not the end of
the world. You can generate merge commits that simply have the wrong
parents. That will be confusing as hell to the user, and it will make
future merges not work very well, but it's a bug in the archive, and
that's "ok". The developers may not be very happy about it. In fact,
afaik we've had a few cases like that in the kernel tree, because
early git had bugs where it would not properly forget parents after a
failed merge. Most of them are ARM-related, because the ARM tree was
one of the first users of git (outside of me, but I had fewer issues
with what happens when things go wrong).

So I would not be *too* shocked if we'd end up with "odd" generation
counts due to some odd bug. It sounds unlikely, but my point is that
that is not at all what I'd *worry* about.

How should that situation be handled? Should fsck check for it and
complain? Should we just ignore it, even though it may cause our
traversal algorithms to be inaccurate? Like clock skew, there's not much
that can be done if the commits are published.

Right. I simply think it's not a big deal.

IOW, if we would rely on generation counts instead of clock dates,
maybe the generation counts would have occasional problems too, but I
suspect they'd be *much* rarer than time-based issues, because at
least the generation count is a well-defined number rather than a
random thing we pick out of emails and badly maintained machines.

That said, I'm not 100% sure at all that we want generation numbers at
all. Their use is pretty limited. If we had had them from the
beginning, I think we would simply have replaced the date-based commit
list sorting with a generation-number-based one, and it should have
been possible to guarantee that we never output a parent before the
commit in rev-parse.

As it is, I have to admit that looking at it, I shudder at changing
the current date-based logic and replacing it with a "date or
generation number".

The date-based one, despite all its fuzziness and not being very well
defined ("Global clock in a distributed system? You're a moron") and
up being a *nice* heuristic for certain human interaction. So it's not
a wonderful solution from a technical standpoint, but it does have (I
think) some nice UI advantages.

(For an example of that: using "--topo-sort" for revision history may
be a very good thing technically, but even if it wasn't for the fact
that it's more expensive, I think that our largely time-based default
order for "git log" in many ways is a better interface for humans. Of
course, when mixed with actually giving a history graph, that changes,
because then you want the "related" commits to group together, rather
than by time. So I think it's just basically a fuzzy area, without any
clear hard rules - which is probably why using that fuzzy timestamp
works so well in practice)

Those are serious questions that I think should be considered if we are
going to put a generation header into the commit object, and I haven't
seen answers for them yet.

I do agree that the really *big* question is "do we even need it at
all". I do like perhaps just tightening the commit timestamp rules.
Because I do think they would probably work very well for the
"contains" problem too.

With the exact same fuzzy downsides, of course. Timestamps aren't
perfect, and they need that annoying fuzz factor thing.

quoted

That said, I don't think a generation count necessarily "fits" in the
pack-file. They are designed to be incremental, so it's not very
natural there. But I do think it would be conceptually prettier to
have the "depth of commit" be part of the "filesystem" data than to
have it as a separate ad-hoc cache.

Sure, I would be fine with that. When you say "packfile", do you mean
the the general concept, as in it could go in the pack index as opposed
to the packfile itself? Or specifically in the packfile? The latter
seems a lot more problematic to me in terms of implementation.

I was thinking the "general" issue - it might make most sense to put
them in the index.

quoted

If we should have fixed it in the original specification, we damn well
should fix it today. It's been "ignorable" because it's just not been
important enough. But if git now adds a fundamental cache for them,
then that information is clearly no longer "not important enough".

OK, so let's say we add generation headers to each commit. What happens
next? Are we going to convert algorithms that use timestamps to use
commit generations? How are we going to handle performance issues when
dealing with older parts of history that don't have generations?

So I do think the _initial_ question need to be the other way around:
do we have to have generation numbers at all?

I think it's likely a design misfeature not to have them, but
considering that we don't, and have been able to make do without for
so long, I'm also perfectly willing to believe that we could speed up
"contains" dramatically with the same kind of (crazy and inexact)
tricks we use for merge bases.

(Looking at a profile, a third - and the top entry - of the "git tag
--contains" profile cost is just in "clear_commit_marks()" - not doing
any real work, rather *undoing* the work in order to re-do things. So
it's entirely possible that the real issue is simply that
"in_merge_bases()" is badly done, and we could speed things up a lot
independently of anything else).

For example, for the "git tag --contains" thing, what's the
performance effect of just skipping tags that are much older than the
commit we ask for?

                Linus

On Fri, Jul 15, 2011 at 02:17:26PM -0700, Linus Torvalds wrote:

quoted

Having the information in two different places is my concern, too. And I
think the fundamental difference between putting it inside or outside
the commit sha1 (where outside encompasses putting it in a cache, in the
pack-index, or whatever), is that I see the commit sha1 as somehow more
"definitive". That is, it is the sole data we pass from repo to repo
during pushes and pulls, and it is the thing that is consistency-checked
by hashes.

Sure. That is also the data that is the same for everybody.

That's a big deal, in the sense that it's the only thing we should
rely on if we want consistent behavior. Immediately if core
functionality starts using any other data, behavior becomes "local".
And I think that's really *really* dangerous.

Yes, I see your argument. I just don't think it's all that big a deal,
because the information is so easily derived from data that _is_ the
same for everybody (and when you _do_ want it to be different locally,
because you are grafting, that is easy to do).

But I think at this point we have both said all there is to say. There
is no actual data to be brought forth in this argument, and we obviously
disagree on this point. So I think we may have to agree to disagree.

And as I said before, I am willing to concede generation numbers in the
commit header. But we need the rest of the solution, too.

So I really don't see why you harp on that. If the generation counters
are in the objects THEY BY DEFINITION CANNOT BE INCONSISTENT.

That's a big issue.

Sure, they may be LYING, but that's a different thing entirely. They
will be lying to everybody consistently. There would never be any
question about what the generation number of a commit is.

See what I'm trying to say? There's no way that they would cause
different behavior for different people. Everything is 100%
consistent.

Read my email again. I am clearly talking about inconsistency between
two data items in the sha1-checked DAG itself. You then proceed to yell
at me that they are not inconsistent, now talking about inconsistency
between different people with the same DAG, but different caches. In
other words, you are talking about an entirely different type of
inconsistency. And then you proceed to say that the generation numbers
may be lying, which is _exactly_ what I meant when I said inconsistency.

I don't mind arguing with you, even if I think you use capital letters
too frequently; but when you do use them, please take care that I really
am being a bonehead, and it is not you misrepresenting what I said.

As to lying (aka inconsistency between items within the DAG), you say:

And btw, having "incorrect" data in the git objects is not the end of
the world. You can generate merge commits that simply have the wrong
parents. That will be confusing as hell to the user, and it will make
future merges not work very well, but it's a bug in the archive, and
that's "ok". The developers may not be very happy about it. In fact,
afaik we've had a few cases like that in the kernel tree, because
early git had bugs where it would not properly forget parents after a
failed merge. Most of them are ARM-related, because the ARM tree was
one of the first users of git (outside of me, but I had fewer issues
with what happens when things go wrong).

No, it's not the end of the world. I just think it's worse than the
possibility of inconsistency between two users' idea of the graph,
because the bug stays with you for all of history, instead of getting
fixed with a new version of git.

That said, I'm not 100% sure at all that we want generation numbers at
all. Their use is pretty limited. If we had had them from the
beginning, I think we would simply have replaced the date-based commit
list sorting with a generation-number-based one, and it should have
been possible to guarantee that we never output a parent before the
commit in rev-parse.

As it is, I have to admit that looking at it, I shudder at changing
the current date-based logic and replacing it with a "date or
generation number".

The date-based one, despite all its fuzziness and not being very well
defined ("Global clock in a distributed system? You're a moron") and
up being a *nice* heuristic for certain human interaction. So it's not
a wonderful solution from a technical standpoint, but it does have (I
think) some nice UI advantages.

That is the conclusion I am coming to, also. I don't find the external
cache as odious as you obviously do. But that was why I posted the
patches with an RFC tag. I wanted to see how painful people found the
concept. But if it's too ugly a concept, I think the path of least
resistance is just making timestamps suck less (by using more consistent
and robust skew avoidance[1] in our various algorithms, and by perhaps
taking more care to notify the user of skew early, before commits are
published).

And then we don't really need generation numbers anymore.  As elegant as
they might have been if they were there from day one, it's just not
worth the hassle of maintaining the dual solution.

[1] We use "N slop commits" in some places and "allow 86400 seconds of
    skew" in other places. We should probably use both, and apply them
    consistently.

quoted

Those are serious questions that I think should be considered if we are
going to put a generation header into the commit object, and I haven't
seen answers for them yet.

I do agree that the really *big* question is "do we even need it at
all". I do like perhaps just tightening the commit timestamp rules.
Because I do think they would probably work very well for the
"contains" problem too.

With the exact same fuzzy downsides, of course. Timestamps aren't
perfect, and they need that annoying fuzz factor thing.

Yeah. But in practice, that fuzz is really easy to implement, has worked
pretty well so far, and doesn't actually hurt performance measurably,
because skew is rare, and a constant, small timestamp tends to equate to
a constant, small number of commits.

quoted

Sure, I would be fine with that. When you say "packfile", do you mean
the the general concept, as in it could go in the pack index as opposed
to the packfile itself? Or specifically in the packfile? The latter
seems a lot more problematic to me in terms of implementation.

I was thinking the "general" issue - it might make most sense to put
them in the index.

If we were to go the cache route, I think I am leaning that way, too, if
only because we don't duplicate the 20-byte sha1 per commit, which keeps
our I/O down.

quoted

OK, so let's say we add generation headers to each commit. What happens
next? Are we going to convert algorithms that use timestamps to use
commit generations? How are we going to handle performance issues when
dealing with older parts of history that don't have generations?

So I do think the _initial_ question need to be the other way around:
do we have to have generation numbers at all?

No, we don't need them. My "contains" patches were already implemented
using timestamps, and it's pretty fast. They fall down only in the face
lying timestamps (i.e., skew). The whole reason to switch to generation
headers was that we could assume they would be correct, and our
algorithms using them would be more likely to be correct.

And I do think a generation header would be more likely to be correct
than a timestamp, if only because timestamps are harder to get right.

I think it's likely a design misfeature not to have them, but
considering that we don't, and have been able to make do without for
so long, I'm also perfectly willing to believe that we could speed up
"contains" dramatically with the same kind of (crazy and inexact)
tricks we use for merge bases.

Already done. I can point you to the patches if you want.

For example, for the "git tag --contains" thing, what's the
performance effect of just skipping tags that are much older than the
commit we ask for?

It's as fast as using generations. See these two patches:

  http://article.gmane.org/gmane.comp.version-control.git/150261

  http://article.gmane.org/gmane.comp.version-control.git/150262

-Peff

On Fri, Jul 15, 2011 at 2:17 PM, Linus Torvalds
[off-list ref] wrote:

For example, for the "git tag --contains" thing, what's the
performance effect of just skipping tags that are much older than the
commit we ask for?

Hmm.

Maybe there is something seriously wrong with this trivial patch, but
it gave the right results for the test-cases I threw at it, and passes
the tests.

Before:

   [torvalds@i5 linux]$ time git tag --contains v2.6.24 > correct

   real	0m7.548s
   user	0m7.344s
   sys	0m0.116s

After:

   [torvalds@i5 linux]$ time ~/git/git tag --contains v2.6.24 > date-cut-off

   real	0m0.161s
   user	0m0.140s
   sys	0m0.016s

and 'correct' and 'date-cut-off' both give the same answer.

The date-based "slop" thing is (at least *meant* to be - note the lack
of any extensive testing) "at least five consecutive commits that have
dates that are more than five days off".

Somebody should double-check my logic. Maybe I'm doing something
stupid. Because that's a *big* difference.

                     Linus

On Fri, Jul 15, 2011 at 4:10 PM, Linus Torvalds
[off-list ref] wrote:

Maybe there is something seriously wrong with this trivial patch, but
it gave the right results for the test-cases I threw at it, and passes
the tests.

Before:

I have fewer branches than tags, but I get something similar for "git
branch --contains":

  [torvalds@i5 linux]$ time git branch --contains v2.6.12 | sha1sum
  9d4224eec98ec7b0bcd5331dfa5badb9ef1fd510  -

  real	0m4.205s
  user	0m4.112s
  sys	0m0.084s
  [torvalds@i5 linux]$ time ~/git/git branch --contains v2.6.12 | sha1sum
  9d4224eec98ec7b0bcd5331dfa5badb9ef1fd510  -

  real	0m0.112s
  user	0m0.100s
  sys	0m0.008s

ie identical results, except one took 4.2s and with the patch it took 0.1s.

This is all hot-cache, of course, and on a fast machine.

                    Linus

And one last comment:

On Fri, Jul 15, 2011 at 4:16 PM, Linus Torvalds
[off-list ref] wrote:

I have fewer branches than tags, but I get something similar for "git
branch --contains":

The time-based heuristic does seem to be important. If I just remove
it, I get increasingly long times for things that aren't contained in
my branches.

And in fact, I think that is why the code used the merge-base helper
functions - not because it wanted merge bases, but because the merge
base stuff will work from either end until it decides things aren't
relevant any more. Because *without* the time-based heuristics, the
trivial "is this a descendant" algorithm ends up working very badly
for the case where the target doesn't exist in the branches. Examples
of NOT having a date-based cut-off, but just doing the straightforward
(non-merge-base) ancestry walk:

  time ~/git/git branch --contains v2.6.12
  real	0m0.113s

  [torvalds@i5 linux]$ time ~/git/git branch --contains v2.6.39
  real	0m3.691s

and what ends up happening is that in the latter case, every branch
walks all the way to the root and checks every commit (walking all the
merges too). While in the first case, it's very quick because it will
find that particular commit when it walk straight backwards (so it
doesn't even have to do a lot of recursion - the first branch that
hits that commit will be a success), so it won't have to look at all
the side ways of getting there.

Of course, the above particular difference happens to be due to the
"depth-first" implementation working well for the thing I am searching
for.  But it does show that the date-based cut-off matters due to
traversal issues like that.

                          Linus

On Fri, Jul 15, 2011 at 04:10:23PM -0700, Linus Torvalds wrote:

On Fri, Jul 15, 2011 at 2:17 PM, Linus Torvalds
[off-list ref] wrote:

quoted

For example, for the "git tag --contains" thing, what's the
performance effect of just skipping tags that are much older than the
commit we ask for?

Hmm.

Maybe there is something seriously wrong with this trivial patch, but
it gave the right results for the test-cases I threw at it, and passes
the tests.

Before:

   [torvalds@i5 linux]$ time git tag --contains v2.6.24 > correct

   real	0m7.548s
   user	0m7.344s
   sys	0m0.116s

After:

   [torvalds@i5 linux]$ time ~/git/git tag --contains v2.6.24 > date-cut-off

   real	0m0.161s
   user	0m0.140s
   sys	0m0.016s

and 'correct' and 'date-cut-off' both give the same answer.

Without even looking carefully at your patches for any minor mistakes, I
can tell you that the speedup you're seeing is approximately right.
Because it's almost exactly the same optimization I made in my
timestamp-based patches (links to which I sent you earlier today).

However, you can make it even faster. The "tag --contains" code will ask
"is_descendant_of" repeatedly for the same set of "want" commits. So you
end up traversing some parts of the graph over and over. My patches
share the marks over a set of contains traversals, so you only ever
touch each commit once. And that's what my patches do.

With yours, on my box:

  $ time git tag --contains HEAD~1000 >/dev/null
  real    0m0.113s
  user    0m0.104s
  sys     0m0.008s

and mine:

  $ time git tag --contains HEAD~1000 >/dev/null
  real    0m0.035s
  user    0m0.020s
  sys     0m0.012s

I suspect you can make the difference even more prominent by having more
tags, or by having multiple "want" commits.

-Peff

On Fri, Jul 15, 2011 at 04:36:40PM -0700, Linus Torvalds wrote:

On Fri, Jul 15, 2011 at 4:16 PM, Linus Torvalds
[off-list ref] wrote:

quoted

I have fewer branches than tags, but I get something similar for "git
branch --contains":

The time-based heuristic does seem to be important. If I just remove
it, I get increasingly long times for things that aren't contained in
my branches.

And in fact, I think that is why the code used the merge-base helper
functions - not because it wanted merge bases, but because the merge
base stuff will work from either end until it decides things aren't
relevant any more. Because *without* the time-based heuristics, the
trivial "is this a descendant" algorithm ends up working very badly
for the case where the target doesn't exist in the branches. Examples
of NOT having a date-based cut-off, but just doing the straightforward
(non-merge-base) ancestry walk:

  time ~/git/git branch --contains v2.6.12
  real	0m0.113s

  [torvalds@i5 linux]$ time ~/git/git branch --contains v2.6.39
  real	0m3.691s

Yes, exactly. That is why my first patch (which goes to a recursive
search), takes about the same amount of time as "git rev-list --all"
(and I suspect your 3.691s above is similar). And then the second one
drops that again to .03s.

I think you are simply recreating the strategy and timings I have posted
several times now.

-Peff

On Fri, Jul 15, 2011 at 8:42 PM, Ted Ts'o [off-list ref] wrote:

On Fri, Jul 15, 2011 at 09:44:21AM -0700, Linus Torvalds wrote:

quoted

So I would like to repeat: I think our commit-date based hack has been
pretty successful. We've lived with it for years and years. Even the
"let's try to fix it by adding slop" code is from three years ago
(commit 7d004199d1), which means that for three years we never really
saw any serious problems. I forget what problem we actually did see -
I have this dim memory of it being Ted that had problems with a merge
because git picked a crap merge base, but that may just be my
Alzheimer's speaking.

My original main issue was simply that "git tag --contains" and "git
branch --contains" was either (a) incorrect, or (b) slower than
popping up gitk and pulling the information out of the GUI.  The
reason for (b) is because of gitk.cache.

Maybe the answer then is creating a command-line tool (it doesn't have to
be in "core" of git) which just pulls the dammned information out of
gitk.cache....

(Yes, it's gross, but I'm not worrying about the long-term
architecture of git or anything high-falutin' like that.  I'm just a
poor dumb user who just wants git tag --contains and git branch
--contains to be fast and accurate...)

If  "git tag --contains" and "git branch --contains" give incorrect
answers because the commiter date is wrong in some commits, then why
not use "git replace" to "change" the commiter date in the commits
that have a wrong date? Is it because you don't want to use "git
replace", or because there is no script to do it automatically, or is
there another reason?

Thanks,
Christian.

On Sat, Jul 16, 2011 at 11:16:45AM +0200, Christian Couder wrote:

If  "git tag --contains" and "git branch --contains" give incorrect
answers because the commiter date is wrong in some commits, then why
not use "git replace" to "change" the commiter date in the commits
that have a wrong date? Is it because you don't want to use "git
replace", or because there is no script to do it automatically, or is
there another reason?

That would work. There are a few tricky things, though:

  1. Most commits have less than 100 skewed commits. But some have many
     (e.g., thousands in the mesa repo). How well does git cope with
     large numbers of replace refs, performance-wise?

  2. Declaring which commits are skewed is actually tricky. You can find
     a commit whose timestamp is less than the timestamp of one of its
     ancestors. But you don't know whether it is skewed, or the
     ancestor.

     If you are implementing a list of commits whose timestamps
     shouldn't be used for traversal cutoff, it doesn't really matter
     who is _right_; you just care about whether the timestamps are
     strictly increasing from that point.

     But once you start replacing commits, you need to put in a
     reasonable value for the timestamp. So you may well be replacing a
     perfectly valid commit with one that has bogus, skewed information
     in the commit timestamp.

  3. Any value you put in is actually going to be a lie during things
     like "git log --pretty=raw". That may be OK. But it is letting an
     optimization meant to make traversal fast and accurate bleed into
     the actual data we show the user.

  4. Sometimes we need to do traversals on the real objects (e.g.,
     because we are doing upload-pack). To get the benefit, those
     traversals would presumably need to look at both the original
     object and the replacement, use the timestamp from the replacement
     for traversal, but otherwise use the original object.

-Peff

On Monday 18 July 2011 05:41:06 Jeff King wrote:

On Sat, Jul 16, 2011 at 11:16:45AM +0200, Christian Couder wrote:

quoted

If  "git tag --contains" and "git branch --contains" give incorrect
answers because the commiter date is wrong in some commits, then why
not use "git replace" to "change" the commiter date in the commits
that have a wrong date? Is it because you don't want to use "git
replace", or because there is no script to do it automatically, or is
there another reason?

That would work. There are a few tricky things, though:

  1. Most commits have less than 100 skewed commits. But some have many
     (e.g., thousands in the mesa repo). How well does git cope with
     large numbers of replace refs, performance-wise?

If it did not cope well, it should be possible to improve the performance.

Anyway, another way to fix the problem with "git replace" could be to create 
branches with commits that have a fixed commiter date and then to use "git 
replace" only to connect these branches to the graph.

For example if you have this:

A - B - X1 - X2 - X3 - C - D

where X1, X2 and X3 are skewed, then you can create this:

A - B - X1 - X2 - X3 - C - D
         \ Y1 - Y2 - Y3

where Y1, Y2, Y3 are the same as X1, X2, X3 except they are not skewed.
Then you only need to do "git replace X3 Y3" so you create only one replace 
ref.

  2. Declaring which commits are skewed is actually tricky. You can find
     a commit whose timestamp is less than the timestamp of one of its
     ancestors. But you don't know whether it is skewed, or the
     ancestor.

     If you are implementing a list of commits whose timestamps
     shouldn't be used for traversal cutoff, it doesn't really matter
     who is _right_; you just care about whether the timestamps are
     strictly increasing from that point.

     But once you start replacing commits, you need to put in a
     reasonable value for the timestamp. So you may well be replacing a
     perfectly valid commit with one that has bogus, skewed information
     in the commit timestamp.

Perhaps but with "git replace" you can choose to create new replace refs and 
deprecate the old replace refs to fix this where you got it wrong.

It would be easier to do that if "git replace" supported sub directories like 
"refs/replace/clock-skew/ted-july-2011/", so you could manage the replace refs 
more easily.

For example you could create new refs in "refs/replace/clock-skew/ted-
july-2011-2/" if you found a better fix. And then use these new refs instead of 
those in "refs/replace/clock-skew/ted-july-2011/".

  3. Any value you put in is actually going to be a lie during things
     like "git log --pretty=raw". That may be OK. But it is letting an
     optimization meant to make traversal fast and accurate bleed into
     the actual data we show the user.

With replace refs, the user could choose the "lies" told to him/her by 
selecting the replace refs or set of replace refs that are used.

As commits are immutable, when they are created with bad data, the best we can 
do is let the user choose if they want to see the original or another "fixed" 
version. Because the original will always be "true" in a way.

  4. Sometimes we need to do traversals on the real objects (e.g.,
     because we are doing upload-pack). To get the benefit, those
     traversals would presumably need to look at both the original
     object and the replacement, use the timestamp from the replacement
     for traversal, but otherwise use the original object.

Yeah, or maybe when we do traversals on real objects we could afford not to 
rely on commiter date or some other "fragile" data.

Thanks,
Christian.

On Tue, Jul 19, 2011 at 06:14:38AM +0200, Christian Couder wrote:

quoted

     But once you start replacing commits, you need to put in a
     reasonable value for the timestamp. So you may well be replacing a
     perfectly valid commit with one that has bogus, skewed information
     in the commit timestamp.

Perhaps but with "git replace" you can choose to create new replace refs and 
deprecate the old replace refs to fix this where you got it wrong.

It would be easier to do that if "git replace" supported sub directories like 
"refs/replace/clock-skew/ted-july-2011/", so you could manage the replace refs 
more easily.

I think all of the arguments I cut from your email are reasonable, but
the crux of the issue comes down to this point.

If you are interested in actually correcting the skew, then yes, replace
refs are a good solution. But doing so is going to involve somebody
looking at the commits and deciding which ones are wrong, and what they
should be. And maybe that's a good thing to do for people who really
care about cleaning history.

But for something like "speed up revision traversal by assuming commit
timestamps are roughly increasing", we want something very automated,
and what is needs to say is much weaker (not "this is what this commit
_should_ say", but rather "this commit might be right, but it is not a
good point for cutting off a traversal"). So that's a much easier
problem, and it's easy to do in an automated way.

So I think while you could use replace refs to handle this issue, it is
not always going to be the right solution, and there is room for
something simpler (and weaker).

-Peff

On Tue, Jul 19, 2011 at 10:00 PM, Jeff King [off-list ref] wrote:

On Tue, Jul 19, 2011 at 06:14:38AM +0200, Christian Couder wrote:

quoted

Perhaps but with "git replace" you can choose to create new replace refs and
deprecate the old replace refs to fix this where you got it wrong.

It would be easier to do that if "git replace" supported sub directories like
"refs/replace/clock-skew/ted-july-2011/", so you could manage the replace refs
more easily.

I think all of the arguments I cut from your email are reasonable, but
the crux of the issue comes down to this point.

If you are interested in actually correcting the skew, then yes, replace
refs are a good solution. But doing so is going to involve somebody
looking at the commits and deciding which ones are wrong, and what they
should be.

I think that we can help the user a lot to find the skew, and then to
decide which commits are wrong, and then to fix the skew even if the
fix we suggest is far from being perfect.

And maybe that's a good thing to do for people who really
care about cleaning history.

Yeah, so maybe at one point we will want to help these people even if
we have implemented automatic generation numbers. Then this means that
automated generation numbers are useful only if:

1) there are commits with skews
2) the heuristics to deal with some skew don't work
3) the user is too lazy to use the help we (can) provide to fix the skews

I think that we can probably find heuristics that will deal with at
least 95% of the cases. For example we could perhaps decide that we
don't cut off a traversal until the date difference is greater than 5
days.

Then in the hopefully few cases where there are really big skews that
won't be caught by our heuristics, (but that we can automatically
detect when fetching or commiting,) we can perhaps afford to ask the
user to do a small analysis to properly fix the skew.

I mean that at one point when things are too weird it is ok and
perhaps even a good thing to involve the user.

But for something like "speed up revision traversal by assuming commit
timestamps are roughly increasing", we want something very automated,
and what is needs to say is much weaker (not "this is what this commit
_should_ say", but rather "this commit might be right, but it is not a
good point for cutting off a traversal"). So that's a much easier
problem, and it's easy to do in an automated way.

Yeah, generation numbers look like an easy thing to do. And yeah,
being automated is great too. But it does not mean it is the right
thing to do. (Or perhaps we could have them but not save them in any
cache, nor in the commit object.)

So I think while you could use replace refs to handle this issue, it is
not always going to be the right solution, and there is room for
something simpler (and weaker).

You know, replace refs can be used to fix or improve a lot of things
like bad authors, clock skews, bisecting on a fixed up history,
working on a larger or smaller repository than the original, and so
on. And of course for each of these problems you may find another
solution tailored to the problem at hand that will seem simpler or
easier. But in the end if you develop all these other solutions you
will have developed a lot of stuff that will be harder to maintain,
less generic, more complex and so on, that properly developed replace
refs.

Thanks,
Christian.