From: George Spelvin <hidden> Date: 2016-06-15 22:51:36
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.
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?
From: Long, Martin <hidden> Date: 2016-06-15 22:51:36
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 [off-list ref] wrote:
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.
Why would you ever care? That makes no sense.
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?
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.
They *can* be computed on demand, so arguably they *should*.
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
From: George Spelvin <hidden> Date: 2016-06-15 22:51:36
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.
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.
But "just because we could recompute it" is a bad bad reason.
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 [off-list ref] wrote:
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.
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
From: George Spelvin <hidden> Date: 2016-06-15 22:51:36
Nobody has *ever* given a reason why the cache would be better than
just making it explicit.
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.)
Why is that so hard for people to understand? The cache is just EXTRA WORK.
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.
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.
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.
From: Anthony Van de Gejuchte <hidden> Date: 2016-06-15 22:51:36
On 18-jul-2011, at 07:13, George Spelvin wrote:
quoted
Nobody has *ever* given a reason why the cache would be better than
just making it explicit.
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.
Git is designed to ignore data in this case afaik, so I do not see any
reason why backwards-compatibility gets broken here.
2) It can't be retrofitted to help historical browsing.
I like to see more (valid) arguments, as I do not see what you are
trying to explain.
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.
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.
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.)
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)
6) It makes git commits slightly larger. (Okay, that's reaching.)
quoted
Why is that so hard for people to understand? The cache is just EXTRA WORK.
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.
quoted
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.
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.
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.
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
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.
From: George Spelvin <hidden> Date: 2016-06-15 22:51:36
quoted
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.
Git is designed to ignore data in this case afaik, so I do not see any
reason why backwards-compatibility gets broken here.
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.
quoted
2) It can't be retrofitted to help historical browsing.
I like to see more (valid) arguments, as I do not see what you are
trying to explain.
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.
quoted
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.
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.
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.
quoted
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.)
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.
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.
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 :-)
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.
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.
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.
From: Nicolas Pitre <nico@fluxnic.net> Date: 2016-06-15 22:51:37
On Mon, 18 Jul 2011, George Spelvin wrote:
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.
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).
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.
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
From: George Spelvin <hidden> Date: 2016-06-15 22:51:37
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.
It seemed like a pretty strong argument to me, too.
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.
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
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.
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.
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.
It seemed like a pretty strong argument to me, too.
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
From: Nicolas Pitre <nico@fluxnic.net> Date: 2016-06-15 22:51:37
On Wed, 20 Jul 2011, david@lang.hm wrote:
On Wed, 20 Jul 2011, George Spelvin wrote:
quoted
quoted
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.
It seemed like a pretty strong argument to me, too.
except that you then have different caches on different systems.
So what?
If the generation number is part of the repository then it's going to
be the same for everyone.
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.
in either case, you still have the different heristics depending on what
version of git someone is running
From: Phil Hord <hidden> Date: 2016-06-15 22:51:37
On 07/20/2011 07:36 PM, Nicolas Pitre wrote:
On Wed, 20 Jul 2011, david@lang.hm wrote:
quoted
If the generation number is part of the repository then it's going to
be the same for everyone.
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.
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
If the generation number is part of the repository then it's going to
be the same for everyone.
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.
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.
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.
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.
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, [off-list ref] wrote:
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)
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.
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.
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.
I agree that this consistancy guarantee seems to be valuable.
Its valuable, but its consistent either with a cache, or not.
--
Shawn.
From: Phil Hord <hidden> Date: 2016-06-15 22:51:37
On 07/20/2011 08:18 PM, david@lang.hm wrote:
On Wed, 20 Jul 2011, Phil Hord wrote:
quoted
On 07/20/2011 07:36 PM, Nicolas Pitre wrote:
quoted
On Wed, 20 Jul 2011, david@lang.hm wrote:
quoted
If the generation number is part of the repository then it's going to
be the same for everyone.
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.
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.
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.
It will only be used locally, so it needn't be consistent with anyone
else's.
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.
I can't see why.
quoted
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.
in that case, why bother with generation numbers at all? the improved
data based heristic seems to solve that problem.
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
From: Phil Hord <hidden> Date: 2016-06-15 22:51:37
On 07/20/2011 08:37 PM, Shawn Pearce wrote:
On Wed, Jul 20, 2011 at 17:18,[off-list ref] wrote:
quoted
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)
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.
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)".
quoted
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.
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.
quoted
I agree that this consistancy guarantee seems to be valuable.
Its valuable, but its consistent either with a cache, or not.
From: Nicolas Pitre <nico@fluxnic.net> Date: 2016-06-15 22:51:37
On Wed, 20 Jul 2011, Phil Hord wrote:
On 07/20/2011 07:36 PM, Nicolas Pitre wrote:
quoted
On Wed, 20 Jul 2011, david@lang.hm wrote:
quoted
If the generation number is part of the repository then it's going to
be the same for everyone.
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.
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)".
Sure. But what do you gain by making holes in the sequence?
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.
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
From: Phil Hord <hidden> Date: 2016-06-15 22:51:37
On 07/20/2011 08:58 PM, Nicolas Pitre wrote:
On Wed, 20 Jul 2011, Phil Hord wrote:
quoted
On 07/20/2011 07:36 PM, Nicolas Pitre wrote:
quoted
On Wed, 20 Jul 2011, david@lang.hm wrote:
quoted
If the generation number is part of the repository then it's going to
be the same for everyone.
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.
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)".
Sure. But what do you gain by making holes in the sequence?
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? ;)
quoted
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.
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.
Good. Nice to see I'm being self-consistent, then.
Phil
On Thu, 2011-07-21 at 08:55 -0400, George Spelvin wrote:
quoted
I have not read yet one discussion about how generation numbers [baked
into a commit] deal with rebasing, for instance. Do we assign one more
than the revision prior to the base of the rebase operation or do we
start with the revision one after the highest of those original commits
included in the rebase? Depending on how that is done
_drastically_different_ numbers can come out of different repository
instances for the same _final_ DAG. This is one major reason why, as I
see it, local storage is good for generation numbers and putting them in
the commit is bad.
Er, no. Whenever a new commit object is generated (as the result
of a rebase or not), its commit number is computed based on its
parent commits. It is NEVER copied.
I don't see the word "copy" in my original.
B-O1-O2-O3-O4-O5-O6
\
R1----R2-------R3
What's the correct generation number for R3? I would say gen(B)+3. My
reading of the posts made by some others was that they thought gen(O6)
was the correct answer. Still others seemed to indicate gen(O6)+1 was
the correct answer. I don't think everybody MEANT to be saying such
different things--that's just how they appeared on this end.
Now, did you mean something different by "commit number?"
--
-Drew Northup
________________________________________________
"As opposed to vegetable or mineral error?"
-John Pescatore, SANS NewsBites Vol. 12 Num. 59
On Wed, Jul 20, 2011 at 17:18, [off-list ref] wrote:
quoted
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)
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.
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
quoted
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.
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.
quoted
I agree that this consistancy guarantee seems to be valuable.
Its valuable, but its consistent either with a cache, or not.
From: George Spelvin <hidden> Date: 2016-06-15 22:51:38
Drew Northup wrote:
On Thu, 2011-07-21 at 08:55 -0400, George Spelvin wrote:
quoted
I have not read yet one discussion about how generation numbers [baked
into a commit] deal with rebasing, for instance. Do we assign one more
than the revision prior to the base of the rebase operation or do we
start with the revision one after the highest of those original commits
included in the rebase? Depending on how that is done
_drastically_different_ numbers can come out of different repository
instances for the same _final_ DAG. This is one major reason why, as I
see it, local storage is good for generation numbers and putting them in
the commit is bad.
Er, no. Whenever a new commit object is generated (as the result
of a rebase or not), its commit number is computed based on its
parent commits. It is NEVER copied.
I don't see the word "copy" in my original.
Indeed, you didn't use it; it was my simplified mental model of your
suggestion that the rebased commits would have generation numbers that
somehow depended on the generation numbers before rebasing.
Althouugh you suggested something different, the mistake is the same:
the rebased commits' generation numbers have simply no relationship to
those of the original pre-rebase commits. The generation numbers depend
only on the commits explicitly listed as parents in the commit objects.
That's why I went on to explain that the equivalence of the commits
produced by a rebase operation is a higher-level concept; the core git
object database just knows that they aren't identical, and therefore
are different.
Thus, they would retain the same relative order as before the rebase
(unless you permuted them with rebase -i), but start with the generation
number of the rebase target.
B-O1-O2-O3-O4-O5-O6
\
R1----R2-------R3
What's the correct generation number for R3? I would say gen(B)+3. My
reading of the posts made by some others was that they thought gen(O6)
was the correct answer. Still others seemed to indicate gen(O6)+1 was
the correct answer. I don't think everybody MEANT to be saying such
different things--that's just how they appeared on this end.
According to the canonical algorithm, it's gen(B)+3 = gen(R2)+1.
However, any non-decreasing series is equally permissible for
optimizing history walking, so you could add jumps to (for example)
make the numbers unique if that simplified anything.
I don't think it does simplify anything, so the issue hasn't been
discussed much.
For the purpose of the optimization enabled by the generation
numbers, however, it doesn't actually matter.
What matters is that if I am listing commits down multiple branches,
once I have walked back on each branch to commits of generation N or
less, I know that I have found all possible descendants of all commits
of generation N or more.
This lets me display the recent part of the commit DAG (back to generation
N) without exploring the entire commit treem or worrying that I'll have to
"back up" to insert a commit in its proper order. Without precomputed
generation numbers, the only way to be sure of this is to explore back
to generation 0 (parentless commits) or to use date-based heuristics.
Now, did you mean something different by "commit number?"
No, just a bran fart I didn't catch before posting.
I meant "generation number".
From: Phil Hord <hidden> Date: 2016-06-15 22:51:38
On 07/21/2011 11:57 AM, Drew Northup wrote:
On Thu, 2011-07-21 at 08:55 -0400, George Spelvin wrote:
quoted
quoted
I have not read yet one discussion about how generation numbers [baked
into a commit] deal with rebasing, for instance. Do we assign one more
than the revision prior to the base of the rebase operation or do we
start with the revision one after the highest of those original commits
included in the rebase? Depending on how that is done
_drastically_different_ numbers can come out of different repository
instances for the same _final_ DAG. This is one major reason why, as I
see it, local storage is good for generation numbers and putting them in
the commit is bad.
Er, no. Whenever a new commit object is generated (as the result
of a rebase or not), its commit number is computed based on its
parent commits. It is NEVER copied.
I don't see the word "copy" in my original.
B-O1-O2-O3-O4-O5-O6
\
R1----R2-------R3
What's the correct generation number for R3? I would say gen(B)+3.
And you would be correct if you follow the SoP algorithm.
My
reading of the posts made by some others was that they thought gen(O6)
was the correct answer. Still others seemed to indicate gen(O6)+1 was
the correct answer.
Maybe the confusion comes from the different storage mechanisms being
discussed. If the generation numbers are in a local cache and used by a
single client, the determinism of the specific numbers doesn't much
matter. If they are part of the commit, it still doesn't need to be
completely deterministic. However, interoperability requires standards,
and standards favor determinism, so dogmatic determinism may triumph in
that case.
1. gen(06) might make sense if you mean to implement --date-order using
gen-numbers, for example. But I don't think it's practical in any case.
2. gen(06)+1 might make sense if you mean to require that gen-numbers
are unique per repo. But this is both unsupportable and unnecessary, so
it's a non-starter.
3. gen(B)+1 is what you'd get from the the algorithm I saw proposed.
All three of these are provably correct by my definition of "correct":
"for each A in ancestors_of(B), gen(A) < gen(B)".
However, [1] and [2] have some extra features of dubious value. Simpler
is better for interoperability, so I like [3] for this purpose.
Even [3] has an extra feature I think is unnecessary: determinism. If
that "requirement" is dropped, I think all three of these algorithms are
(functionally) roughly equivalent.
I don't think everybody MEANT to be saying such
different things--that's just how they appeared on this end.
Now, did you mean something different by "commit number?"
I remain unconvinced that there is value in gen-number distribution, so
to my mind, the specific algorithm and whether or not it is
deterministic are unimportant.
Phil ~ who wasn't really being asked, but felt like answering
From: George Spelvin <hidden> Date: 2016-06-15 22:51:38
I have not read yet one discussion about how generation numbers [baked
into a commit] deal with rebasing, for instance. Do we assign one more
than the revision prior to the base of the rebase operation or do we
start with the revision one after the highest of those original commits
included in the rebase? Depending on how that is done
_drastically_different_ numbers can come out of different repository
instances for the same _final_ DAG. This is one major reason why, as I
see it, local storage is good for generation numbers and putting them in
the commit is bad.
Er, no. Whenever a new commit object is generated (as the result
of a rebase or not), its commit number is computed based on its
parent commits. It is NEVER copied.
Just like the parent pointers themselves. Remember, even though we talk
about "the same commit" after rebasing, it's really just an EQUIVALENT
commit according to some higher-level concept of similarity. As far
as the core git engine is concerned, it's always a DIFFERENT commit,
with different parent hashes and a different hash itself.
This point hasn't been mentioned explicltly precisely because it's
so obvious; the history-walking code that the generation numbers are
for requires this property to function.
On Wed, 2011-07-20 at 16:26 -0700, david@lang.hm wrote:
On Wed, 20 Jul 2011, George Spelvin wrote:
quoted
quoted
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.
It seemed like a pretty strong argument to me, too.
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.
I keep hearing (reading) people stating this utterly unfounded argument.
The fact is that for any work not yet integrated back into a shared
repository it just isn't true--and even after upstream integration the
truth of such a statement may be limited.
I have not read yet one discussion about how generation numbers [baked
into a commit] deal with rebasing, for instance. Do we assign one more
than the revision prior to the base of the rebase operation or do we
start with the revision one after the highest of those original commits
included in the rebase? Depending on how that is done
_drastically_different_ numbers can come out of different repository
instances for the same _final_ DAG. This is one major reason why, as I
see it, local storage is good for generation numbers and putting them in
the commit is bad.
I have no problem with putting an _advisory_ "revision number" in the
commit. It would not be expected to have a proper "1-to-1 and onto"
functional association with the _final_ DAG, but it could potentially
get us some nice benefits. We would still need to answer questions like
the one I ask above, but it would hurt less to change if we need to.
One other sane option that was mentioned at least once in passing was to
store the generation number in some Git "filesystem-level" object. This
could then be reconciled with each "git gc" or "git fsck" operation if
not more often. This is less ad-hoc and messy than a separate cache,
becomes amenable to the standard tool-set, and always gets updated (no
invalid cache). If an _advisory_ revision number is available in commits
that are sent along those could conceivably be used to help build up the
local git-fs generation numbers more quickly. (If a "git pull" is issued
to our repo, or we push to another, we don't send the generation numbers
locally stored--we expect the git-fs machinery to regenerate those on
the fly.)
I may not be one of the "resident rocket scientists," but that's how I
see it.
--
-Drew Northup
________________________________________________
"As opposed to vegetable or mineral error?"
-John Pescatore, SANS NewsBites Vol. 12 Num. 59
From: George Spelvin <hidden> Date: 2016-06-15 22:51:38
On [off-list ref] wrote:
On Wed, 20 Jul 2011, Shawn Pearce wrote:
quoted
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.
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
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.
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 second set are identical trees.
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.
From: Jakub Narebski <hidden> Date: 2016-06-15 22:51:38
George Spelvin, could you please try not mangle CC to include only
emails, stripping names (e.g. "spearce@spearce.org" instead of
"Shawn Pearce [off-list ref]")?
"George Spelvin" [off-list ref] writes:
On [off-list ref] wrote:
quoted
On Wed, 20 Jul 2011, Shawn Pearce wrote:
quoted
quoted
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.
quoted
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
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.
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.
--
Jakub Narębski
From: George Spelvin <hidden> Date: 2016-06-15 22:51:38
There is also another issue that I have mentioned, namely incomplete
clones - which currently means shallow clone, without access to full
history.
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
Nb. grafts are so horrible hack that I would be not against turning
off generation numbers if they are used.
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.
In the case of replace objects you need both non-replaced and replaced
DAG generation numbers.
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 [off-list ref] wrote:
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.
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".
--
Shawn.
From: Pēteris Kļaviņš <hidden> Date: 2016-06-15 22:51:38
On 21/07/2011 5:24 PM, Phil Hord wrote:
Maybe the confusion comes from the different storage mechanisms being
discussed. If the generation numbers are in a local cache and used by a
single client, the determinism of the specific numbers doesn't much
matter. If they are part of the commit, it still doesn't need to be
completely deterministic. However, interoperability requires standards,
and standards favor determinism, so dogmatic determinism may triumph in
that case.
1. gen(06) might make sense if you mean to implement --date-order using
gen-numbers, for example. But I don't think it's practical in any case.
2. gen(06)+1 might make sense if you mean to require that gen-numbers
are unique per repo. But this is both unsupportable and unnecessary, so
it's a non-starter.
3. gen(B)+1 is what you'd get from the the algorithm I saw proposed.
All three of these are provably correct by my definition of "correct":
"for each A in ancestors_of(B), gen(A) < gen(B)".
However, [1] and [2] have some extra features of dubious value. Simpler
is better for interoperability, so I like [3] for this purpose.
Even [3] has an extra feature I think is unnecessary: determinism. If
that "requirement" is dropped, I think all three of these algorithms are
(functionally) roughly equivalent.
quoted
I don't think everybody MEANT to be saying such
different things--that's just how they appeared on this end.
Now, did you mean something different by "commit number?"
I remain unconvinced that there is value in gen-number distribution, so
to my mind, the specific algorithm and whether or not it is
deterministic are unimportant.
The beauty of Git is that no two copies of a Git repository as a whole
are the same: some people make shallow copies; others prune away all
branches except for the one they are interested in; yet others graft
together multiple original repositories. The upshot is that two copies
of the same repository may end up having different commits as their root
commits, and so the generation numbers computed for their repositories
would be different. Indeed, the shallow repository copy could later be
filled out with additional underlying commits, and so on.
Given this context, I can't see the value in fixing generation numbers
within commits. In my mind generation numbers are extremely useful
transient helper objects in every Git repository but they have no
meaning outside that repository, sort of like GIT_WORK_TREE.
Peter
From: Christian Couder <hidden> Date: 2016-06-15 22:51:38
On Fri, Jul 22, 2011 at 12:40 AM, Pēteris Kļaviņš
[off-list ref] wrote:
The beauty of Git is that no two copies of a Git repository as a whole are
the same: some people make shallow copies; others prune away all branches
except for the one they are interested in; yet others graft together
multiple original repositories. The upshot is that two copies of the same
repository may end up having different commits as their root commits, and so
the generation numbers computed for their repositories would be different.
Indeed, the shallow repository copy could later be filled out with
additional underlying commits, and so on.
Not only people want different repos, but with their own repo they
want different "views" (or "virtual graph") of it.
Given this context, I can't see the value in fixing generation numbers
within commits. In my mind generation numbers are extremely useful
transient helper objects in every Git repository but they have no meaning
outside that repository, sort of like GIT_WORK_TREE.
It's not even per repository that they have a meaning, it's per "view"
of the commit graph.
Thanks,
Christian.
From: Jakub Narebski <hidden> Date: 2016-06-15 22:51:38
On Thu, 21 Jul 2011, George Spelvin wrote:
quoted
There is also another issue that I have mentioned, namely incomplete
clones - which currently means shallow clone, without access to full
history.
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.
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.
quoted
Nb. grafts are so horrible hack that I would be not against turning
off generation numbers if they are used.
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.
Grafts are non-transferable, and if you use them to cull rather than add
history they are unsafe against garbage collection... I think.
quoted
In the case of replace objects you need both non-replaced and replaced
DAG generation numbers.
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.
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.
--
Jakub Narebski
Poland
From: Nicolas Pitre <nico@fluxnic.net> Date: 2016-06-15 22:51:38
On Fri, 22 Jul 2011, Jakub Narebski wrote:
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?
They would indeed be copied verbatim and become incorrect.
Nicolas
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.
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?
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
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?
They would indeed be copied verbatim and become incorrect.
From: Jakub Narebski <hidden> Date: 2016-06-15 22:51:38
On Fri, 22 Jul 2011, David Lang [off-list ref] wrote:
On Fri, 22 Jul 2011, Nicolas Pitre wrote:
quoted
On Fri, 22 Jul 2011, Jakub Narebski wrote:
quoted
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?
They would indeed be copied verbatim and become incorrect.
how would they become incorrect?
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.
--
Jakub Narebski
Poland
On Fri, Jul 22, 2011 at 11:34 AM, Jakub Narebski [off-list ref] wrote:
That is IF unknown headers are copied verbatim during rebase. For
"encoding" header this is a good thing, for "generation" it isn't.
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, 22 Jul 2011, David Lang [off-list ref] wrote:
quoted
On Fri, 22 Jul 2011, Nicolas Pitre wrote:
quoted
On Fri, 22 Jul 2011, Jakub Narebski wrote:
quoted
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?
They would indeed be copied verbatim and become incorrect.
how would they become incorrect?
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.
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
From: Nicolas Pitre <nico@fluxnic.net> Date: 2016-06-15 22:51:38
On Fri, 22 Jul 2011, david@lang.hm wrote:
On Fri, 22 Jul 2011, Jakub Narebski wrote:
quoted
That is IF unknown headers are copied verbatim during rebase. For
"encoding" header this is a good thing, for "generation" it isn't.
commit headers are _not_ copied during rebase
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
From: Jeff King <hidden> Date: 2016-06-15 22:51:38
On Fri, Jul 22, 2011 at 12:06:08PM -0700, Linus Torvalds wrote:
On Fri, Jul 22, 2011 at 11:34 AM, Jakub Narebski [off-list ref] wrote:
quoted
That is IF unknown headers are copied verbatim during rebase. For
"encoding" header this is a good thing, for "generation" it isn't.
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?
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
From: Felipe Contreras <hidden> Date: 2016-06-15 22:51:40
On Fri, Jul 22, 2011 at 10:06 PM, Linus Torvalds
[off-list ref] wrote:
On Fri, Jul 22, 2011 at 11:34 AM, Jakub Narebski [off-list ref] wrote:
quoted
That is IF unknown headers are copied verbatim during rebase. For
"encoding" header this is a good thing, for "generation" it isn't.
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.
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.
--
Felipe Contreras
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