4 ms·

Does it work when I'm looking for all commits changing a directory? I.e. Do directories get added to the bloom filter or just filenames?

deleted 8y ago
[deleted]
tempay 8y ago
I thought git didn't have a concept of directories, just blobs that have a path? If so, I presume "all commits changing a directory" is found by individually checking each file contained by the directory.
- lozenge 8y ago
  As the article mentions, each folder is a tree object containing (referencing) subfolders and blobs (files). Run git show HEAD^{tree} to see it. Finding the list of all filenames that were ever in a particular path is very expensive.
- masklinn 8y ago
  Git very much has directories, it calls them "tree": a commit links to a tree, which links to a number of trees or blobs associating each with a name: https://git-scm.com/book/gr/v2/Git-Internals-Git-Objects https://git-scm.com/book/gr/v2/Git-Internals-Git-Objects A blob is a file (ish, it can also be use for some other things since it's not intrinsically named), a tree is a directory. However Git doesn't treat filesystem directories themselves as first-class e.g. you can't version an empty directory. A tree only exists in order to contain sub-items (ultimately blobs).
stolee 8y ago
It does! The Bloom filter stores every path that changed, including paths to trees (except the root tree, which is expected to be changed by default). When you change a file, you also change every tree above it.
- kingosticks 8y ago
  So presumably that eats into the 512 item limit. If I had quite a deep directory structure (10 levels doesn't sound that unreasonable) I'd only get this speedup for commits changing 51 files or less. Right?
  - stolee 8y ago
    In your calculation, you are assuming that all of those files are in independent parts of the folder hierarchy. In practice, deep directory structures mean that single commits are likely focused in a few very deep folders. We ran the statistics on a number of repos with different shapes to come up with this number, and it covers 99% of commits that we measured.
    - kingosticks 8y ago
      That is true and I do agree. Thanks for clarifying and for the informative write-up, it's a great use of bloom filters.

deleted 8y ago

[deleted]

tempay 8y ago

I thought git didn't have a concept of directories, just blobs that have a path? If so, I presume "all commits changing a directory" is found by individually checking each file contained by the directory.

lozenge 8y ago
As the article mentions, each folder is a tree object containing (referencing) subfolders and blobs (files). Run git show HEAD^{tree} to see it. Finding the list of all filenames that were ever in a particular path is very expensive.
masklinn 8y ago
Git very much has directories, it calls them "tree": a commit links to a tree, which links to a number of trees or blobs associating each with a name: https://git-scm.com/book/gr/v2/Git-Internals-Git-Objects https://git-scm.com/book/gr/v2/Git-Internals-Git-Objects A blob is a file (ish, it can also be use for some other things since it's not intrinsically named), a tree is a directory. However Git doesn't treat filesystem directories themselves as first-class e.g. you can't version an empty directory. A tree only exists in order to contain sub-items (ultimately blobs).

stolee 8y ago

It does! The Bloom filter stores every path that changed, including paths to trees (except the root tree, which is expected to be changed by default). When you change a file, you also change every tree above it.

kingosticks 8y ago
So presumably that eats into the 512 item limit. If I had quite a deep directory structure (10 levels doesn't sound that unreasonable) I'd only get this speedup for commits changing 51 files or less. Right?
- stolee 8y ago
  In your calculation, you are assuming that all of those files are in independent parts of the folder hierarchy. In practice, deep directory structures mean that single commits are likely focused in a few very deep folders. We ran the statistics on a number of repos with different shapes to come up with this number, and it covers 99% of commits that we measured.
  - kingosticks 8y ago
    That is true and I do agree. Thanks for clarifying and for the informative write-up, it's a great use of bloom filters.