From: Elijah Newren Date: Tue, 09 Sep 2025 08:57:23 GMT Subject: Re: [PATCH 06/17] xdiff: delete redundant array xdfile_t.ha Message-ID: In-Reply-To: On Sun, Sep 7, 2025 at 12:46 PM Ezekiel Newren via GitGitGadget wrote: > > From: Ezekiel Newren > > 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... > > Signed-off-by: Ezekiel Newren > --- > 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? > 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.