Re: git-revert is a memory hog
- From
Junio C Hamano <gitster@pobox.com>
- Date
- Jan 29, 2008, 23:19 UTC
- Message-ID
- <7vwspskynz.fsf@gitster.siamese.dyndns.org>
- In-Reply-To
- <7vfxwgmf87.fsf@gitster.siamese.dyndns.org>
Junio C Hamano <gitster@pobox.com> writes:
Show 12 quoted lines
> Jeff King <peff@peff.net> writes: > >> On Wed, Jan 30, 2008 at 08:51:09AM +1100, Linus Torvalds wrote: >> >>> I definitely can reproduce it, it's horrid. >>> >>> This is from "top" fairly late in the game, but with the thing not even >>> done yet. Current git, pretty much fully (and fairly aggressively) packed >>> current kernel repo, and using "diff.renamelmit=0". >> >> Hrm, setting diff.renamelimit to 0 lets me reproduce (I thought I tried >> it before, but clearly not...).
How about this fairly obvious patch?
We used to record, for N=src deleted paths and M=dst created paths, (N x M) "struct diff_score" that records how similar each of the pair is, and picked the <src,dst> pairs that gives the best match first, and then went on to worse matches. This sorting is so that two destinations are both found to be similar to a single source, we can process the more similar one first, and when processing the second one, it can notice "Ah, the source I was planning to say I am a copy of is already taken by somebody else" and continue on to match himself with another source with a lessor match (this matters to a change introduced between 1.5.3.X series and 1.5.4-rc, that lets the code to favor unused matches first and then falls back to using already used matches).
This instead allocates and keeps only M records in core. For each dst, we compute similarlity with all sources (so the number of similarity estimate computations we do is still N x M), but we keep the best src for each dst. This is essentially to save memory drastically by giving up to come up with better pairing.
I guess we could keep a handful best candidates per dst, instead of just one, to further improve on this approach, and such a change should be fairly straightforward.
--- diffcore-rename.c | 46 +++++++++++++++++++++++----------------------- 1 files changed, 23 insertions(+), 23 deletions(-)
diff --git a/diffcore-rename.c b/diffcore-rename.c index 3d37725..7e8fdcd 100644 --- a/diffcore-rename.c +++ b/diffcore-rename.c @@ -473,42 +473,42 @@ void diffcore_rename(struct diff_options *options) if (num_create * num_src > rename_limit * rename_limit) goto cleanup; - mx = xmalloc(sizeof(*mx) * num_create * num_src); + + mx = xmalloc(sizeof(*mx) * num_create); for (dst_cnt = i = 0; i < rename_dst_nr; i++) { - int base = dst_cnt * num_src; struct diff_filespec *two = rename_dst[i].two; + struct diff_score *m; + if (rename_dst[i].pair) continue; /* dealt with exact match already. */ + + m = &mx[dst_cnt]; + m->dst = -1; for (j = 0; j < rename_src_nr; j++) { struct diff_filespec *one = rename_src[j].one; - struct diff_score *m = &mx[base+j]; - m->src = j; - m->dst = i; - m->score = estimate_similarity(one, two, - minimum_score); - m->name_score = basename_same(one, two); + int score, name_score; + score = estimate_similarity(one, two, + minimum_score); + name_score = basename_same(one, two); + if (m->dst < 0 || + score > m->score || + (score == m->score && + name_score > m->name_score)) { + m->score = score; + m->name_score = name_score; + m->src = j; + m->dst = i; + } diff_free_filespec_blob(one); } /* We do not need the text anymore */ diff_free_filespec_blob(two); dst_cnt++; } + /* cost matrix sorted by most to least similar pair */ - qsort(mx, num_create * num_src, sizeof(*mx), score_compare); - for (i = 0; i < num_create * num_src; i++) { - struct diff_rename_dst *dst = &rename_dst[mx[i].dst]; - struct diff_filespec *src; - if (dst->pair) - continue; /* already done, either exact or fuzzy. */ - if (mx[i].score < minimum_score) - break; /* there is no more usable pair. */ - src = rename_src[mx[i].src].one; - if (src->rename_used) - continue; - record_rename_pair(mx[i].dst, mx[i].src, mx[i].score); - rename_count++; - } - for (i = 0; i < num_create * num_src; i++) { + qsort(mx, num_create, sizeof(*mx), score_compare); + for (i = 0; i < num_create; i++) { struct diff_rename_dst *dst = &rename_dst[mx[i].dst]; if (dst->pair) continue; /* already done, either exact or fuzzy. */