> 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.
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
And a tree 2 like this
A
/ \
B D
Where A is a root node, and B, C and D are subtrees (which may be huge; maybe many megabytes each), what actually gets stored for tree 1 is something like this:
A_tree_1
/ \
C B
And for tree 2:
A_tree_2
/ \
B D
And ultimately when you store both, you have this:
A_tree_1 A_tree_2
/ \ / \
/ \ / \
/ \ / \
C B D
Ok that's not the best drawing but I think I got the point across: we managed to have two different trees (tree 1 and tree 2) that each share an identical subtree (the B subtree), and as such B needs to be stored only once.
(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)