From: amisha Date: Thu, 15 Jan 2026 13:09:35 GMT Subject: [PATCH v3] sparse-checkout: optimize string_list construction Message-ID: <20260115130935.93526-1-amishhhaaaa@gmail.com> In-Reply-To: <20260114192803.4852-1-amishhhaaaa@gmail.com> Improve O(n^2) complexity to O(n log n) while building a sorted 'string_list' by constructing it unsorted and sorting it afterwards. Signed-off-by: Amisha Chhajed --- builtin/sparse-checkout.c | 8 +++----- 1 file changed, 3 insertions(+), 5 deletions(-) diff --git a/builtin/sparse-checkout.c b/builtin/sparse-checkout.c index 15d51e60a8..edabe7cbd9 100644 --- a/builtin/sparse-checkout.c +++ b/builtin/sparse-checkout.c @@ -91,7 +91,7 @@ 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); @@ -289,11 +289,10 @@ 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); - string_list_remove_duplicates(&sl, 0); fprintf(fp, "/*\n!/*/\n"); @@ -311,13 +310,12 @@ 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); string_list_sort(&sl); - string_list_remove_duplicates(&sl, 0); for (i = 0; i < sl.nr; i++) { char *pattern = escaped_pattern(sl.items[i].string); -- 2.51.0