4 ms·

Since a git hash points to a sorted list of filenames and content hashes, to diff two git commits you lookup the commit objects by their hash, run down the resu

by pja 12y ago

Since a git hash points to a sorted list of filenames and content hashes, to diff two git commits you lookup the commit objects by their hash, run down the resultant list of filename/hash pairs & then only lookup & diff the content of those files that have differing hashes (if they have the same hash, they must have the same content according to the git data model, so they can be safely ignored). Hence diffing arbitrary commits with git is always O(N) in the number of changed files, regardless of the number of interstitial commits.

throw_away 12y ago
In particular he's saying that for a tree, you can quickly skip sub-trees if they are the same, regardless of how deep they go. Kind of like a Merkle tree: http://en.m.wikipedia.org/wiki/Merkle_tree http://en.m.wikipedia.org/wiki/Merkle_tree I'm no git internals expert, but I suspect for a flat list of files the complexity is still O(n) where n is the number of files (not changes) because at very least you must check that n checksums are the same.
- pja 12y ago
  I'm no git internals expert, but I suspect for a flat list of files the complexity is still O(n) where n is the number of files (not changes) because at very least you must check that n checksums are the same. Sure. The constant factors make a huge difference though - even if you've cached all the data in memory walking all those structures and diffing the actual file data is going to be enormously slower than simply walking a list of hashes, so you're really saying that the total time is big * O(number of files changed) + small * O(number of files). If small*N ~ big then it's reasonable to just disregard that cost - it's going to be lost in the noise.
  - throw_away 12y ago
    I'm not arguing that, but rather that this ability to skip unchanged trees because the hash of all contents is bubbled up is specifically what Linus is referring to in the comment, not simply the comparison of hashes in the flat-directory use-case.
EGreg 12y ago
Wouldn't it still be O(total)? Or at the very least O(log total)? You have to look at all the files even if it's just to compare the hash. The size of the file doesn't matter so I think what Linus should have said was it's O(number of files) still, and maybe O(log total) in the average case. But if there are 1,000,000 files and only 2 change then I don't see how you don't have to look at all the hashes.

by pja 12y ago

throw_away 12y ago

In particular he's saying that for a tree, you can quickly skip sub-trees if they are the same, regardless of how deep they go. Kind of like a Merkle tree: http://en.m.wikipedia.org/wiki/Merkle_tree http://en.m.wikipedia.org/wiki/Merkle_tree I'm no git internals expert, but I suspect for a flat list of files the complexity is still O(n) where n is the number of files (not changes) because at very least you must check that n checksums are the same.

pja 12y ago
I'm no git internals expert, but I suspect for a flat list of files the complexity is still O(n) where n is the number of files (not changes) because at very least you must check that n checksums are the same. Sure. The constant factors make a huge difference though - even if you've cached all the data in memory walking all those structures and diffing the actual file data is going to be enormously slower than simply walking a list of hashes, so you're really saying that the total time is big * O(number of files changed) + small * O(number of files). If small*N ~ big then it's reasonable to just disregard that cost - it's going to be lost in the noise.
- throw_away 12y ago
  I'm not arguing that, but rather that this ability to skip unchanged trees because the hash of all contents is bubbled up is specifically what Linus is referring to in the comment, not simply the comparison of hashes in the flat-directory use-case.

EGreg 12y ago

Wouldn't it still be O(total)? Or at the very least O(log total)? You have to look at all the files even if it's just to compare the hash. The size of the file doesn't matter so I think what Linus should have said was it's O(number of files) still, and maybe O(log total) in the average case. But if there are 1,000,000 files and only 2 change then I don't see how you don't have to look at all the hashes.