[PATCH v4 2/2] revision.c: reduce memory usage on reverse before
- From
Mirko Faina <mroik@delayed.space>
- Date
- Apr 27, 2026, 00:24 UTC
- Message-ID
- <7c0bab5d14bb2ce2a10d35d93e3d911ed4c386eb.1777249165.git.mroik@delayed.space>
- In-Reply-To
- <cover.1777249165.git.mroik@delayed.space>
Due to the nature of --reverse=before we have to walk all of the history and store each non-filtered processed commit, this can be expensive on memory for projects with a long history. When --max-count is being used we don't really have to keep every processed commit, we can discard older commits (as in have been processed before than the ones we're now considering, from a chronological commit order they are the newer commits) as we surpass the --max-count limit.
Teach get_revision() to keep only the newer commits as we walk a revision with --reverse=before and --max-count=<k>. We do this through a simple queue. With N nodes and K as the --max-count argument, assuming K < N, we go from a space complexity of O(N) to O(K). When it comes down to time complexity, the queue has an amortized time of O(1) for pops, so the complexity remains O(N).
Signed-off-by: Mirko Faina <mroik@delayed.space> --- revision.c | 42 ++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 40 insertions(+), 2 deletions(-)
diff --git a/revision.c b/revision.c index d581f5e38e..41c3d185c5 100644 --- a/revision.c +++ b/revision.c @@ -4530,6 +4530,40 @@ static struct commit *get_revision_internal(struct rev_info *revs) return c; } +static void retrieve_with_window(struct rev_info *revs, int max_count, + struct commit_list **reversed) +{ + struct commit *c; + struct commit_list *into_queue = NULL; + struct commit_list *outo_queue = NULL; + int into_count = 0; + int outo_count = 0; + + while ((c = get_revision_internal(revs))) { + commit_list_insert(c, &into_queue); + into_count++; + if (into_count + outo_count > max_count) { + if (!outo_count) { + while (into_count) { + c = pop_commit(&into_queue); + into_count--; + commit_list_insert(c, &outo_queue); + outo_count++; + } + } + pop_commit(&outo_queue); + outo_count--; + } + } + + while ((c = pop_commit(&outo_queue))) + commit_list_insert(c, reversed); + while ((c = pop_commit(&into_queue))) + commit_list_insert(c, &outo_queue); + while ((c = pop_commit(&outo_queue))) + commit_list_insert(c, reversed); +} + struct commit *get_revision(struct rev_info *revs) { struct commit *c; @@ -4546,8 +4580,12 @@ struct commit *get_revision(struct rev_info *revs) revs->max_count = -1; reversed = NULL; - while ((c = get_revision_internal(revs))) - commit_list_insert(c, &reversed); + if (revs->reverse == REVERSE_BEFORE && max_count >= 0) { + retrieve_with_window(revs, max_count, &reversed); + } else { + while ((c = get_revision_internal(revs))) + commit_list_insert(c, &reversed); + } commit_list_free(revs->commits); revs->commits = reversed; revs->reverse_output_stage = 1;
-- 2.54.0