Git stores states of the repo across time. The diff is something created for the user. Internally, Git might or might store it in an optimized way, but not necessarily.
But still, I can’t reason about how so many changes to a repo can be recorded in a way that’s so efficient that it’s almost imperceptible in time cost. And I’ve yet to see a satisfactory answer to this question. I need concrete examples.
When you ask git for a diff it compares the trees and when there is a difference it compares the files the trees reference and it shows you a diff.
Git does not store diffs, it stores file trees.
With this foundation, Git is already quite efficient in common scenarios since most commits create only a few new objects: the commit, the new versions of the files, and all directory nodes all the way to the top.
Git could store all of these in the filesystem. Often, they are stored in indexed and compressed pack files though. But the underlying principle remains the same.
git add . && git commit -m wip
This is basically the speed of
find .
Then it takes all that metadata, comine it to one, add it to a commit message and it's done.
Doesn't take a lot of time to do these things, but it will for very large files.
Going the other direction is fast, reverse lookup all that metadata and copy the contents back into the working directory
It's because git does heavy deduplication, in the same way that functional, persistent data structures do heavy deduplication.
For example, if you have a tree data structure and one tree (let's call it tree 1) like this
A
/ \
C B
A
/ \
B D
A_tree_1
/ \
C B
A_tree_2
/ \
B D
A_tree_1 A_tree_2
/ \ / \
/ \ / \
/ \ / \
C B D
(But note that the "spine" of the tree - the path from the possibly deduplicated subtrees until the root - will not itself be deduplicated. That is, even if A is identical between tree 1 and tree 2, you still need different A_tree_1 and A_tree_2, because one of them contains pointers to C and B, and the other contains pointers to B and D)
That's how persistent data structures work in functional programming (for example, in Haskell, if you are careful with sharing you can have two different trees share a subtree rather than making a deep copy them, lowering the memory usage)
And that's how objects in git work (which include commits, filesystem trees, and file contents, that are called blobs). Two different objects that share subtrees will also share storage. That's not a diff, that's just how things are stored in Git. But ultimately, whenever you need to diff, you only need to consider the diff between C and D; B is common between A_tree_1 and A_tree_2 and doesn't need to be diffed.
And the reason this works is that in Git, objects are immutable: you don't modify an existing commit when you do git commit --amend for example, you create an entirely new commit (and the old commit is still in the repository, until you run git gc to get rid of it - but it probably occupies almost no space, because its filesystem tree is probably quite similar to the other commit)
(That's how it works in functional programming too: persistent data structures are commonly used there because in functional programming, you don't modify existing trees, you create new ones whenever you want to do a "functional update"; but you deduplicate the trees so that this update can still be somewhat efficient)
And the mechanism this deduplication is implemented in Git is content addressing: every object is identified by a sha1 hash of its contents, and every time you try to store an object with a given sha1 hash, git will first verify if this object already exist and if so, it will reuse the existing object.
(This means that a "pointer" to a subtree, in git, is just its sha1 hash. So the reason that A_tree_1 and A_tree_2, in Git, need to be different objects, is that inside them there are different hashes: one has C and B, and the other, B and D)
(Deduplication in Haskell's data structures wouldn't use content addressing, but instead you manually tell that a given tree will be built with a subtree from another tree, and then it just works because no tree can be modified)
Note: content addressing is also how deduplication in filesystems like btrfs work. In those filesystems, the kernel will hash a piece of a file (an extent) and check in a hash table whether that particular extent is already stored somewhere. If yes, you don't need to store again. (you can disable online deduplication too, and do it offline, with a batch job)
Git logically stores file contents as blobs in essentially a key-value store. However, the physical storage writes many objects into a single "packfile", and for each object it uses heuristics to look for "likely similar" object candidates already in the packfile, computes deltas based on them, choosing the smallest possible delta or falling back to storing the object as-is if it can't find a good candidate.
Start with a filesystem like this. They all have a root object with an id that is pointing to a tree. The tree is (name, type, pointer to data):
root object 1:
dir1 directory 2
dir2 directory 3
file1 file 4
file2 file 5
What it stores is the following:
root object 6:
dir1 directory 2
dir2 directory 3
file1 file 7
file2 file 5
1. The new root object, which is a bunch of pointers
2. the new file data
That is very fast to store, and very efficient to store and retrieve. It is not slower to access old data vs new data.
The data is all immutable, all you are storing is pointers to which data is named what.
If you had a file in dir1 instead, you would update the root object and dir1. dir2 would be untouched, so you would still store ... just as much as above.
This is how git works at a high level.
In practice, most commits change a small number of files. So you will update the root object, and all the directory objects on the way to your new file, but that's it.
Most source code trees are lets say 10 directories deep max? So even if you have a thousand directories, you are updating only the directory objects that are parents of your file's path. So maybe 10 directory objects get updated. All others are untouched.
So O(10) changed directory objects to store, plus the root object, plus the new file data. Everything else is reused.
This is very fast.
The worst case for something like the above is where you change a file in every directory. It will then have to rewrite every directory object, even for small file changes.
Or you have flat directories with huge numbers of small files. You then pay the cost of rewriting the directory objects all the time.
But for most source code layouts, the above works very fast.
Even without compression, the total space usage of your repo is O(total amount of changed data) rather than O(total amount of data represented by all root objects)
1 million revisions of kernel, at 4gig of data each, would be 4PB if you were storing complete copies at every revision.
Instead it's like 9 gigabytes or something, total.
Tom's 15 years old text remains the only correct, useful, easy to understand explanation of the why and how of git I've ever popularly encountered.
Post like the OP's do far more harm than good by introducing mental models comprised of best-effort confused half-knowledge.
If (generic) you ever wanted to "really learn git", do yourself a favor and read it.
git cat-file commit HEAD
For commits it shows the log message and textual diff.The internal representation doesn’t matter for most users and use cases.
Similar to the particle-wave duality in physics, a commit is both a snapshot and a diff, and similar to physics, which way to look at it depends on context.
For example, if you are rebasing branch A onto branch B, then you will want to look at the current state of branch B (the snapshot model) plus the diffs of the relevant commits from branch A (the diff model).
You will get nowhere fast if you try to look at branch A using the snapshot model. (And looking at branch B using the diff model will drive you insane.)
How git stores the data is orthogonal to that, I kind of know in the back of my head but I don't really care too much. It's enough that git gives me access to both the snapshot and the diff aspect of a commit.
It uses snapshots because that is efficient, but from a user perspective all common git operations look more like they are operating on diffs than snapshots.
When you cherry-pick a commit, the diff of the old and new commit will be similar, but the snapshots are normally completely different; that's the point. The same goes for rebasing, which is like applying a set of patches. Heck, if it goes wrong, you get merge conflicts, which wouldn't happen if you were just manipulating pointers between snapshots.
Git actually makes it quite difficult to manipulate commits as pointers to snapshots instead of diffs -- i doubt most git users even know about `git commit-tree`.
This is why i don't really get the "git is wrong and should work on diffs" crowd. If it did, the user experience would be 99% the same, unless you're manually editing your diffs before committing them.
Git does delta compression, so in fact it does usually store diffs on disk. That, however, is a technical detail that doesn't actually influence the user and can be 100% ignored as long as you don't mess with its internal files by hand.
What the user actually operates on in the repository are snapshots, with diffs being merely an intermediate representation useful for factoring, reading or distributing stuff. Git is good at confusing the user that it works on diffs, but the sooner you realize that it's not true, the easier it will be for you to work with Git.
And while "git cherry-pick" (and in turn, "git rebase" too) seems like an automated "git format-patch + git am" at first glance, it actually goes further and is using three-way merge for better conflict resolution. It works on snapshots, not diffs.
> Git does delta compression, so in fact it does usually store diffs on disk.
Yep. The comment you replied to originally was pointing out that snapshots and diffs are isomorphic, so i'm glad we all seem to agree.
> What the user actually operates on in the repository are snapshots
They don't, though. Git doesn't show you the tree IDs in normal operation, and you can't actually make commits that point to specific trees (snapshots) without unusual commands.
> it actually goes further and is using three-way merge for better conflict resolution. It works on snapshots, not diffs
It doesn't really matter what it's working on, the best mental model to understand cherry-picking and rebase is that of applying diffs. Can you (in general) even explain things like rebase and cherry-pick without the terminology of diffs? The git manual doesn't bother.
Didn't want to, consider "you" to be plural in my last comment, or replace it with "one". I honestly believe that reasoning about commits as "diffs" leads to nothing but confusion.
> They don't, though.
They do. The fact that to write a letter you type each character separately doesn't mean that what you're operating on in a text editor are one-char diffs. You're composing a single letter to save - just like in Git, where you're composing a single state of the repo to then commit (or in other words, to snapshot it). How exactly you compose that state (by using index, or commit-tree, or subtrees, or placing files directly in .git, or...) is irrelevant to the resulting repository graph - and that graph of snapshots is ultimately the data structure that you're conceptually operating on (regardless of how it's represented on the disk).
You work on commits, not trees. Commits are snapshots of your files. Trees and blobs are just how Git represents your files - almost an implementation detail. From the user PoV, Git could even be creating new directories in .git with copies of your whole working dir for each commit and nothing would change conceptually, it's irrelevant to the high-level mental model of a Git repository.
> Can you (in general) even explain things like rebase and cherry-pick without the terminology of diffs?
A diff is a result of an operation applied to two snapshots. Cherry-pick executes that operation and uses the result of it (at least conceptually). You can't think of it as operating directly on "commits as diffs", because then things like cherry-picking a merge commit wouldn't make any sense, while they still make perfect sense and are easy to explain with the "commit is a snapshot" mental model. Some things in Git calculate diffs between two commits and use that result in some way, but that doesn't change the model of the repository.
And because Git often shows you diffs for convenience, it's easy to develop a wrong mental model of the repository - a model that most people operate on, but which will bite you sooner or later. That's exactly why so many people end up being confused with Git.
IMO it makes just as much sense either way. When cherry-picking a merge commit you have to specify which parent to diff against, which could just as easily be explained in terms of diffs (i.e. which part of an n-way diff to apply).
> it's easy to develop a wrong mental model of the repository - a model that most people operate on, but which will bite you sooner or later. That's exactly why so many people end up being confused with Git
This doesn't match my experience (as "that guy that people go to for git help"). Perhaps you have a concrete example.
Just to be clear, i'm not advocating for teaching or believing that git works in a way that it doesn't, that would be silly. More that being able to think about it in different (equivalent) ways in different situations is helpful.
- cherry-pick creates "duplicated" commits
- you can checkout a commit, rather than a branch
- two commits in the same repo may be topologically unrelated to each other
- merge commit can contain changes unrelated to its parents (usually after making some by accident)
- you can git reset --soft
Those are just the ones that came to my head on a whim (and don't get me started on rebase-heavy workflows). I've had people telling me that it "finally clicked" when made aware that commit is a state rather than a change. Explaining what I just did to "fix" someone's repo is also often easier after a proper "commit as a snapshot" prelude. If people who used Git for years say "oh, that makes much more sense now" after being presented with basic Git concepts, it suggests that their mental model may have been somewhat flawed.
Once you internalize that commit is a snapshot, going from that to thinking about diffs between two commits is easy. The other way around is not so obvious - when checking out a commit from complicated topology, it may not be immediately clear how to get from one state to another by "applying diffs" even if it's technically equivalent, so simple operations will end up seeming like undecipherable magic to you simply because they don't fit your mental model very well.
The whole thread started with a notion of "particle-wave duality", which is technically true, but useless in practice when "diff between two arbitrary commits" is one of the simplest operations to think about in terms of graphs of snapshots.