Re: Git commit generation numbers

There are a few design mistakes in git. The way the object type and size are prefixed to the data for hasing purposes, which prevents aligned fetching from memory-mapped data in the hashing code, isn't too pretty either.

But git has generally preferred to avoid storing information that can be recomputed. File renames are the big example. given this, why the heck store generation numbers?

They *can* be computed on demand, so arguably they *should*. Cacheing is then an optimization, just like packs, pack indexes, the hashed object storage directories, and all that.

I'm in the "make it a cache" camp, honestly.  

For example, here's a different possible generation number scheme. By making the generation number a cache, it becomes a valid alternative to experiment with.

Simply store a topologically sorted list of commits. Each commit's position can serve as a generation number, and is greater than the positions of all ancestors. But by using the offset within the list, the number is stored implicitly.

Generation numbers don't have to be consecutive as long as they're correctly ordered, so you could, e.g. choose to make them unique.

I don't think this is actually worth it; I'm just using it as a not-completely-insane example of a different design that nonetheless achieves the same goal.

Why freeze this in the object format?

Because if you put it in the object format, then it gets pushed and pulled around, thereby putting generation numbers in every clone.

I'm starting to think put them in the object store, for exactly that reason, and to start moving repositories in a direction where the look more like they would if this had been done correctly from the start.

Then, because some operations are still going to create a lot of traversals, a cache is always an option to improve the performance in that area.

On Sun, Jul 17, 2011 at 11:27 AM, George Spelvin <linux@horizon.com> wrote:

Why would you ever care? That makes no sense.

Guys, please don't bring up file renames. I explained once already why bringing up file renames just makes you look like a f^&% moron.

Let me explain one more time:

 - Storing file renames is STUPID. It's stupid for very fundamental
reasons that have absolutely *NOTHING* to do with "it can be computed
later".

It's fundamentally stupid because it will FOREVER SCREW UP YOUR DATA, and because it will make merging an unmitigated disaster and make your repository depend on how you *created* your data, rather than on what the data is. It will totally break the situation of one person doing a rename, while another person does something else to the metadata (eg a create of the same filename).

Trying to track file identities will leave to very fundamentally unsolvable issues like "which file identity do we choose when two different files get the same name", or "which file identity will we choose when one file splits in two".

Git doesn't track renames, because unlike pretty much every other SCM out there, git really does have a good design, and because I damn well understood the real problems.

So bringing it up as an example of "we don't store it because we can compute it" is really totally idiotic. It's a sign of not understanding the problems with renames. Stop doing it. That argument is totally irrelevant. Really.

It's like saying "We shouldn't do generation numbers because fish don't use bicycles". The only thing that kind of argument does is to make me convinced that you don't understand the problem enough to be worth even arguing with. It is not only a worthless argument, but it makes your every other argument suspect.

Comprende? Stop it.

Umm, no.

That's actually a really bad argument.

There are valid things that we "should" do, but they have nothing to do with "if something can be done, it should be done". That's just a crazy argument.

A thing we really *should* do is perform well. And be really reliable. And support a distributed workflow.

Those are real arguments that aren't about "just because it's there".

Now, some of those arguments can then be used to say "don't bother storing redundant data". For example, redundant data takes disk space and network bandwidth, and if something can be recomputed cheaply (ie if it doesn't have a negative impact on performance), then redundant data is just bad.

And what appears like a much better argument (right now) is that some data isn't needed AT ALL, because you can make do with other data entirely (ie dates).

But "just because we could recompute it" is a bad bad reason.

The thing is, the very basic design of git is all about *incomplete* DAG traversal. The DAG traversal part is pretty obvious and simple, but the *partial* thing really is very very important. We absolutely need it for reasonable scalability. We've spent a *lot* of time in git development on trying to perform really well by avoiding work. Not just in revision traversal, but in many other areas too (like making diff and merge much faster by being able to handle whole identical recursive subdirectories by just checking the SHA1, for example).

That's a *really* fundamental design issue in git. Performance was always a primary goal. And by primary, I really mean primary. As in "more important than just about anything else". There were other primary goals, but really not very many.

And there really aren't very good ways to limit DAG traversal. Generation numbers are one of the very few fundamental ones. We hacked around it with dates, and it works pretty well in practice (well enough that I'm certainly ok with the hack), but it's definitely one of the areas where git simply does something "wrong". It's simply not a entirely reliable algorithm, and that fact makes me a bit uncomfortable with it.

