Re: [PATCH v5 1/2] sparse-checkout: optimize string_list construction
On 1/19/2026 7:33 AM, amisha wrote:
Show 25 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.
>
> Signed-off-by: Amisha Chhajed <amishhhaaaa@gmail.com>
> ---
> builtin/sparse-checkout.c | 7 ++++---
> 1 file changed, 4 insertions(+), 3 deletions(-)
>
> 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);Shouldn't this line be added in the other uses of string_list_append()?
Show 12 quoted lines
>
> 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);Actually, there is a string_list_remove_duplicates() just outside of the context of this diff.
Show 9 quoted lines
> @@ -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);
Same here.
This diff looks good, but I do believe it would be good to include your duplicate test here instead of in a second patch.
Also, the way your second patch appeared as a trailer of your first patch, so it didn't appear properly as a thread in my email client. Here it is for review:
Show 5 quoted lines
> From b20a99f0773bab063a31eea6fead730e18200ca7 Mon Sep 17 00:00:00 2001
> From: Amisha Chhajed <amishhhaaaa@gmail.com>
> Date: Mon, 19 Jan 2026 00:20:47 +0530
> Subject: [PATCH v5 2/2] t1091: Add tests for deduplication of cone-mode sparse
> patterns
nit: this title is a little long and has incorrect capitalization. Take note for later, since I expect this diff to be squashed into the previous patch.
Show 8 quoted lines
> +test_expect_success 'sparse-checkout deduplicates repeated cone patterns' '
> + rm -f repo/.git/info/sparse-checkout &&
> + git -C repo sparse-checkout init --cone &&
> + git -C repo sparse-checkout add --stdin <<-\EOF &&
> + /foo/
> + /bar/
> + /foo/
> + EOF
This slashes are redundant for cone-mode patterns. I recommend a more interesting case, such as
foo/bar/baz
a/b/c
foo/bar/baz
a/b
This should remove the duplicates foo/bar/baz during the run, but also it should notice that a/b/c is contained within the recursive set defined by a/b.
The resulting sparse-checkout file should have lines such as
/*
!/*/
/a/
!/a/*/
/a/b
/foo
!/foo/*/
/foo/bar
!/foo/bar/*/
/foo/bar/baz
The order might be different, but this is what I recall from how nested directories work in cone mode.
Show 8 quoted lines
> + cat >expect <<-\EOF &&
> + /*
> + !/*/
> + /bar/
> + /foo/
> + EOF
> + test_cmp expect repo/.git/info/sparse-checkout
> +'
Show 15 quoted lines
> +test_expect_success 'sparse-checkout list deduplicates repeated cone patterns' '
> + rm -f repo/.git/info/sparse-checkout &&
> + git -C repo sparse-checkout init --cone &&
> + git -C repo sparse-checkout add --stdin <<-\EOF &&
> + /foo/
> + /bar/
> + /foo/
> + EOF
> + git -C repo sparse-checkout list >actual &&
> + cat >expect <<-\EOF &&
> + bar
> + foo
> + EOF
> + test_cmp expect actual
> +'
This does lead to an interesting case where the 'list' command was only interacting with the sparse-checkout file, which wouldn't have duplicates if it was modified by the user in cone mode.
Keep in mind that you're not actually testing the 'list' command, because the 'add' command already deduplicated. You'll need to modify the sparse-checkout file itself to get an interesting test of the 'list' command.
When not in cone mode, we should not be removing duplicates because the order of the patterns matters and we should not be reordering them. I'm not sure if that's relevant but it's something to keep in mind while you're testing, since the command will revert to non-cone mode if the sparse-checkout file doesn't match the cone mode pattern expectations.
Thanks, -Stolee
amisha
