Re: [PATCH] sparse-checkout: optimize string_list construction

From: Amisha Chhajed <amishhhaaaa@gmail.com>
Date: Jan 18, 2026, 13:07 UTC
Message-ID: <CAPvEtrceTDtZ2HdHnETRsKd0KTeeoVaiHy-K1O_+Qiuk6XAKcw@mail.gmail.com>
In-Reply-To: <xmqqqzrp74q3.fsf@gitster.g>

On Sat, 17 Jan 2026 at 00:41, Junio C Hamano <gitster@pobox.com> wrote:

Show 17 quoted lines

>
> amisha <amishhhaaaa@gmail.com> writes:
>
> > Subject: Re: [PATCH] sparse-checkout: optimize string_list construction
>
> It would have been nice to see [PATCH v2] or whatever that signals
> that there is an earlier iteration.
>
> > From: Amisha Chhajed <amishhhaaaa@gmail.com>
> >
> > Improve O(n^2) complexity to O(n log n) while building a sorted
> > 'string_list' by constructing it unsorted then sorting it
> > followed by removing duplicates.
>
> By the way, do we have t/perf/ that substanticates the performance
> claim here (in other words, how much improvement are we expecting in
> practice)?

After running different perf tests i was not able to find any substantial improvement in the results output before and after this patch, after going through some perf tests i came to conclude that for the results of this commit to shine we need a perf test that tests it with many duplicates, thanks to inputs by Derrick for further confirming this and giving me a starting point.

> Also, have you found out why the previous round that did not remove
> duplicates saw no failed tests?  Perhaps it is a good idea to add
> some test that would notice if we failed to add calls to
> remove_duplicates in this patch?

Yes!, actually we don't have a test that covers the line which removes duplicates. I wrote a test locally which fails if duplicates are found in the output with duplicates in input, very similar to what Jeff wrote for reproducing. I will create a patch sh

Show 6 quoted lines

> This is an unrelated tangent, a possible #leftoverbits material, but
> should not be part of this patch (or even in the same series as this
> patch).  I notice that string_list_remove_duplicates() almost always
> immediately follow a call to string_list_sort() of the same
> instance, which makes me wonder if we would be better off if we had
> a variant of string_list_sort(), and call it string_list_sort_u()

 After running command git grep -n -e "string_list_sort" -e
"string_list_remove_duplicates" -- clone.c fast-export.c fetch.c
help.c pack-objects.c sparse-checkout.c
from builtin/
i got the output

clone.c:1139:           string_list_sort(&option_recurse_submodules);

clone.c:1140: string_list_remove_duplicates(&option_recurse_submodules, 0);

fast-export.c:1121:     string_list_sort(&extra_refs);

fast-export.c:1122:     string_list_remove_duplicates(&extra_refs, 0);

fetch.c:1370:           string_list_sort(&refnames);

fetch.c:2587:   string_list_remove_duplicates(&list, 0);

help.c:159:     string_list_sort(&keys);

help.c:199:     string_list_remove_duplicates(&keys_uniq, 0);

pack-objects.c:3852:    string_list_sort(&include_packs);

pack-objects.c:3853:    string_list_remove_duplicates(&include_packs, 0);

pack-objects.c:3854:    string_list_sort(&exclude_packs);

pack-objects.c:3855:    string_list_remove_duplicates(&exclude_packs, 0);

pack-objects.c:3899: * string_list_item's ->util pointer, which string_list_sort() does not

pack-objects.c:4141:    string_list_sort(&discard_packs);

pack-objects.c:4142:    string_list_sort(&fresh_packs);

sparse-checkout.c:97:           string_list_sort(&sl);

sparse-checkout.c:98:           string_list_remove_duplicates(&sl, 0);

sparse-checkout.c:296:  string_list_sort(&sl);

sparse-checkout.c:297:  string_list_remove_duplicates(&sl, 0);

sparse-checkout.c:320:  string_list_sort(&sl);

sparse-checkout.c:321:  string_list_remove_duplicates(&sl, 0);

There are many places where string_list_rmeove_duplicates is directly next to string_list_sort, so it is a very common pattern

Thank you.