(Now, in theory, a global *approximate* time is theoretically possible in a distributed environment, and as such it's arguable that "global time with a slop that is based on the speed of light and knowledge of location" is at least theoretically sound. So the real problem with commit dates is that people simply don't have good clocks. So it's a practical problem rather than a theoretical one, and it's a practical problem that doesn't really cause enough problems in practice to not be workable. But I'm making excuses for it, and I _know_ I'm making excuses for it, so I'm not really happy about it)

And it's just about the only area where I am aware of git doing something "wrong". Which is why I would like to have had generation numbers even though the dates do work.

Anyway, to get back to the actual issue of caching vs not caching: if you think "we could compute it dynamically" means that we should, then we damn well shouldn't cache it either - why cache it, when you could just compute it. And if it's worth it to waste resources on the cache in order to avoid performance issues, then it damn well would be ok to waste (fewer) resources on just saving the generation number in the object data base. And make that *fundamental* fix to a hack that git has had since pretty much day one.

And btw, git didn't have the date-based hack originally, because I didn't think it would be problematic enough. I thought that we could do universally efficient partial DAG traversal - not having to go all the way to the root - based purely on the DAG. The code in "everybody_uninteresting()" tries to be that "limit DAG traversal by only looking at the DAG itself", and it works for many simple situations. But it turns out that it does *not* work for many other cases.

So the generation number really is very very fundamnetal. It's absolutely not some "additional information that can be computed", because the whole AND ONLY point of having the number is to not compute it.

We are never interested in the generation number for its own sake. We are only interested in it in order to avoid having to look at the rest of the DAG.

So no, the number fundamentally isn't computable, because computing it obviates the need for it.

                           Linus

You're making my point and somehow not seeing it.

What you're describing here is the archetpical cache.

The only reason for having a memory cache is to avoid accessing memory! The only reason for having a TLB is to avoid walking the page tables! The only reason for having a page cache is to avoid hitting the disk! The only reason for having a dcache is to avoid traversing the file system directories!

And yes, the only reason for having a generation number cache is to avoid traversing the DAG. D'oh. Do you think this is somehow news to anyone?

The fundamental nature of a cache is that it lets you look something up quickly that you could compute but don't want to.

I'm slapping my forehead like Homer Simpson here. The fact that computing the generation number is expensive is why it's worth cacheing. But the fact that it *can* be computed is a reason not to clutter the published commit object format with it.

The generation number is NOT FUNDAMENTAL. It contains no information that's not already in the DAG. The danger of putting it into a commit is that you'll do it wrong, and thereby screw everything up.

If we have broken code that generates a broken cache, we fix the code and the bugs magically go away.

If we have broken code that generates a broken commit object, we have a huge problem.

Just like we don't ship pack indexes around, but recompute them on arrival. The index is essential for performance, but it's absolutely non-essential for correctness.

As a general design principle, the exported data structures, like the commits, should be as simple as possible. Do not include extraneous or redundant data, because then you have to deal with the possibility of inconsistency. This leads to bugs. (Frequently buffer overflow bugs.)

Maybe it would have been worth violating that principle during the initial git design. I still see a good argument for not doing that even if we had a time machine.

But now that the commit format is established and widely used, the argument has far more force. Changing the commit format provides zero functionality gain, and the performance gain can be obtained a different way.

Maybe a bit more code, but nothing extraordinary.

To me, the KISS principle says "don't change the commit format!"

Now, you complain about code complexity. But this is a read-only cache. The generation number of a commit object never changes. There's no update operation. Like an I-cache, if there's ever any problem, throw it away.

Arguing that "the patch to put it in the commit object is smaller" is stupidly short-sighted. Now every version of git from now until forever has to support both kinds of commit objects. (And browsing old git trees will forever be slow.)

You only take on that sort of legacy support burden if you absolutely have to.

Bull puckey.  You're ugly and stupid and WRONG.

It's an excellent reason. I'm amazed that you're not seeing it. The principle is "don't include redundant data in a transport format." Because it can be recomputed, it's redundant. Therefore, it shouldn't be included in the transport format.

It's exactly the same principle as "don't store the indexes in the database dump" and "don't store filename hashes in file system archives".

This is a principle, not an iron-clad rule. It can be violated for good and sufficient reasons, notably performance.

But in this case, we can get the performance without it. Without, in fact, changing the git transport format at all.

And "don't change a widely-used transport format" is ANOTHER important principle. Backward-compatible is much better than incompatible, but far better to avoid changing it at all.

Breaking two such principles without an absolutely iron-clad reason is ugly and stupid and wrong.

(As you well know, the more general principle is "don't store redundant data AT ALL unless you need to for performance". Redundant data is A Bad Thing. It can get out of sync. But if you have to, a private cache is much better than a exchange format.)

