From: Ezekiel Newren via GitGitGadget Date: Wed, 25 Mar 2026 21:11:00 GMT Subject: [PATCH v2 0/5] Xdiff cleanup part 3 Message-ID: In-Reply-To: v2 is a radical departure from v1 Changes in v2: * make the flow of xdl_cleanup_records() easier to follow There is no performance or behavioral change introduced in this patch series. === original cover letter bellow === Patch series summary: * patch 1: Introduce the ivec type * patch 2: Create the function xdl_do_classic_diff() * patches 3-4: generic cleanup * patches 5-8: convert from dstart/dend (in xdfile_t) to delta_start/delta_end (in xdfenv_t) * patches 9-10: move xdl_cleanup_records(), and related, from xprepare.c to xdiffi.c Things that will be addressed in future patch series: * Make xdl_cleanup_records() easier to read * convert recs/nrec into an ivec * convert changed to an ivec * remove reference_index/nreff from xdfile_t and turn it into an ivec * splitting minimal_perfect_hash out as its own ivec * improve the performance of the classifier and parsing/hashing lines === before this patch series typedef struct s_xdfile { xrecord_t *recs; size_t nrec; ptrdiff_t dstart, dend; bool *changed; size_t *reference_index; size_t nreff; } xdfile_t; typedef struct s_xdfenv { xdfile_t xdf1, xdf2; } xdfenv_t; === after this patch series typedef struct s_xdfile { xrecord_t *recs; size_t nrec; bool *changed; size_t *reference_index; size_t nreff; } xdfile_t; typedef struct s_xdfenv { xdfile_t xdf1, xdf2; size_t delta_start, delta_end; size_t mph_size; } xdfenv_t; Ezekiel Newren (5): xdiff/xdl_cleanup_records: delete local recs pointer xdiff/xdl_cleanup_records: make limits more clear xdiff/xdl_cleanup_records: make setting action easier to follow xdiff/xdl_cleanup_records: simplify INVESTIGATE handling for clarity xdiff/xdl_cleanup_records: use unambiguous types xdiff/xprepare.c | 89 ++++++++++++++++++++++++++++++++---------------- 1 file changed, 59 insertions(+), 30 deletions(-) base-commit: ca1db8a0f7dc0dbea892e99f5b37c5fe5861be71 Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-2156%2Fezekielnewren%2Fxdiff-cleanup-3-v2 Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-2156/ezekielnewren/xdiff-cleanup-3-v2 Pull-Request: https://github.com/git/git/pull/2156 Range-diff vs v1: 1: adf1395d20 < -: ---------- ivec: introduce the C side of ivec 2: 9bd01bce9f < -: ---------- xdiff: make classic diff explicit by creating xdl_do_classic_diff() 3: 53e4840c16 < -: ---------- xdiff: don't waste time guessing the number of lines 4: 70040ea135 < -: ---------- xdiff: let patience and histogram benefit from xdl_trim_ends() 5: 742f2d381a ! 1: 8f9165d477 xdiff: use xdfenv_t in xdl_trim_ends() and xdl_cleanup_records() @@ Metadata Author: Ezekiel Newren ## Commit message ## - xdiff: use xdfenv_t in xdl_trim_ends() and xdl_cleanup_records() + xdiff/xdl_cleanup_records: delete local recs pointer - View with --color-words. Prepare these functions to use the fields: - delta_start, delta_end. A future patch will add these fields to - xdfenv_t. + Simplify the first 2 for loops by directly indexing the xdfile.recs. + recs is unused in the last 2 for loops, remove it. Best viewed with + --color-words. Signed-off-by: Ezekiel Newren ## xdiff/xprepare.c ## @@ xdiff/xprepare.c: static bool xdl_clean_mmatch(uint8_t const *action, long i, long s, long e) { - * matches on the other file. Also, lines that have multiple matches - * might be potentially discarded if they appear in a run of discardable. */ --static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2) { -+static int xdl_cleanup_records(xdlclassifier_t *cf, xdfenv_t *xe) { + static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2) { long i, nm, mlim; - xrecord_t *recs; +- xrecord_t *recs; xdlclass_t *rcrec; + uint8_t *action1 = NULL, *action2 = NULL; + bool need_min = !!(cf->flags & XDF_NEED_MINIMAL); @@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd - * Create temporary arrays that will help us decide if - * changed[i] should remain false, or become true. */ -- if (!XDL_CALLOC_ARRAY(action1, xdf1->nrec + 1)) { -+ if (!XDL_CALLOC_ARRAY(action1, xe->xdf1.nrec + 1)) { - ret = -1; - goto cleanup; - } -- if (!XDL_CALLOC_ARRAY(action2, xdf2->nrec + 1)) { -+ if (!XDL_CALLOC_ARRAY(action2, xe->xdf2.nrec + 1)) { - ret = -1; - goto cleanup; - } -@@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd - /* - * Initialize temporary arrays with DISCARD, KEEP, or INVESTIGATE. - */ -- if ((mlim = xdl_bogosqrt((long)xdf1->nrec)) > XDL_MAX_EQLIMIT) -+ if ((mlim = xdl_bogosqrt((long)xe->xdf1.nrec)) > XDL_MAX_EQLIMIT) + if ((mlim = xdl_bogosqrt((long)xdf1->nrec)) > XDL_MAX_EQLIMIT) mlim = XDL_MAX_EQLIMIT; - for (i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart]; i <= xdf1->dend; i++, recs++) { -+ for (i = xe->xdf1.dstart, recs = &xe->xdf1.recs[xe->xdf1.dstart]; i <= xe->xdf1.dend; i++, recs++) { - rcrec = cf->rcrecs[recs->minimal_perfect_hash]; +- rcrec = cf->rcrecs[recs->minimal_perfect_hash]; ++ for (i = xdf1->dstart; i <= xdf1->dend; i++) { ++ size_t mph1 = xdf1->recs[i].minimal_perfect_hash; ++ rcrec = cf->rcrecs[mph1]; nm = rcrec ? rcrec->len2 : 0; action1[i] = (nm == 0) ? DISCARD: (nm >= mlim && !need_min) ? INVESTIGATE: KEEP; } -- if ((mlim = xdl_bogosqrt((long)xdf2->nrec)) > XDL_MAX_EQLIMIT) -+ if ((mlim = xdl_bogosqrt((long)xe->xdf2.nrec)) > XDL_MAX_EQLIMIT) + if ((mlim = xdl_bogosqrt((long)xdf2->nrec)) > XDL_MAX_EQLIMIT) mlim = XDL_MAX_EQLIMIT; - for (i = xdf2->dstart, recs = &xdf2->recs[xdf2->dstart]; i <= xdf2->dend; i++, recs++) { -+ for (i = xe->xdf2.dstart, recs = &xe->xdf2.recs[xe->xdf2.dstart]; i <= xe->xdf2.dend; i++, recs++) { - rcrec = cf->rcrecs[recs->minimal_perfect_hash]; +- rcrec = cf->rcrecs[recs->minimal_perfect_hash]; ++ for (i = xdf2->dstart; i <= xdf2->dend; i++) { ++ size_t mph2 = xdf2->recs[i].minimal_perfect_hash; ++ rcrec = cf->rcrecs[mph2]; nm = rcrec ? rcrec->len1 : 0; action2[i] = (nm == 0) ? DISCARD: (nm >= mlim && !need_min) ? INVESTIGATE: KEEP; + } @@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd - * Use temporary arrays to decide if changed[i] should remain * false, or become true. */ -- xdf1->nreff = 0; + xdf1->nreff = 0; - for (i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart]; - i <= xdf1->dend; i++, recs++) { -+ xe->xdf1.nreff = 0; -+ for (i = xe->xdf1.dstart, recs = &xe->xdf1.recs[xe->xdf1.dstart]; -+ i <= xe->xdf1.dend; i++, recs++) { ++ for (i = xdf1->dstart; i <= xdf1->dend; i++) { if (action1[i] == KEEP || -- (action1[i] == INVESTIGATE && !xdl_clean_mmatch(action1, i, xdf1->dstart, xdf1->dend))) { -- xdf1->reference_index[xdf1->nreff++] = i; -+ (action1[i] == INVESTIGATE && !xdl_clean_mmatch(action1, i, xe->xdf1.dstart, xe->xdf1.dend))) { -+ xe->xdf1.reference_index[xe->xdf1.nreff++] = i; - /* changed[i] remains false, i.e. keep */ - } else -- xdf1->changed[i] = true; -+ xe->xdf1.changed[i] = true; - /* i.e. discard */ + (action1[i] == INVESTIGATE && !xdl_clean_mmatch(action1, i, xdf1->dstart, xdf1->dend))) { + xdf1->reference_index[xdf1->nreff++] = i; +@@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd } -- xdf2->nreff = 0; + xdf2->nreff = 0; - for (i = xdf2->dstart, recs = &xdf2->recs[xdf2->dstart]; - i <= xdf2->dend; i++, recs++) { -+ xe->xdf2.nreff = 0; -+ for (i = xe->xdf2.dstart, recs = &xe->xdf2.recs[xe->xdf2.dstart]; -+ i <= xe->xdf2.dend; i++, recs++) { ++ for (i = xdf2->dstart; i <= xdf2->dend; i++) { if (action2[i] == KEEP || -- (action2[i] == INVESTIGATE && !xdl_clean_mmatch(action2, i, xdf2->dstart, xdf2->dend))) { -- xdf2->reference_index[xdf2->nreff++] = i; -+ (action2[i] == INVESTIGATE && !xdl_clean_mmatch(action2, i, xe->xdf2.dstart, xe->xdf2.dend))) { -+ xe->xdf2.reference_index[xe->xdf2.nreff++] = i; - /* changed[i] remains false, i.e. keep */ - } else -- xdf2->changed[i] = true; -+ xe->xdf2.changed[i] = true; - /* i.e. discard */ - } - -@@ xdiff/xprepare.c: cleanup: - /* - * Early trim initial and terminal matching records. - */ --static int xdl_trim_ends(xdfile_t *xdf1, xdfile_t *xdf2) { -+static int xdl_trim_ends(xdfenv_t *xe) { - long i, lim; - xrecord_t *recs1, *recs2; - -- recs1 = xdf1->recs; -- recs2 = xdf2->recs; -- for (i = 0, lim = (long)XDL_MIN(xdf1->nrec, xdf2->nrec); i < lim; -+ recs1 = xe->xdf1.recs; -+ recs2 = xe->xdf2.recs; -+ for (i = 0, lim = (long)XDL_MIN(xe->xdf1.nrec, xe->xdf2.nrec); i < lim; - i++, recs1++, recs2++) - if (recs1->minimal_perfect_hash != recs2->minimal_perfect_hash) - break; - -- xdf1->dstart = xdf2->dstart = i; -+ xe->xdf1.dstart = xe->xdf2.dstart = i; - -- recs1 = xdf1->recs + xdf1->nrec - 1; -- recs2 = xdf2->recs + xdf2->nrec - 1; -+ recs1 = xe->xdf1.recs + xe->xdf1.nrec - 1; -+ recs2 = xe->xdf2.recs + xe->xdf2.nrec - 1; - for (lim -= i, i = 0; i < lim; i++, recs1--, recs2--) - if (recs1->minimal_perfect_hash != recs2->minimal_perfect_hash) - break; - -- xdf1->dend = (long)xdf1->nrec - i - 1; -- xdf2->dend = (long)xdf2->nrec - i - 1; -+ xe->xdf1.dend = (long)xe->xdf1.nrec - i - 1; -+ xe->xdf2.dend = (long)xe->xdf2.nrec - i - 1; - - return 0; - } -@@ xdiff/xprepare.c: int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp, - xdl_classify_record(2, &cf, rec); - } - -- xdl_trim_ends(&xe->xdf1, &xe->xdf2); -+ xdl_trim_ends(xe); - if ((XDF_DIFF_ALG(xpp->flags) != XDF_PATIENCE_DIFF) && - (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF) && -- xdl_cleanup_records(&cf, &xe->xdf1, &xe->xdf2) < 0) { -+ xdl_cleanup_records(&cf, xe) < 0) { - - xdl_free_ctx(&xe->xdf2); - xdl_free_ctx(&xe->xdf1); + (action2[i] == INVESTIGATE && !xdl_clean_mmatch(action2, i, xdf2->dstart, xdf2->dend))) { + xdf2->reference_index[xdf2->nreff++] = i; 6: 65da408da9 < -: ---------- xdiff: cleanup xdl_trim_ends() 7: d74722538b < -: ---------- xdiff: replace xdfile_t.dstart with xdfenv_t.delta_start 8: d0ef5b23c4 < -: ---------- xdiff: replace xdfile_t.dend with xdfenv_t.delta_end 9: f9b10e71d2 ! 2: 62adaa8e5a xdiff: remove dependence on xdlclassifier from xdl_cleanup_records() @@ Metadata Author: Ezekiel Newren ## Commit message ## - xdiff: remove dependence on xdlclassifier from xdl_cleanup_records() + xdiff/xdl_cleanup_records: make limits more clear - Disentangle xdl_cleanup_records() from the classifier so that it can be - moved from xprepare.c into xdiffi.c. - - The classic diff is the only algorithm that needs to count the number - of times each line occurs in each file. Make xdl_cleanup_records() - count the number of lines instead of the classifier so it won't slow - down patience or histogram. + Make the handling of per-file limits and the minimal-case clearer. + * Use explicit per-file limit variables (mlim1, mlim2) and initialize + them. + * The additional condition `!need_min` is redudant now, remove it. + Best viewed with --color-words. Signed-off-by: Ezekiel Newren ## xdiff/xprepare.c ## -@@ - */ - - #include "xinclude.h" -+#include "compat/ivec.h" - - - #define XDL_KPDIS_RUN 4 -@@ xdiff/xprepare.c: typedef struct s_xdlclass { - struct s_xdlclass *next; - xrecord_t rec; - long idx; -- long len1, len2; - } xdlclass_t; - - typedef struct s_xdlclassifier { -@@ xdiff/xprepare.c: static void xdl_free_classifier(xdlclassifier_t *cf) { - } - - --static int xdl_classify_record(unsigned int pass, xdlclassifier_t *cf, xrecord_t *rec) { -+static int xdl_classify_record(xdlclassifier_t *cf, xrecord_t *rec) { - size_t hi; - xdlclass_t *rcrec; - -@@ xdiff/xprepare.c: static int xdl_classify_record(unsigned int pass, xdlclassifier_t *cf, xrecord_t - return -1; - cf->rcrecs[rcrec->idx] = rcrec; - rcrec->rec = *rec; -- rcrec->len1 = rcrec->len2 = 0; - rcrec->next = cf->rchash[hi]; - cf->rchash[hi] = rcrec; - } - -- (pass == 1) ? rcrec->len1++ : rcrec->len2++; -- - rec->minimal_perfect_hash = (size_t)rcrec->idx; - - return 0; @@ xdiff/xprepare.c: static bool xdl_clean_mmatch(uint8_t const *action, long i, long s, long e) { - return rpdis1 * XDL_KPDIS_RUN < (rpdis1 + rdis1); - } - -+struct xoccurrence -+{ -+ size_t file1, file2; -+}; -+ -+ -+DEFINE_IVEC_TYPE(struct xoccurrence, xoccurrence); -+ - - /* - * Try to reduce the problem complexity, discard records that have no - * matches on the other file. Also, lines that have multiple matches * might be potentially discarded if they appear in a run of discardable. */ --static int xdl_cleanup_records(xdlclassifier_t *cf, xdfenv_t *xe) { + static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2) { - long i, nm, mlim; -+static int xdl_cleanup_records(xdfenv_t *xe, uint64_t flags) { -+ long i; -+ size_t nm, mlim; - xrecord_t *recs; -- xdlclass_t *rcrec; ++ long i, nm; ++ size_t mlim1, mlim2; + xdlclass_t *rcrec; uint8_t *action1 = NULL, *action2 = NULL; -- bool need_min = !!(cf->flags & XDF_NEED_MINIMAL); -+ struct IVec_xoccurrence occ; -+ bool need_min = !!(flags & XDF_NEED_MINIMAL); - int ret = 0; - ptrdiff_t dend1 = xe->xdf1.nrec - 1 - xe->delta_end; - ptrdiff_t dend2 = xe->xdf2.nrec - 1 - xe->delta_end; + bool need_min = !!(cf->flags & XDF_NEED_MINIMAL); +@@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd + goto cleanup; + } -+ IVEC_INIT(occ); -+ ivec_zero(&occ, xe->mph_size); -+ -+ for (size_t j = 0; j < xe->xdf1.nrec; j++) { -+ size_t mph1 = xe->xdf1.recs[j].minimal_perfect_hash; -+ occ.ptr[mph1].file1 += 1; -+ } -+ -+ for (size_t j = 0; j < xe->xdf2.nrec; j++) { -+ size_t mph2 = xe->xdf2.recs[j].minimal_perfect_hash; -+ occ.ptr[mph2].file2 += 1; ++ if (need_min) { ++ /* i.e. infinity */ ++ mlim1 = SIZE_MAX; ++ mlim2 = SIZE_MAX; ++ } else { ++ mlim1 = XDL_MIN(xdl_bogosqrt(xdf1->nrec), XDL_MAX_EQLIMIT); ++ mlim2 = XDL_MIN(xdl_bogosqrt(xdf2->nrec), XDL_MAX_EQLIMIT); + } + /* - * Create temporary arrays that will help us decide if - * changed[i] should remain false, or become true. -@@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfenv_t *xe) { - if ((mlim = xdl_bogosqrt((long)xe->xdf1.nrec)) > XDL_MAX_EQLIMIT) - mlim = XDL_MAX_EQLIMIT; - for (i = xe->delta_start, recs = &xe->xdf1.recs[xe->delta_start]; i <= dend1; i++, recs++) { -- rcrec = cf->rcrecs[recs->minimal_perfect_hash]; -- nm = rcrec ? rcrec->len2 : 0; -+ nm = occ.ptr[recs->minimal_perfect_hash].file2; - action1[i] = (nm == 0) ? DISCARD: (nm >= mlim && !need_min) ? INVESTIGATE: KEEP; + * Initialize temporary arrays with DISCARD, KEEP, or INVESTIGATE. + */ +- if ((mlim = xdl_bogosqrt((long)xdf1->nrec)) > XDL_MAX_EQLIMIT) +- mlim = XDL_MAX_EQLIMIT; + for (i = xdf1->dstart; i <= xdf1->dend; i++) { + size_t mph1 = xdf1->recs[i].minimal_perfect_hash; + rcrec = cf->rcrecs[mph1]; + nm = rcrec ? rcrec->len2 : 0; +- action1[i] = (nm == 0) ? DISCARD: (nm >= mlim && !need_min) ? INVESTIGATE: KEEP; ++ action1[i] = (nm == 0) ? DISCARD: nm >= mlim1 ? INVESTIGATE: KEEP; } - if ((mlim = xdl_bogosqrt((long)xe->xdf2.nrec)) > XDL_MAX_EQLIMIT) - mlim = XDL_MAX_EQLIMIT; - for (i = xe->delta_start, recs = &xe->xdf2.recs[xe->delta_start]; i <= dend2; i++, recs++) { -- rcrec = cf->rcrecs[recs->minimal_perfect_hash]; -- nm = rcrec ? rcrec->len1 : 0; -+ nm = occ.ptr[recs->minimal_perfect_hash].file1; - action2[i] = (nm == 0) ? DISCARD: (nm >= mlim && !need_min) ? INVESTIGATE: KEEP; - } - -@@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfenv_t *xe) { - cleanup: - xdl_free(action1); - xdl_free(action2); -+ ivec_free(&occ); - - return ret; - } -@@ xdiff/xprepare.c: int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp, - - for (size_t i = 0; i < xe->xdf1.nrec; i++) { - xrecord_t *rec = &xe->xdf1.recs[i]; -- xdl_classify_record(1, &cf, rec); -+ xdl_classify_record(&cf, rec); +- if ((mlim = xdl_bogosqrt((long)xdf2->nrec)) > XDL_MAX_EQLIMIT) +- mlim = XDL_MAX_EQLIMIT; + for (i = xdf2->dstart; i <= xdf2->dend; i++) { + size_t mph2 = xdf2->recs[i].minimal_perfect_hash; + rcrec = cf->rcrecs[mph2]; + nm = rcrec ? rcrec->len1 : 0; +- action2[i] = (nm == 0) ? DISCARD: (nm >= mlim && !need_min) ? INVESTIGATE: KEEP; ++ action2[i] = (nm == 0) ? DISCARD: nm >= mlim2 ? INVESTIGATE: KEEP; } - for (size_t i = 0; i < xe->xdf2.nrec; i++) { - xrecord_t *rec = &xe->xdf2.recs[i]; -- xdl_classify_record(2, &cf, rec); -+ xdl_classify_record(&cf, rec); - } - -+ xe->mph_size = cf.count; -+ - xdl_trim_ends(xe); - if ((XDF_DIFF_ALG(xpp->flags) != XDF_PATIENCE_DIFF) && - (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF) && -- xdl_cleanup_records(&cf, xe) < 0) { -+ xdl_cleanup_records(xe, xpp->flags) < 0) { - - xdl_free_ctx(&xe->xdf2); - xdl_free_ctx(&xe->xdf1); - - ## xdiff/xtypes.h ## -@@ xdiff/xtypes.h: typedef struct s_xdfile { - typedef struct s_xdfenv { - xdfile_t xdf1, xdf2; - size_t delta_start, delta_end; -+ size_t mph_size; - } xdfenv_t; - - + /* 10: 1dba6b34aa < -: ---------- xdiff: move xdl_cleanup_records() from xprepare.c to xdiffi.c -: ---------- > 3: 8be7e4781a xdiff/xdl_cleanup_records: make setting action easier to follow -: ---------- > 4: 6abd052c34 xdiff/xdl_cleanup_records: simplify INVESTIGATE handling for clarity -: ---------- > 5: a52787f019 xdiff/xdl_cleanup_records: use unambiguous types -- gitgitgadget