On Wed, Dec 30, 2020 at 11:26 AM Derrick Stolee via GitGitGadget
<gitgitgadget@xxxxxxxxx> wrote:
>
> From: Derrick Stolee <dstolee@xxxxxxxxxxxxx>
>
> I had difficulty in my efforts to learn about the cached tree extension
> based on the documentation and code because I had an incorrect
> assumption about how it behaved. This might be due to some ambiguity in
> the documentation, so this change modifies the beginning of the cached
> tree format by expanding the description of the feature.
>
> My hope is that this documentation clarifies a few things:
>
> 1. There is an in-memory recursive tree structure that is constructed
> from the extension data. This structure has a few differences, such
> as where the name is stored.
>
> 2. What does it mean for an entry to be invalid?
>
> 3. When exactly are "new" trees created?
>
> Signed-off-by: Derrick Stolee <dstolee@xxxxxxxxxxxxx>
> ---
> Documentation/technical/index-format.txt | 36 ++++++++++++++++++++----
> 1 file changed, 30 insertions(+), 6 deletions(-)
>
> diff --git a/Documentation/technical/index-format.txt b/Documentation/technical/index-format.txt
> index 69edf46c031..c614e136e24 100644
> --- a/Documentation/technical/index-format.txt
> +++ b/Documentation/technical/index-format.txt
> @@ -138,12 +138,36 @@ Git index format
>
> === Cached tree
>
> - Cached tree extension contains pre-computed hashes for trees that can
> - be derived from the index. It helps speed up tree object generation
> - from index for a new commit.
> -
> - When a path is updated in index, the path must be invalidated and
> - removed from tree cache.
> + Since the index does not record entries for directories, the cache
> + entries cannot describe tree objects that already exist in the object
> + database for regions of the index that are unchanged from an existing
> + commit. The cached tree extension stores a recursive tree structure that
> + describes the trees that already exist and completely match sections of
> + the cache entries. This speeds up tree object generation from the index
> + for a new commit by only computing the trees that are "new" to that
> + commit.
> +
> + The recursive tree structure uses nodes that store a number of cache
> + entries, a list of subnodes, and an object ID (OID). The OID references
> + the exising tree for that node, if it is known to exist. The subnodes
> + correspond to subdirectories that themselves have cached tree nodes. The
> + number of cache entries corresponds to the number of cache entries in
> + the index that describe paths within that tree's directory.
> +
> + Note that the path for a given tree is part of the parent node in-memory
> + but is part of the child in the file format. The root tree has an empty
> + string for its name and its name does not exist in-memory.
> +
> + When a path is updated in index, Git invalidates all nodes of the
> + recurisive cached tree corresponding to the parent directories of that
> + path. We store these tree nodes as being "invalid" by using "-1" as the
> + number of cache entries. To create trees corresponding to the current
> + index, Git only walks the invalid tree nodes and uses the cached OIDs
> + for the valid trees to construct new trees. In this way, Git only
> + constructs trees on the order of the number of changed paths (and their
> + depth in the working directory). This comes at a cost of tracking the
> + full directory structure in the cached tree extension, but this is
> + generally smaller than the full cache entry list in the index.
Ooh, I really like it; this probably would have helped me. However,
we'll need to get someone else to take a look at this, because I don't
know enough to say whether any part of it is incorrect, misleading, or
incomplete or whether it's all good. My knowledge in the area is
limited to moving a function from merge-recursive.c to cache-tree.c in
commit 724dd767b2 ("cache-tree: share code between functions writing
an index as a tree", 2019-08-17), but I seem to recall that I had to
rely on Junio's reviews and guidance to make the minor adaptations
found in that commit.