Put another way, it IS stupid, it IS expendable, and therefore it SHOULD go.

On Sun, Jul 17, 2011 at 4:39 PM, George Spelvin <linux@horizon.com> wrote:

And I'm slapping *my* forehead.

Nobody has *ever* given a reason why the cache would be better than just making it explicit.

That's my issue.

Why is that so hard for people to understand? The cache is just EXTRA WORK.

To take your TLB example: it's like having a TLB for a page table that would be as easy to just create in a way that it's *faster* to look up in the actual data structure than it would be to look up in the cache.

Or to take your disk cache example: wouldn't you say that a disk cache is a F&*&ING BAD IDEA if it is slower than the disk it caches?

Seriously.

                    Linus

I thought I listed a few.  Let me be clearer.

1) It involves changing the commit format.  Since the change is
   backward-compatible, it's not too bad, but this is still fundamentally
   A Bad Thing, to be avoided if possible.

2) It can't be retrofitted to help historical browsing.

3) You have to support commits without generation numbers forever.
   This is a support burden.  If you can generate generation numbers for
   an entire repository, including pre-existing commits, you can *throw
   out* the commit date heuristic code entirely.

4) It can't be made to work with grafts or replace objects.

5) It includes information which is redundant, but hard to verify,
   in git objects.  Leading to potentially bizarre and version-dependent
   behaviour if it's wrong.  (Checking that the numbers are consistent
   is the same work as regenerating a cache.)

