On Thu, Feb 13, 2025 at 1:01 AM Meet Soni <meetsoni3017@xxxxxxxxx> 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.
> Signed-off-by: Meet Soni <meetsoni3017@xxxxxxxxx>
> ---
> 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.)
