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

[Junio C Hamano <gitster@pobox.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.

> 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.

> 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);