Re: [RFC PATCH 2/2] merge-recursive: optimize time complexity for get_unmerged
From: Elijah Newren <hidden>
Date: 2025-02-13 17:11:45
On Thu, Feb 13, 2025 at 1:01 AM Meet Soni [off-list ref] wrote:
Previously, `get_unmerged()` used `string_list_insert()`, which has an O(n^2) complexity due to shifting elements on each insertion. It also called `string_list_lookup()` before insertion, which performs a binary search in O(log n).
Okay.
This combination made insertion costly, especially for large index states, as each new entry required both a search and potentially shifting many elements.
Why does the combination make it costly? O(log n) + O(n^2) is still O(n^2), so I don't see why it matters to mention the combination. Could you clarify? Also, does it actually make it costly, or do you only suspect that it does? O(n^2) worst case sometimes behaves O(n) or O(n log n) in some cases. Since your commit message says "made insertion costly" instead of "might make insertion costly", I think that would suggest you have some performance numbers to back this up on some interesting real world repository. Do you? Can you share them?
Replace `string_list_insert()` with `string_list_append()` to achieve O(n) insertion. After all entries are added, sort the list in O(n log n) and remove duplicates in O(n), reducing the overall complexity to O(n log n).
Okay.
This improves performance significantly for large datasets
That's a big claim; it may be true, but without evidence I don't believe it for three reasons : (1) n here is the number of conflicts, not the number of files in the repo or the number of lines being merged. Thus, n is typically small. (2) Other O(n^2) behavior in merge-recursive likely drowns this particular codepath out, so any gains here just aren't going to be noticed, (3) After looking at the code and knowing the specialized structure of the index, I think that while string_list_insert() for n items in general is going to be O(n^2), it will likely functionally be O(n log n) for this particular code path, meaning you haven't actually improved the performance.
while maintaining correctness.
More on that below.
quoted hunk ↗ jump to hunk
Signed-off-by: Meet Soni <redacted> --- merge-recursive.c | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-)diff --git a/merge-recursive.c b/merge-recursive.c index 884ccf99a5..6165993429 100644 --- a/merge-recursive.c +++ b/merge-recursive.c@@ -547,15 +547,15 @@ static struct string_list *get_unmerged(struct index_state *istate) if (!ce_stage(ce)) continue; - item = string_list_lookup(unmerged, ce->name); - if (!item) { - item = string_list_insert(unmerged, ce->name); - item->util = xcalloc(1, sizeof(struct stage_data)); - } + item = string_list_append(unmerged, ce->name); + item->util = xcalloc(1, sizeof(struct stage_data)); + e = item->util; e->stages[ce_stage(ce)].mode = ce->ce_mode; oidcpy(&e->stages[ce_stage(ce)].oid, &ce->oid);
Did you run any tests? I'm not sure you maintained correctness here.
}
+ string_list_sort(unmerged);
+ string_list_remove_duplicates(unmerged, 1);
return unmerged;
}
--
2.34.1(As a side note, due to the specialized structure of the input, I suspect this code could be modified to run in O(n), i.e. we could skip the string_list_lookup and the string_list_sort and the string_list_remove_duplicates... But, it'd make the code trickier, so it'd need to be carefully commented, the change would need to be justified, and it'd need to be carefully tested. Even if we weren't planning to delete this entire file, I suspect it's not possible to find a case justifying such a change without optimizing several other things in merge-recursive first, but optimizing those things probably results in a significant rewrite...which we've already done with merge-ort.)