( )⚙ D2634 [DRAFT] xdiff: avoid hashing trimmed lines

This is an archive of the discontinued Mercurial Phabricator instance.

Differential D2634

[DRAFT] xdiff: avoid hashing trimmed lines
AbandonedPublic

Authored by quark on Mar 3 2018, 11:21 PM.

Details

Reviewers
None
Group Reviewers
hg-reviewers
Summary

Things are a bit faster now:

hg perfbdiff --count 3000 --blocks --xdiff .hg/store/data/mercurial/commands.py.i 1
# before
! wall 1.510821 comb 1.500000 user 1.500000 sys 0.000000 (best of 6)
# after
! wall 1.025628 comb 1.020000 user 1.020000 sys 0.000000 (best of 8)

Diff Detail

Repository
rHG Mercurial
Lint
Lint Skipped
Unit
Unit Tests Skipped

Event Timeline

quark created this revision.Mar 3 2018, 11:21 PM
quark abandoned this revision.Mar 4 2018, 7:50 PM

D2686 is a better fix

Revision Contents
Changeset List

Diff 6535

mercurial/thirdparty/xdiff/xprepare.c

goto abort; goto abort;
if (!(recs = (xrecord_t **) xdl_malloc(narec * sizeof(xrecord_t *)))) if (!(recs = (xrecord_t **) xdl_malloc(narec * sizeof(xrecord_t *))))
goto abort; goto abort;
nrec = 0; nrec = 0;
if ((cur = blk = xdl_mmfile_first(mf, &bsize)) != NULL) { if ((cur = blk = xdl_mmfile_first(mf, &bsize)) != NULL) {
for (top = blk + bsize; cur < top; ) { for (top = blk + bsize; cur < top; ) {
prev = cur; prev = cur;
hav = xdl_hash_record(&cur, top, xpp->flags); xdl_next_record(&cur, top);
if (nrec >= narec) { if (nrec >= narec) {
narec *= 2; narec *= 2;
if (!(rrecs = (xrecord_t **) xdl_realloc(recs, narec * sizeof(xrecord_t *)))) if (!(rrecs = (xrecord_t **) xdl_realloc(recs, narec * sizeof(xrecord_t *))))
goto abort; goto abort;
recs = rrecs; recs = rrecs;
} }
if (!(crec = xdl_cha_alloc(&xdf->rcha))) if (!(crec = xdl_cha_alloc(&xdf->rcha)))
goto abort; goto abort;
crec->ptr = prev; crec->ptr = prev;
crec->size = (long) (cur - prev); crec->size = (long) (cur - prev);
crec->ha = hav; crec->ha = 0;
recs[nrec++] = crec; recs[nrec++] = crec;
} }
} }
if (!(rchg = (char *) xdl_malloc((nrec + 2) * sizeof(char)))) if (!(rchg = (char *) xdl_malloc((nrec + 2) * sizeof(char))))
goto abort; goto abort;
memset(rchg, 0, (nrec + 2) * sizeof(char)); memset(rchg, 0, (nrec + 2) * sizeof(char));
static int xdl_prepare_hashtable(unsigned int pass, long reserved, mmfile_t static int xdl_prepare_hashtable(unsigned int pass, long reserved, mmfile_t
*mf, xpparam_t const *xpp, xdlclassifier_t *cf, xdfile_t *xdf) *mf, xpparam_t const *xpp, xdlclassifier_t *cf, xdfile_t *xdf)
{ {
xrecord_t **rhash = NULL; xrecord_t **rhash = NULL;
long nrec; long nrec;
unsigned int hbits; unsigned int hbits;
long hsize; long hsize;
long i; long i, j;
long start = xdf->dstart - reserved; long start = xdf->dstart - reserved;
long end = xdf->dend + reserved; long end = xdf->dend + reserved;
if (start < 0) if (start < 0)
start = 0; start = 0;
if (end >= xdf->nrec) if (end >= xdf->nrec)
end = xdf->nrec - 1; end = xdf->nrec - 1;
nrec = end - start; nrec = end - start;
hbits = xdl_hashbits((unsigned int) nrec); hbits = xdl_hashbits((unsigned int) nrec);
hsize = 1 << hbits; hsize = 1 << hbits;
if (!(rhash = (xrecord_t **) xdl_malloc(hsize * sizeof(xrecord_t *)))) if (!(rhash = (xrecord_t **) xdl_malloc(hsize * sizeof(xrecord_t *))))
goto abort; goto abort;
memset(rhash, 0, hsize * sizeof(xrecord_t *)); memset(rhash, 0, hsize * sizeof(xrecord_t *));
for (i = start; i <= end; i++) { for (i = start; i <= end; i++) {
{
unsigned long ha = 5381;
char const *ptr = xdf->recs[i]->ptr;
for (j = 0; j < xdf->recs[i]->size; ++j) {
ha += (ha << 5);
ha ^= (unsigned long)ptr[j];
}
xdf->recs[i]->ha = ha;
}
if (xdl_classify_record(pass, cf, rhash, hbits, xdf->recs[i]) < 0) if (xdl_classify_record(pass, cf, rhash, hbits, xdf->recs[i]) < 0)
goto abort; goto abort;
} }
xdf->hbits = hbits; xdf->hbits = hbits;
xdf->rhash = rhash; xdf->rhash = rhash;
return 0; return 0;

mercurial/thirdparty/xdiff/xutils.h

int xdl_emit_diffrec(char const *rec, long size, char const *pre, long psize, int xdl_emit_diffrec(char const *rec, long size, char const *pre, long psize,
xdemitcb_t *ecb); xdemitcb_t *ecb);
int xdl_cha_init(chastore_t *cha, long isize, long icount); int xdl_cha_init(chastore_t *cha, long isize, long icount);
void xdl_cha_free(chastore_t *cha); void xdl_cha_free(chastore_t *cha);
void *xdl_cha_alloc(chastore_t *cha); void *xdl_cha_alloc(chastore_t *cha);
long xdl_guess_lines(mmfile_t *mf, long sample); long xdl_guess_lines(mmfile_t *mf, long sample);
int xdl_blankline(const char *line, long size, long flags); int xdl_blankline(const char *line, long size, long flags);
int xdl_recmatch(const char *l1, long s1, const char *l2, long s2, long flags); int xdl_recmatch(const char *l1, long s1, const char *l2, long s2, long flags);
void xdl_next_record(char const **data, char const *top);
unsigned long xdl_hash_record(char const **data, char const *top, long flags); unsigned long xdl_hash_record(char const **data, char const *top, long flags);
unsigned int xdl_hashbits(unsigned int size); unsigned int xdl_hashbits(unsigned int size);
int xdl_num_out(char *out, long val); int xdl_num_out(char *out, long val);
int xdl_emit_hunk_hdr(long s1, long c1, long s2, long c2, int xdl_emit_hunk_hdr(long s1, long c1, long s2, long c2,
const char *func, long funclen, xdemitcb_t *ecb); const char *func, long funclen, xdemitcb_t *ecb);
int xdl_fall_back_diff(xdfenv_t *diff_env, xpparam_t const *xpp, int xdl_fall_back_diff(xdfenv_t *diff_env, xpparam_t const *xpp,
int line1, int count1, int line2, int count2); int line1, int count1, int line2, int count2);
#endif /* #if !defined(XUTILS_H) */ #endif /* #if !defined(XUTILS_H) */

mercurial/thirdparty/xdiff/xutils.c

ha += (ha << 5); ha += (ha << 5);
ha ^= (unsigned long) *ptr; ha ^= (unsigned long) *ptr;
} }
*data = ptr < top ? ptr + 1: ptr; *data = ptr < top ? ptr + 1: ptr;
return ha; return ha;
} }
inline void xdl_next_record(char const **data, char const *top) {
char const *next = memchr(*data, '\n', top - *data);
if (next) {
*data = next + 1;
} else {
*data = top;
}
}
unsigned long xdl_hash_record(char const **data, char const *top, long flags) { unsigned long xdl_hash_record(char const **data, char const *top, long flags) {
unsigned long ha = 5381; unsigned long ha = 5381;
char const *ptr = *data; char const *ptr = *data;
if (flags & XDF_WHITESPACE_FLAGS) if (flags & XDF_WHITESPACE_FLAGS)
return xdl_hash_record_with_whitespace(data, top, flags); return xdl_hash_record_with_whitespace(data, top, flags);
for (; ptr < top && *ptr != '\n'; ptr++) { for (; ptr < top && *ptr != '\n'; ptr++) {