[PATCH v3] sparse-checkout: optimize string_list construction
- From
amisha <amishhhaaaa@gmail.com>
- Date
- Jan 15, 2026, 13:09 UTC
- 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 <amishhhaaaa@gmail.com> --- 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