6) It makes git commits slightly larger.  (Okay, that's reaching.)

That's why it *might* have been a good idea to include the number in the original design. But now that the design is widely deployed, it's better to avoid changing the design if not necessary.

With a bit of extra work, it's not necessary.

You've subtly jumped points. The original point was that it's worth precomputing and storing the generation numbers. I was trying to say that this is fundamentally a caching operation.

Now we're talking about *where* to store the cached generation numbers.

Your point, which is a very valid one, is that they are to be stored on disk, exactly one per commit, can be computed when the commit is generated, and are accessed at the same time as the commit, so it makes all kinds of sense to store them *with* the commits. As part of them, even.

This has the huge benefit that it does away with the need for a *separate* data structure. (Kinda sorts like the way AMD stores instruction boundaries in the L1 I-cache, avoiding the need for a separate data structure.)

I'm arguing that, despite this annoying overhead, there are valid reasons to want to store it separately. There are some practical ones, but the basic one is an esthetic/maintainability judgement of "less cruft in the commit objects is worth more cruft in the code".

Git has done very well partly *because* of the minimality of its basic persistent object database format. I think we should be very reluctant to add to that without a demonstrated need that *cannot* be met in another way.

In this particular case, a TLB is not a transport format. It's okay to add redundant cruft to make it faster, because it only lasts until the next reboot. (A more apropos, software-oriented analogy might be "struct page".)

A git commit object *is* a transport format, one specifically designed for transporting data a very long way forward in time, so it should be designed with considerable care, and cruft ruthlessly eradicated.

Whatever you add to it has to be supported by every git implementation, forever. As does every implementation bug ever produced.

A cache, on the other hand, is purely a local implementation detail. It can be changed between versions with much less effort.

I agree it's more implementation work. But the upside is a cleaner struct commit. Which is a very good thing.

On 18-jul-2011, at 07:13, George Spelvin wrote:

Git is designed to ignore data in this case afaik, so I do not see any reason why backwards-compatibility gets broken here.

I like to see more (valid) arguments, as I do not see what you are trying to explain.

I'll give you a few months to rethink at this statement until this feature does get used widely. I think there was never a moment where we would ever think to rebuild older commits as this would break the hash of the commits where many people are potential looking for.

The data is *consistent* as long as the hash doesn't change, storing the data in the commits *can* reduce resource and makes calculations cheaper. Therefore, I think there are enough reasons to add the generation number in the commit. Yes, many data can be calculated or can be an overhead, but as Torvalds already said, it can be used as consistency check.

If the data does get wrong, then its probably caused by something stupid enough to break the rules. Yes, this is a problem but I think there are already enough reasons given, look back to the archives of this topic.

Ok, there is one possible thing that *can* go wrong and that is when you are changing history with generation numbers with an older git client.

(And thats a good reason to communicate with others as clear as possible about this feature, but its still not version-dependent as it doesn't require a client to use it)

A cache would use more resources because they can become invalid at any point and *should* be recalculated by every client. We are processing data that *can* be reused by everybody with a git client which has this specific feature, but does not break anything with an older client.

So please, calculate things only once as this may save a *lot* of time :-)

I would see more advantage in a cache if the data could differs on every client, but that still doesn't mean that you should use one.

Maybe I shouldn't even have responded to this as I tend not to agree with the given opinions to use a cache, even when I think that Torvalds starts throwing arguments as well for certain reasons, but thats probably my wrong thinking at it.

That's what I just wrote. "The change is backward-compatible" is a simpler and shorter way of writing "it doesn't break backwards-compatibility" (to put the generation number in the commit object).

I just said that *any* change is still undesirable.

I apologize for being unclear. I meant that if you store the generation in the commit, then you can't add generation numbers to an existing repository ("retrofit") in order to speed up --contains and --topo-sort operations on pre-existing git repositories.

(Without recomputing all the hashes and breaking the ability to merge with people not using the feature.)

As Linus points out, this is not likely to be a major performance issue in practice, as operations like finding merge bases overwhelmingly use recent objects (which will have generation numbers once the feature goes in), but it is a measurable disadvantage.

I'm afraid that your English grammar is sufficiently mangled here that I don't understand *your* point. Which is a shame because it's one of my more important points.

Storing the generation number inside the commit means that a commit with a generation number has a different hash than a commit without one. This means that people won't want to break the hashes of existing commits by adding them. In many cases, ever.

Which means that git will have to be able to work without the generation numbers forever.

If the generation numbers are stored in a separate data structure that can be added to an existing repository, then a new version of git can do that when needed. Which lets git depend on always having the the generation numbers to do all history walking and stop using commit date based heuristics completely.

You're mixing up two issues. Storing the generation number *anywhere* can make calculations cheaper. Storing them in the commit is indeed the *simplest* place, but the calculation cost point is equally true if the numbers are stored somewhere else.

As for consistency...

I'm defining "consistent" as consistency between the generation number and the parent pointers. This is the property that the history-walking optimizations depend on.

A commit's generation number is consistent if it is larger than the generation number of any of its parents. (Optionally, you may require that it be larger by exatly 1.)

A generation number is *not* consistent if is less than or equal to the generation number of one of its parents.

If this happens, history walking code that uses the generation numbers will not produce correct output.

Further, the nature of the incorrectness will depend on implementation details ("potentially bizarre and version-dependent behaviour") of the history-walking code.

By computing the generation numbers when needed, the entire "what happens if someone makes a commit with an inconsistent generation number" problem goes away. It goes from "not likely to happen" or "somthing that has to be checked for when receiving objects" to "can't happen".

The computation to verify that an incoming commit's generation number is consistent is exactly the same computation needed to compute the generation number it should have: look up all parent commit generation numbers and take the maximum. The only question is whether we store the result after computing it, or compare with the included generation number and possibly print an error message.

For example, suppose I generate a commit with a generation number of UINT_MAX. Will this crash git? That's a new error condition the code has to worry about. If I generate the generation number locally, I know that can't happen in any repository that I can download in a reasonable period of time.

If we had generation numbers from day 1, we could just require that they always be checked, and an inconsistent object could be always rejected.

But since old git versions ignore the generation number in commits, a bad generation number could spread a long way before someone notices it. It becomes a visible problem. Not a really big one (I'm pretty sure that refusing to pull it introduces no security holes), but it's an error condition that we have to actually think about.

This is silly. The cache can't become invalid except by disk corruption, which can corrupt numbers stored in the commit object just the same. (The corruption can be detected by git-fsck, but that's also true independent of where the numbers are stored.)

And the work to recalculate the numbers is far less than the work to garbage collect, or repack, or generate the index of an incoming pack, or any of a dozen operations that are normally done by all clients. (Don't get me started on rename detection!)

This is a completely misplaced optimization. Walking every commit in the repository takes a few seconds and enough memory that we don't want to do it every "git log" operation, but it's barely perceptible compared to other repository maintenance operations.

Do it once when you install a new git software version and then you can forget about it.

If you use grafts or replace objects, it can be. That's my point 4) above. Supporting these makes maintaining a cache trickier, but it's simply impossible to do with in-commit generation numbers.

On Mon, 18 Jul 2011, George Spelvin wrote:

I've been diverting myself from $day_job by reading through this thread. Still, I couldn't make my mind between having the generation number stored in the commit object or in a separate cache by reading all the arguments for each until now. Admittedly I'm not as involved in the design of Git as I once was, so my comments can be considered with the same proportions.

Obviously, with a perfect design, we would have had gen numbers from the beginning. But we did mistakes, and now have to regret and live with them (and yes I have my own share of responsibility for some of those regrets which are now embodied in the Git data format).

To me this is the killer argument. Being able to forget about the broken date heuristics entirely and simplify the code is what makes the external cache so fundamentally better as it can be applied to any existing repositories. And it has no backward compatibility issues as old Git version won't work any worse if they can't make any usage of that cache.

The alternative of having to sometimes use the generation number, sometimes use the possibly broken commit date, makes for much more complicated code that has to be maintained forever. Having a solution that starts working only after a certain point in history doesn't look eleguant to me at all. It is not like having different pack formats where back and forth conversions can be made for the _entire_ history.

And if you don't care about graft/replace then the cached data is immutable just like the in-commit version would, so there is no consistency issues. If you do care about graft/replace (or who knows what other dag alteration scheme might be created in 5 years from now) then a separate cache will be required _anyway_, regardless of any in-commit gen number.

So to say that if a generation number is _really_ needed, then it should go in a separate cache. Saying that if we would have done it initially then it would have been inside the commit object is not a good enough justification to do it today if it can't be applied to the whole of already existing repositories and avoid special cases.

I however have not formed any opinion on that fundamental question i.e. whether or not gen numbers are worth it in today's conditions. Neither did I think about the actual cache format (I don't think that adding it to the pack index is a good idea if grafts are to be honored) which certainly has bearing on that fundamental question too.

But I don't see the point of starting to add them now to commit objects, even if we regret not doing it initially, simply because having them appear randomly based on the Git version/implementation being used is still much uglier than some ad hoc cache or even not having them at all.

Nicolas

It seemed like a pretty strong argument to me, too.

A possible workaround would be to keep track of the largest generation number skew introduced by any graft, and add that safety factor into the history-walking code, but that would be painful if you replace a single large commit with an equivalent long development history, such as adding a historical development tree behind a recently-cut-off one. or development history You can do a workaround at the expense of ine

I was thinking of something very close to the V2 pack format. http://book.git-scm.com/7_the_packfile.html A magic number, a 256-entry fanout table, a sorted list of 20-byte hashes, followed by a matching list of 4-byte generation numbers.

Ending with a 20-byte hash of the replaces and grafts state that this cache is valid for, and a hash of the cache itself.

A bit of code factoring should make it easy to share much of the code.

It would certainly be possible to share the SHA1 table in an existing pack index and store the generation numbers of the base (no replacement) case, but you'd have to store null values for all the non-commit objects.

That takes 4 bytes per object, while a separate list of commits takes 24 bytes per commit. A separate list is better if commits are less than 1/6 of all objects.

Looking at git's own object database, we have:
 66125 blobs   (45.50%)
 49292 trees   (33.92%)
 29554 commits (20.33%)
   362 tags    ( 0.25%)
145333 total

So we're actually a bit over the 16.66% optimum. but it's not far enough to be a real efficiency problem.

On Wed, 20 Jul 2011, George Spelvin wrote:

except that you then have different caches on different systems. If the generation number is part of the repository then it's going to be the same for everyone.

in either case, you still have the different heristics depending on what version of git someone is running

David Lang

On Wed, 20 Jul 2011, david@lang.hm wrote:

So what?

The actual generation number will be, and has to be, the same for everyone with the same repository content, regardless of the cache used. It is a well defined number with no room to interpretation.

Indeed.

Nicolas

On 07/20/2011 07:36 PM, Nicolas Pitre wrote:

Nonsense.

Even if the generation number is well-defined and shared by all clients, the only quasi-essential definition is "for each A in ancestors_of(B), gen(A) < gen(B)".

In practice, the actual generation number *will be the same* for everyone with the same repository content, unless and until someone develops a different calculation method. But there is no reason to require that the number *has to be* the same for everyone unless you expect (or require) everyone to share their gen-caches.

Surely there will be a competent and efficient gen-cache API. But most code can just ask if B --contains A or even just use rev-list and benefit from the increased speed of the answer. Because most code doesn't really care about the gen numbers themselves, but only the speed of determining ancestry.

Phil

On Wed, 20 Jul 2011, Phil Hord wrote:

and I think this is why Linus is not happy with a cache. He is seeing this as something that has significantly more value if it is going to be consistant in a distributed manner than if it's just something calculated locally that can be different from other systems.

if it's just locally generated, then I could easily see generation numbers being different on different people's ssstems, dependin on the order that they see commits (either locally generated or pulled from others)

If it's part of the commit, then as that commit gets propogated the generation number gets propogated as well, and every repository will agree on what the generation number is for any commit that's shared.

I agree that this consistancy guarantee seems to be valuable.

in that case, why bother with generation numbers at all? the improved data based heristic seems to solve that problem.

David Lang

On Wed, Jul 20, 2011 at 17:18,  <david@lang.hm> wrote:

But this should only happen if the user fudges with their Git sources and makes Git produce a different generation number.

If the algorithm is always "gen(A) = max(gen(P) for each parent_of(A))
+ 1" then it doesn't matter who merged what commits, the same commit
appears at the same part of the graph relative to all of its
ancestors, and therefore always has the same generation number. This
is true whether or not the commit contains the generation number.

This isn't really as beneficial as you are making it out to be. We already can agree on what the generation number should be for any given commit, if you topo-sort the commit DAG, you get the same result.

Its valuable, but its consistent either with a cache, or not.

On 07/20/2011 08:37 PM, Shawn Pearce wrote:

Interesting. I was going to disagree with the latter part of your statement, but then I realized you're right.

And that your algorithm allows duplicate generation numbers.

And that there's nothing wrong with that.

Because it meets the one quasi-essential need, "for each A in ancestors_of(B), gen(A) < gen(B)".

I still fail to see the value.

Phil

On Wed, 20 Jul 2011, Shawn Pearce wrote:

I have to think about this more, but I'm wondering about cases where the same result ia achieved via different methods, something along the lines of one person developing something with _many_ commits (creating a large generation number) that one person merges far sooner than another, causing the commits that they do after the merge to have much larger generation numbers than someone making the same changes, but doing the merge later

something like

   C9
    \
C2 - C10 - C11 - C12

vs
                 C9
                   \
C2 - C3 - C4 - C5 - C10

where the C10-12 in the first set and C3-5 in the second set are completely unrelated to what's done in C9 and C12 in the first set and C10 in the sedond set are identical trees.

now I know that part of a commit is what it's parents are, so that is different (and that may be enough to say that generations don't matter and this entire issue is moot), but I haven't thought about it long enough to convince myself what would (or should) happen in these cases.

