3 ms·

> You may not use "git cat" very often, but what about "git checkout <SHA>"? If commits were stored as diffs, then Git would have to rebuild a tree of the very

> You may not use "git cat" very often, but what about "git checkout <SHA>"? If commits were stored as diffs, then Git would have to rebuild a tree of the very first commit, then replay every single diff up to the SHA you asked for. Yes, this is true. I don't know why it never bothers me. Maybe it's because you could also store the diffs in the opposite direction (i.e. store the tip of each branch in the clear, then store diffs from each commit to its parent). Computing the inverse of a diff should be a quick operation. Usually, when you check out something, it's the tip of a branch or near the tip of a branch. Anyway. Of course I know that storing trees makes it easy to compute diffs. Computing diffs will becomes slower with larger trees. On the other hand, storing diffs makes it slow to compute trees, and the more commits we've got, the slower the tree computation goes.

kevincox 6y ago
> Computing diffs will becomes slower with larger trees Not usually. Computing a diff is roughly O(n) with the size of a diff. This is because unchanged leaves of the tree can be seen as identical (because the are content addressed) and are skipped. So to compute the diff you only need to recurse into changed directories. So having a million files in the root directory and one has changed is very fast to diff as you just diff that one file. The worse case is the diff happening in a very deeply nested directory with lots of files in each of the subdirectories but even that is quite cheap as diffing a sorted directory listing is O(n) with the size of the listing. (The actual worst case is diffing large files as most text diff algorithms are worse than O(n))