git@vger.kernel.org list mirror (unofficial, one of many)
 help / color / mirror / code / Atom feed
From: Junio C Hamano <gitster@pobox.com>
To: "Phillip Wood via GitGitGadget" <gitgitgadget@gmail.com>
Cc: git@vger.kernel.org,
	Johannes Schindelin <Johannes.Schindelin@gmx.de>,
	Phillip Wood <phillip.wood@dunelm.org.uk>
Subject: Re: [PATCH 1/2] patience diff: remove unnecessary string comparisons
Date: Wed, 05 May 2021 09:31:02 +0900	[thread overview]
Message-ID: <xmqqpmy658e1.fsf@gitster.g> (raw)
In-Reply-To: <a339d1cf9b9ffd6365fca3efda8fb7e10346dda4.1620120345.git.gitgitgadget@gmail.com> (Phillip Wood via GitGitGadget's message of "Tue, 04 May 2021 09:25:44 +0000")

"Phillip Wood via GitGitGadget" <gitgitgadget@gmail.com> writes:

> From: Phillip Wood <phillip.wood@dunelm.org.uk>
>
> xdl_prepare_env() calls xdl_classify_record() which arranges for the
> hashes of non-matching lines to be different so lines can be tested
> for equality by comparing just their hashes.

Hmph, that is a bit different from what I read from the comment in
the post context of the first hunk, though.

	/*
	 * After xdl_prepare_env() (or more precisely, due to
	 * xdl_classify_record()), the "ha" member of the records (AKA lines)
	 * is _not_ the hash anymore, but a linearized version of it.  In
	 * other words, the "ha" member is guaranteed to start with 0 and
	 * the second record's ha can only be 0 or 1, etc.
	 *
	 * So we multiply ha by 2 in the hope that the hashing was
	 * "unique enough".
	 */

The words "home" and "enough" hints to me that the "ha" member is
not hash, but "lineralized version of it" (whatever it means) does
not guarantee that two records with the same "ha" are identical, or
does it?

Well, I should just go read xdl_classify_record() to see what it
really does, but if it eliminates collisions, then the patch is a
clear and obvious improvement.

Thanks.

> diff --git a/xdiff/xpatience.c b/xdiff/xpatience.c
> index 20699a6f6054..db2d53e89cb0 100644
> --- a/xdiff/xpatience.c
> +++ b/xdiff/xpatience.c
> @@ -90,7 +90,7 @@ static void insert_record(xpparam_t const *xpp, int line, struct hashmap *map,
>  {
>  	xrecord_t **records = pass == 1 ?
>  		map->env->xdf1.recs : map->env->xdf2.recs;
> -	xrecord_t *record = records[line - 1], *other;
> +	xrecord_t *record = records[line - 1];
>  	/*
>  	 * After xdl_prepare_env() (or more precisely, due to
>  	 * xdl_classify_record()), the "ha" member of the records (AKA lines)
> @@ -104,11 +104,7 @@ static void insert_record(xpparam_t const *xpp, int line, struct hashmap *map,
>  	int index = (int)((record->ha << 1) % map->alloc);
>  
>  	while (map->entries[index].line1) {
> -		other = map->env->xdf1.recs[map->entries[index].line1 - 1];
> -		if (map->entries[index].hash != record->ha ||
> -				!xdl_recmatch(record->ptr, record->size,
> -					other->ptr, other->size,
> -					map->xpp->flags)) {
> +		if (map->entries[index].hash != record->ha) {
>  			if (++index >= map->alloc)
>  				index = 0;
>  			continue;
> @@ -253,8 +249,7 @@ static int match(struct hashmap *map, int line1, int line2)
>  {
>  	xrecord_t *record1 = map->env->xdf1.recs[line1 - 1];
>  	xrecord_t *record2 = map->env->xdf2.recs[line2 - 1];
> -	return xdl_recmatch(record1->ptr, record1->size,
> -		record2->ptr, record2->size, map->xpp->flags);
> +	return record1->ha == record2->ha;
>  }
>  
>  static int patience_diff(mmfile_t *file1, mmfile_t *file2,

  reply	other threads:[~2021-05-05  0:31 UTC|newest]

Thread overview: 8+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2021-05-04  9:25 [PATCH 0/2] A couple of small patience diff cleanups Phillip Wood via GitGitGadget
2021-05-04  9:25 ` [PATCH 1/2] patience diff: remove unnecessary string comparisons Phillip Wood via GitGitGadget
2021-05-05  0:31   ` Junio C Hamano [this message]
2021-05-05  9:34     ` Phillip Wood
2021-05-05 14:58     ` Johannes Schindelin
2021-05-05 18:00       ` Phillip Wood
2021-05-06  1:32       ` Junio C Hamano
2021-05-04  9:25 ` [PATCH 2/2] patience diff: remove unused variable Phillip Wood via GitGitGadget

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

  List information: http://vger.kernel.org/majordomo-info.html

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=xmqqpmy658e1.fsf@gitster.g \
    --to=gitster@pobox.com \
    --cc=Johannes.Schindelin@gmx.de \
    --cc=git@vger.kernel.org \
    --cc=gitgitgadget@gmail.com \
    --cc=phillip.wood@dunelm.org.uk \
    --subject='Re: [PATCH 1/2] patience diff: remove unnecessary string comparisons' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

Code repositories for project(s) associated with this inbox:

	https://80x24.org/mirrors/git.git

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).