David Lang

On <david@lang.hm> wrote:

Can't happen. Using the basic algorithm as Shawn described, the generation number is defined uniquely by the ancestor DAG.

The generation number is the length of the longest path to a root (zero-ancestor) commit through the DAG.

If you look at past discussion, several people have thought it was okay to bake into the commit precsiely because it can be computed once and will never change.

However, git does have some ability to amend the history DAG after it's been written, using grafts and replace objects. These can change generation numbers, presisely because they change the DAG.

The generation numbers in the above are as follows:
First example:
	C2 = C9 = 0
	C10 = 1 = max(C2, C9) + 1
	C11 = 2 = C10 + 1
	C12 = 3 = C11 + 1

Second example:
	C2 = C9 = 0
	C3 = 1 = C2 + 1
	C4 = 2 = C2 + 1
	C5 = 3 = C4 + 1
	C10 = 4 = max(C5, C9) + 1

Now, the history pruning works fine if the "+1" is replaced my any other non-zero increment, but it's not clear why you'd bother.

George Spelvin, could you please try not mangle CC to include only emails, stripping names (e.g. "spearce@spearce.org" instead of "Shawn Pearce <spearce@spearce.org>")?

"George Spelvin" <linux@horizon.com> writes:

There is also another issue that I have mentioned, namely incomplete clones - which currently means shallow clone, without access to full history.

