Re: [PATCH] sparse-checkout: optimize string_list construction
- From
Junio C Hamano <gitster@pobox.com>
- Date
- Jan 16, 2026, 19:11 UTC
- Message-ID
- <xmqqqzrp74q3.fsf@gitster.g>
- In-Reply-To
- <20260116165003.95314-1-amishhhaaaa@gmail.com>
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.
Show 5 quoted lines
> 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)?
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?
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().
Thanks.
Show 35 quoted lines
> diff --git a/builtin/sparse-checkout.c b/builtin/sparse-checkout.c
> index 15d51e60a8..7dfb276bf0 100644
> --- a/builtin/sparse-checkout.c
> +++ b/builtin/sparse-checkout.c
> @@ -91,10 +91,11 @@ static int sparse_checkout_list(int argc, const char **argv, const char *prefix,
>
> hashmap_for_each_entry(&pl.recursive_hashmap, &iter, pe, ent) {
> /* pe->pattern starts with "/", skip it */
> - string_list_insert(&sl, pe->pattern + 1);
> + string_list_append(&sl, pe->pattern + 1);
> }
>
> string_list_sort(&sl);
> + string_list_remove_duplicates(&sl, 0);
>
> for (i = 0; i < sl.nr; i++) {
> quote_c_style(sl.items[i].string, NULL, stdout, 0);
> @@ -289,7 +290,7 @@ static void write_cone_to_file(FILE *fp, struct pattern_list *pl)
> if (!hashmap_contains_parent(&pl->recursive_hashmap,
> pe->pattern,
> &parent_pattern))
> - string_list_insert(&sl, pe->pattern);
> + string_list_append(&sl, pe->pattern);
> }
>
> string_list_sort(&sl);
> @@ -311,7 +312,7 @@ static void write_cone_to_file(FILE *fp, struct pattern_list *pl)
> if (!hashmap_contains_parent(&pl->recursive_hashmap,
> pe->pattern,
> &parent_pattern))
> - string_list_insert(&sl, pe->pattern);
> + string_list_append(&sl, pe->pattern);
> }
>
> strbuf_release(&parent_pattern);