list-objects: support for skipping tree traversal
PATCH v2 1/1 list-objects: support for skipping tree traversal
The tree:0 filter does not need to traverse the trees that it has filtered out, so optimize list-objects and list-objects-filter to skip traversing the trees entirely. Before this patch, we iterated over all children of the tree, and did nothing for all of them, which was wasteful.
Signed-off-by Matthew DeVore <[email protected]>
--- list-objects-filter.c | 11 +++++++++-- list-objects-filter.h | 6 ++++++ list-objects.c | 5 ++++- t/t6112-rev-list-filters-objects.sh | 13 +++++++++++++ 4 files changed, 32 insertions(+), 3 deletions(-)
list-objects-filter.c +9 -2
@@ -102,9 +102,16 @@ static enum list_objects_filter_result filter_trees_none(case LOFS_BEGIN_TREE :case LOFS_BLOB : -if (filter_data->omits) +if (filter_data->omits) {oidset_insert (filter_data->omits, &obj->oid); -return LOFR_MARK_SEEN ;/* but not LOFR_DO_SHOW (hard omit) */ +/* _MARK_SEEN but not _DO_SHOW (hard omit) */ +return LOFR_MARK_SEEN ; + }else { +/* +* Not collecting omits so no need to to traverse tree. +*/ +return LOFR_SKIP_TREE |LOFR_MARK_SEEN ; + }case LOFS_END_TREE :assert (obj->type ==OBJ_TREE );
list-objects-filter.h +6 -0
@@ -24,6 +24,11 @@ struct oidset;* In general, objects should only be shown once, but * this result DOES NOT imply that we mark it SEEN. * +* _SKIP_TREE : Used in LOFS_BEGIN_TREE situation - indicates that +* the tree's children should not be iterated over. This +* is used as an optimization when all children will +* definitely be ignored. +* * Most of the time, you want the combination (_MARK_SEEN | _DO_SHOW) * but they can be used independently, such as when sparse-checkout * pattern matching is being applied.
@@ -45,6 +50,7 @@ enum list_objects_filter_result {LOFR_ZERO =0 ,LOFR_MARK_SEEN =1 <<0 ,LOFR_DO_SHOW =1 <<1 , + LOFR_SKIP_TREE = 1<<2, }; enum list_objects_filter_situation {
list-objects.c +4 -1
@@ -11,6 +11,7 @@#include "list-objects-filter-options.h" #include "packfile.h" #include "object-store.h" +#include "trace.h" struct traversal_context {struct rev_info *revs;
@@ -184,7 +185,9 @@ static void process_tree(struct traversal_context *ctx,if (base->len)strbuf_addch (base,'/' ); -if (!failed_parse) +if (r &LOFR_SKIP_TREE ) +trace_printf ("Skipping contents of tree %s...\n" , base->buf); +else if (!failed_parse)process_tree_contents (ctx, tree, base);if ((obj->flags &NOT_USER_GIVEN ) && ctx->filter_fn) {
t/t6112-rev-list-filters-objects.sh +13 -0
@@ -281,6 +281,19 @@ test_expect_success 'verify tree:0 includes trees in "filtered" output' ' test_cmp expected filtered_types ' +# Make sure tree:0 does not iterate through any trees. + +test_expect_success 'filter a GIANT tree through tree:0' ' + GIT_TRACE=1 git -C r3 rev-list \ + --objects --filter=tree:0 HEAD 2>filter_trace && + grep "Skipping contents of tree [.][.][.]" filter_trace >actual && + # One line for each commit traversed. + test_line_count = 2 actual && + + # Make sure no other trees were considered besides the root. + ! grep "Skipping contents of tree [^.]" filter_trace +' + # Delete some loose objects and use rev-list, but WITHOUT any filtering. # This models previously omitted objects that we did not receive.
Signature · 1 line
2.19.1.568.g152ad8e336-goog
Quoted 8 lines · Matthew DeVore
The tree:0 filter does not need to traverse the trees that it has filtered out, so optimize list-objects and list-objects-filter to skip traversing the trees entirely. Before this patch, we iterated over all children of the tree, and did nothing for all of them, which was wasteful.
Signed-off-by Matthew DeVore <[email protected]>---
Thanks, will queue.