Re: [PATCH 06/17] xdiff: delete redundant array xdfile_t.ha

From: Elijah Newren <newren@gmail.com>
Date: Sep 9, 2025, 08:57 UTC
Message-ID: <CABPp-BEh1UYwQsFhF_9uHEOi_xfhUJppXcSbJkQv_VuaAbAR0w@mail.gmail.com>
In-Reply-To: <bff456860268a833078b273ff34e3bc26a0c3975.1757274320.git.gitgitgadget@gmail.com>

On Sun, Sep 7, 2025 at 12:46 PM Ezekiel Newren via GitGitGadget <gitgitgadget@gmail.com> wrote:

Show 5 quoted lines

>
> From: Ezekiel Newren <ezekielnewren@gmail.com>
>
> When 0 <= i < xdfile_t.nreff the following is true:
> xdfile_t.ha[i] == xdfile_t.recs[xdfile_t.rindex[i]]

I like getting rid of redundant stuff. One thing to note here is that you're replacing a single indirection with two...

Show 41 quoted lines

>
> Signed-off-by: Ezekiel Newren <ezekielnewren@gmail.com>
> ---
>  xdiff/xdiffi.c   | 24 ++++++++++++++----------
>  xdiff/xprepare.c | 12 ++----------
>  xdiff/xtypes.h   |  1 -
>  3 files changed, 16 insertions(+), 21 deletions(-)
>
> diff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c
> index bbf0161f84..11cd090b53 100644
> --- a/xdiff/xdiffi.c
> +++ b/xdiff/xdiffi.c
> @@ -22,6 +22,11 @@
>
>  #include "xinclude.h"
>
> +static unsigned long get_hash(xdfile_t *xdf, long index)
> +{
> +       return xdf->recs[xdf->rindex[index]]->ha;
> +}
> +
>  #define XDL_MAX_COST_MIN 256
>  #define XDL_HEUR_MIN_COST 256
>  #define XDL_LINE_MAX (long)((1UL << (CHAR_BIT * sizeof(long) - 1)) - 1)
> @@ -42,8 +47,8 @@ typedef struct s_xdpsplit {
>   * using this algorithm, so a little bit of heuristic is needed to cut the
>   * search and to return a suboptimal point.
>   */
> -static long xdl_split(unsigned long const *ha1, long off1, long lim1,
> -                     unsigned long const *ha2, long off2, long lim2,
> +static long xdl_split(xdfile_t *xdf1, long off1, long lim1,
> +                     xdfile_t *xdf2, long off2, long lim2,
>                       long *kvdf, long *kvdb, int need_min, xdpsplit_t *spl,
>                       xdalgoenv_t *xenv) {
>         long dmin = off1 - lim2, dmax = lim1 - off2;
> @@ -87,7 +92,7 @@ static long xdl_split(unsigned long const *ha1, long off1, long lim1,
>                                 i1 = kvdf[d + 1];
>                         prev1 = i1;
>                         i2 = i1 - d;
> -                       for (; i1 < lim1 && i2 < lim2 && ha1[i1] == ha2[i2]; i1++, i2++);
> +                       for (; i1 < lim1 && i2 < lim2 && get_hash(xdf1, i1) == get_hash(xdf2, i2); i1++, i2++);

You're not going to be happy with me asking, so sorry in advance, but I'm really curious...we are now replacing a single indirection with a double-indirection inside a for loop, which is nested within two other for loops. Three levels of for-loops to me suggests it might be a hot codepath. Does this double indirection in these codepaths affect performance?

Show 120 quoted lines

>                         if (i1 - prev1 > xenv->snake_cnt)
>                                 got_snake = 1;
>                         kvdf[d] = i1;
> @@ -124,7 +129,7 @@ static long xdl_split(unsigned long const *ha1, long off1, long lim1,
>                                 i1 = kvdb[d + 1] - 1;
>                         prev1 = i1;
>                         i2 = i1 - d;
> -                       for (; i1 > off1 && i2 > off2 && ha1[i1 - 1] == ha2[i2 - 1]; i1--, i2--);
> +                       for (; i1 > off1 && i2 > off2 && get_hash(xdf1, i1 - 1) == get_hash(xdf2, i2 - 1); i1--, i2--);
>                         if (prev1 - i1 > xenv->snake_cnt)
>                                 got_snake = 1;
>                         kvdb[d] = i1;
> @@ -159,7 +164,7 @@ static long xdl_split(unsigned long const *ha1, long off1, long lim1,
>                                 if (v > XDL_K_HEUR * ec && v > best &&
>                                     off1 + xenv->snake_cnt <= i1 && i1 < lim1 &&
>                                     off2 + xenv->snake_cnt <= i2 && i2 < lim2) {
> -                                       for (k = 1; ha1[i1 - k] == ha2[i2 - k]; k++)
> +                                       for (k = 1; get_hash(xdf1, i1 - k) == get_hash(xdf2, i2 - k); k++)
>                                                 if (k == xenv->snake_cnt) {
>                                                         best = v;
>                                                         spl->i1 = i1;
> @@ -183,7 +188,7 @@ static long xdl_split(unsigned long const *ha1, long off1, long lim1,
>                                 if (v > XDL_K_HEUR * ec && v > best &&
>                                     off1 < i1 && i1 <= lim1 - xenv->snake_cnt &&
>                                     off2 < i2 && i2 <= lim2 - xenv->snake_cnt) {
> -                                       for (k = 0; ha1[i1 + k] == ha2[i2 + k]; k++)
> +                                       for (k = 0; get_hash(xdf1, i1 + k) == get_hash(xdf2, i2 + k); k++)
>                                                 if (k == xenv->snake_cnt - 1) {
>                                                         best = v;
>                                                         spl->i1 = i1;
> @@ -260,13 +265,12 @@ static long xdl_split(unsigned long const *ha1, long off1, long lim1,
>  int xdl_recs_cmp(xdfile_t *xdf1, long off1, long lim1,
>                  xdfile_t *xdf2, long off2, long lim2,
>                  long *kvdf, long *kvdb, int need_min, xdalgoenv_t *xenv) {
> -       unsigned long const *ha1 = xdf1->ha, *ha2 = xdf2->ha;
>
>         /*
>          * Shrink the box by walking through each diagonal snake (SW and NE).
>          */
> -       for (; off1 < lim1 && off2 < lim2 && ha1[off1] == ha2[off2]; off1++, off2++);
> -       for (; off1 < lim1 && off2 < lim2 && ha1[lim1 - 1] == ha2[lim2 - 1]; lim1--, lim2--);
> +       for (; off1 < lim1 && off2 < lim2 && get_hash(xdf1, off1) == get_hash(xdf2, off2); off1++, off2++);
> +       for (; off1 < lim1 && off2 < lim2 && get_hash(xdf1, lim1 - 1) == get_hash(xdf2, lim2 - 1); lim1--, lim2--);
>
>         /*
>          * If one dimension is empty, then all records on the other one must
> @@ -285,7 +289,7 @@ int xdl_recs_cmp(xdfile_t *xdf1, long off1, long lim1,
>                 /*
>                  * Divide ...
>                  */
> -               if (xdl_split(ha1, off1, lim1, ha2, off2, lim2, kvdf, kvdb,
> +               if (xdl_split(xdf1, off1, lim1, xdf2, off2, lim2, kvdf, kvdb,
>                               need_min, &spl, xenv) < 0) {
>
>                         return -1;
> diff --git a/xdiff/xprepare.c b/xdiff/xprepare.c
> index 91b0ed54e0..59730989a3 100644
> --- a/xdiff/xprepare.c
> +++ b/xdiff/xprepare.c
> @@ -134,7 +134,6 @@ static void xdl_free_ctx(xdfile_t *xdf)
>
>         xdl_free(xdf->rindex);
>         xdl_free(xdf->rchg - 1);
> -       xdl_free(xdf->ha);
>         xdl_free(xdf->recs);
>         xdl_cha_free(&xdf->rcha);
>  }
> @@ -147,7 +146,6 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_
>         char const *blk, *cur, *top, *prev;
>         xrecord_t *crec;
>
> -       xdf->ha = NULL;
>         xdf->rindex = NULL;
>         xdf->rchg = NULL;
>         xdf->recs = NULL;
> @@ -182,8 +180,6 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_
>             (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF)) {
>                 if (!XDL_ALLOC_ARRAY(xdf->rindex, xdf->nrec + 1))
>                         goto abort;
> -               if (!XDL_ALLOC_ARRAY(xdf->ha, xdf->nrec + 1))
> -                       goto abort;
>         }
>
>         xdf->rchg += 1;
> @@ -301,9 +297,7 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd
>              i <= xdf1->dend; i++, recs++) {
>                 if (dis1[i] == 1 ||
>                     (dis1[i] == 2 && !xdl_clean_mmatch(dis1, i, xdf1->dstart, xdf1->dend))) {
> -                       xdf1->rindex[nreff] = i;
> -                       xdf1->ha[nreff] = (*recs)->ha;
> -                       nreff++;
> +                       xdf1->rindex[nreff++] = i;
>                 } else
>                         xdf1->rchg[i] = 1;
>         }
> @@ -313,9 +307,7 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd
>              i <= xdf2->dend; i++, recs++) {
>                 if (dis2[i] == 1 ||
>                     (dis2[i] == 2 && !xdl_clean_mmatch(dis2, i, xdf2->dstart, xdf2->dend))) {
> -                       xdf2->rindex[nreff] = i;
> -                       xdf2->ha[nreff] = (*recs)->ha;
> -                       nreff++;
> +                       xdf2->rindex[nreff++] = i;
>                 } else
>                         xdf2->rchg[i] = 1;
>         }
> diff --git a/xdiff/xtypes.h b/xdiff/xtypes.h
> index 8b8467360e..85848f1685 100644
> --- a/xdiff/xtypes.h
> +++ b/xdiff/xtypes.h
> @@ -52,7 +52,6 @@ typedef struct s_xdfile {
>         char *rchg;
>         long *rindex;
>         long nreff;
> -       unsigned long *ha;
>  } xdfile_t;
>
>  typedef struct s_xdfenv {
> --
> gitgitgadget

Other than the performance question, it looks like you've made a straightforward mechanical change as highlighted in the commit message.