Nb. grafts are so horrible hack that I would be not against turning off generation numbers if they are used.

In the case of replace objects you need both non-replaced and replaced DAG generation numbers.

As far as history walking is concerned, you can just consider "missing parent" the same as "no parent" and start the generation numbers at 0. As long as you recompute

Yeah, but it's not too miserable to add support (the logic is very similar to replace objects), and then you would be able to have the history walking code depend on the presence of generation numbers. (The "load the cache" function would regenerate it if necessary.)

Only do this if you already have support for "no generation numbers" in the history walking code for (say) loose objects.

Yes, the cache validity/invalidation criteria are the tricky bit. Honestly, this is where the code gets ugly, not computing and storing the generation numbers.

One thought on an expanded generation number cache:

There are many git operations that use ONLY the commit DAG, and do not actually use any information from the commits other than their hashes and parent pointers. The ones that come to mind are rev-parse, rev-list, describe, name-rev, and merge-base.

These could be sped up if, instead of just generation numbers, we kept a complete cached copy of the commit DAG, so the commit objects didn't have to be uncompressed and parsed.

This could be provided by an extended form of generation number cache. In addition to listing the generation number of each commit, it would list all the ancestors (by file offset rather than hash, for compactness). Then simple commit walking could load this cache and avoid unpacking commit objects from packs.

