Re: [PATCH v2 1/5] merge-ort: replace string_list_df_name_compare with faster alternative

From: Derrick Stolee <stolee@gmail.com>
To: Elijah Newren via GitGitGadget <gitgitgadget@gmail.com>,
	git@vger.kernel.org
Cc: "Derrick Stolee" <dstolee@microsoft.com>,
	"Jonathan Tan" <jonathantanmy@google.com>,
	"Taylor Blau" <me@ttaylorr.com>, "René Scharfe" <l.s.r@web.de>,
	"Elijah Newren" <newren@gmail.com>
Subject: Re: [PATCH v2 1/5] merge-ort: replace string_list_df_name_compare with faster alternative
Date: Wed, 2 Jun 2021 07:29:17 -0400	[thread overview]
Message-ID: <11416fb2-50f1-ebf0-e2ca-cebe64aeeeed@gmail.com> (raw)
In-Reply-To: <c4a0f6a9510c6e57604e7b0c62b1216a4f5f5618.1622559516.git.gitgitgadget@gmail.com>

On 6/1/21 10:58 AM, Elijah Newren via GitGitGadget wrote:
> From: Elijah Newren <newren@gmail.com>
> 
...
>  	/*
> -	 * Here we only care that entries for D/F conflicts are
> -	 * adjacent, in particular with the file of the D/F conflict
> -	 * appearing before files below the corresponding directory.
> -	 * The order of the rest of the list is irrelevant for us.
> +	 * Here we only care that entries for directories appear adjacent
> +	 * to and before files underneath the directory.  We can achieve
> +	 * that by pretending to add a trailing slash to every file and
> +	 * then sorting.  In other words, we do not want the natural
> +	 * sorting of
> +	 *     foo
> +	 *     foo.txt
> +	 *     foo/bar
> +	 * Instead, we want "foo" to sort as though it were "foo/", so that
> +	 * we instead get
> +	 *     foo.txt
> +	 *     foo
> +	 *     foo/bar
> +	 * To achieve this, we basically implement our own strcmp, except that
> +	 * if we get to the end of either string instead of comparing NUL to
> +	 * another character, we compare '/' to it.
> +	 *
> +	 * If this unusual "sort as though '/' were appended" perplexes
> +	 * you, perhaps it will help to note that this is not the final
> +	 * sort.  write_tree() will sort again without the trailing slash
> +	 * magic, but just on paths immediately under a given tree.

I find this comment to be helpful.

> +	 * The reason to not use df_name_compare directly was that it was
> +	 * just too expensive (we don't have the string lengths handy), so
> +	 * I had to reimplement it.

Just a hyper-nit I think first person works great in commit
messages, as the author's name is clearly listed in context.
Here, I'd prefer "so it was reimplemented" over "so I had to
reimplement it" as the author will not be present in context.

> +
> +	while (*one && (*one == *two)) {
> +		one++;
> +		two++;
> +	}
> +
> +	c1 = *one;
> +	if (!c1)
> +		c1 = '/';
> +
> +	c2 = *two;
> +	if (!c2)
> +		c2 = '/';

While I'm making other nits on this patch, perhaps this is
an appropriate place for some ternary operators to compress
the vertical space in this method:

	c1 = *one ? *one : '/';
	c2 = *two ? *two : '/';

> +	if (c1 == c2) {
> +		/* Getting here means one is a leading directory of the other */
> +		return (*one) ? 1 : -1;
> +	} else
> +		return c1-c2;

nit: "c1 - c2"

Thanks,
-Stolee