A compact implementation would abuse the flexibility of generation numbers to make them serve double duty. They would be used as offsets into a table of parent pointers. By keeping the table topologically sorted, the offsets would satisfy the requirements for generation numbers, but would be unique, and there would be additional gaps when a commit had multiple parents.

The parent pointers would themselves be 31-bit offsets into the table of SHA-1 hashes, with the msbit meaning "this commit has multiple parents, also look at the following table entry". (If we use offset 0 to mean "no parents", it might be more convenient to have the offset point to the *end* of the run of parents rather than the beginning, so "following" would be earlier in the file, but that's an implementation detail.)

I'm assuming that 2^31 commits having (in aggregate) 2^32 parents would be enough for the time being. As a local cache, it can be extended with a software upgrade. There's no need to ever have support for two formats in any given release; just notice that the cache format is wrong, blow it away, and regenerate it.

On Thu, Jul 21, 2011 at 13:27, George Spelvin <linux@horizon.com> wrote:

Don't assume that. Consider a repository stored on NFS that is read-only to you. The NFS server has one version of Git installed, and is using cache format A. You have a newer version of Git installed on your workstation, using cache format B. Now you cannot use this repository as a local filesystem... its only available to you over the Git protocols. This breaks a number of people's environments. :-)

Its better if we can avoid having to change file formats very often, even if they are a local "cache".

On Thu, 21 Jul 2011, George Spelvin wrote:

Well, shallow clone case can be considered both for putting 'true' generation numbers in commit header, and against it.

For, because with generation numbers in commits you can use true generation numbers.

Against, because if there are commits without generation numbers in header, you cannot assign true generation number, and you can only use "shallow" generation number, in generation numbers cache.

Grafts are non-transferable, and if you use them to cull rather than add
history they are unsafe against garbage collection... I think.
 

BTW. with storing generation number in commit header there is a problem what would old version of git, one which does not understand said header, do during rebase. Would it strip unknown headers, or would it copy generation number verbatim - which means that it can be incorrect?

BTW2. code size comparing in-commit and external cache cases must take into account yet to be written fsck for in-commit generation numbers.

On Fri, 22 Jul 2011, Jakub Narebski wrote:

They would indeed be copied verbatim and become incorrect.

Nicolas

On Fri, 22 Jul 2011, Nicolas Pitre wrote:

how would they become incorrect?

David Lang

On Fri, 22 Jul 2011, David Lang <david@lang.hm> wrote:

Let's assume that the following history was created with new git, one that correcly adds generation number header to commits:

  A(1)---B(2)---C(3)---D(4)---E(5)       <-- master
          \
           \----x(3)---y(4)---z(5)       <-- foo

The numbers are generation numbers in commit object.

Let's assume that this repository is fetched into repository instance that is managed by older git, one that doesn't understand generation header.

Then, if we do

  [old]$ git rebase master foo

and if old git _copies_ generation number header _verbatim_, we would get:

  A(1)---B(2)---C(3)---D(4)---E(5)                         <-- master
                               \
                                \---x'(3)--y'(4)--z'(5)    <-- foo

Those generation numbers are *incorrect*; they should be:

  A(1)---B(2)---C(3)---D(4)---E(5)                         <-- master
                               \
                                \---x'(6)--y'(7)--z'(8)    <-- foo

That is IF unknown headers are copied verbatim during rebase. For "encoding" header this is a good thing, for "generation" it isn't.

On Fri, Jul 22, 2011 at 11:34 AM, Jakub Narebski <jnareb@gmail.com> wrote:

Afaik, they aren't copied verbatim, and never have been. Afaik, the only thing that has *ever* written commits is "commit_tree()" (originally "main()" in commit-tree.c). Why is this red herring even being discussed?

Of course you can always generate bogus commits by writing them by hand. But that's irrelevant.

                     Linus

On Fri, Jul 22, 2011 at 12:06:08PM -0700, Linus Torvalds wrote:

In git.git, that is the case. There are other programs that may write git commits, though. Try:

  http://www.google.com/codesearch#search/&q=hash-object.*commit&type=cs

Many uses seem OK (they are generating a commit from scratch). This one at least (the sixth result from the search above) would actually generate buggy generation headers (it modifies parents but passes other headers through):

  http://www.google.com/codesearch#XUVcT9DKB_U/replace&ct=rc&cd=7&q=hash-object.*commit

It may be worth saying that such code is stupid and ugly and wrong, or that it is not deployed widely enough to care about. But it's not entirely a red herring.

-Peff

On Fri, Jul 22, 2011 at 10:06 PM, Linus Torvalds <torvalds@linux-foundation.org> wrote:

Let's suppose for a moment that the commits do have these wrong generation numbers, shouldn't a fetch on the newer client check these and show an error? But what if they are pushed to a central server that has old version of git? It would be messy.

Hi,

First, let me start out by saying that I'm a fairly new contributor to Git, and I'm far less experienced than the other people on this thread. I've read through all the discussions time and again, and thought about the problem for some time now - I can't say I understand it as fully as many of you do, but I think I may have a slightly different perspective to offer.

In what way is Git fundamentally different from Subversion? It's the simplicity of the data model. From the simplest building block, a key-value store, we have been able to compose and build things on top of it. The reason we built centralized version control systems earlier is because it was *easier* to address the composition problems. We dumped all related repository and problems into one central server. With so much information in one place, things are tightly coupled and problems are easier to solve. Still not convinced? What's the weakest component in Git today? Undoubtedly submodules. Ofcourse, a large part of the reason is that many people don't use submodules, and hence it doesn't improve -- but it's actually a circular problem. People don't use submodules, because it's so featureless and hard to develop. Why is it so hard? Back to the fundamental problem of composition from simple building blocks. In submodules, we have to take entire DAGs and build a composite DAG. The key pieces of information are deep inside Git's fundamnetals: Gitlinks. Other projects try like Gitslave try to attack the problem on a more superficial level, but they all hit a barrier when they discover that they can't compose big blocks of data: you need simple building blocks to compose.

It's the same story with C (and now, Haskell). Why does everyone like C so much? Because it only provides fundamental building blocks and gives people the freedom to compose the way they like. It doesn't provide big "template blocks" like Java, because they tend to be restrictive in the long run. Sure, Java is easier to start out with, but people soon realize that big blocks can't compose.

More than arguing about backward compatibility, and about how older versions of Git commits won't have generation numbers, I think this is what we should be focusing on. Sure, it'll additionally make sense to put in a cache to speed things up now, but we need to think about what Git will be 10~15 years from now. The fundamental pieces of information required for composition must be present in the fundamental building blocks.

The real question we should be asking is: "Should Git have had commit generation numbers in 2005?". If the answer is "yes", we should put them in now before it becomes even harder, bending over backwards for backward compatibility if necessary. Otherwise, we'll regret this decision 10~15 years later, when we're faced with deeper issues. If you want a concrete example, think about how you'd compose DAGs together (again, the submodules problem): where is the information required to prune each DAG and compose?

I wish I could write this in myself, but I'm afraid I don't have the engineering skill yet. I'll be happy to contribute whatever little I can, and participate in the review process.

Thanks.

-- Ram

On Fri, 22 Jul 2011, Jakub Narebski wrote:

commit headers are _not_ copied during rebase

a rebase is not the exact same commit, it's a "logically equivalent" commit.

so when you do a rebase, you change the commit headers (you have to change the parent headers in any case, and you would have to change the generation numbers as well)

this was discussed earlier in this thread.

David Lang

On Fri, 22 Jul 2011, david@lang.hm wrote:

Yes, this turns out to be true as I forgot that rebase is constructed on top of format-patch+am, and format-patch doesn't preserve the ancillary headers such as the existing "encoding" header, or the hypothetical "generation" header.

Nicolas

On Fri, 22 Jul 2011, Jakub Narebski wrote:

Linus has already pointed out that this is safe.

old versions won't create generation numbers, but they will ignore them if they exist. Since commits are not modified after they are created, the old versions don't copy or modify them.

David Lang

On 07/20/2011 08:18 PM, david@lang.hm wrote:

It will only be used locally, so it needn't be consistent with anyone else's.

I can't see why.

Does it? Surely the ruckus would've died down in that case. But I haven't been reading pu.

It seems to me that the main drawback to a gen-cache is that it slows down the first operation after even a local clone (with just hardlinks).

On the other hand, I see too many nails in the distributed-gen-numbers coffin: legacy commits can't catch up (and therefore suffer), and legacy clients can trash or corrupt even "new-style" commits.

Phil

On Wed, 20 Jul 2011, Phil Hord wrote:

Sure.  But what do you gain by making holes in the sequence?

And with the above you clearly reinforced the argument _against_ storing the generation number in the commit object. If you can imagine a different calculation method already, and if it is actually useful, then who knows if something even better could be done eventually.

Nicolas

On 07/20/2011 08:58 PM, Nicolas Pitre wrote:

Depends on the algorithm. Probably speed. Possibly more efficient limited-cache building (jit-style discovery in reverse, as-needed, for example).

What do you gain by enforcing contiguousness? Why not require all gen numbers to be even? Or prime? ;)

Good.  Nice to see I'm being self-consistent, then.

Phil