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.

Download Raw Diff

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

Herald added a reviewer: hg-reviewers. · View Herald TranscriptMar 3 2018, 11:21 PM

Herald added a subscriber: mercurial-devel. · View Herald Transcript

D2686 is a better fix

Revision Contents
Changeset List

			Path	Packages
M			mercurial/thirdparty/xdiff/xprepare.c (16 lines)
M			mercurial/thirdparty/xdiff/xutils.h (1 line)
M			mercurial/thirdparty/xdiff/xutils.c (9 lines)

Status	Author	Revision
Abandoned	quark	D2634 [DRAFT] xdiff: avoid hashing trimmed lines
Abandoned	quark	D2631 [DRAFT] xdiff: skip trimmed lines when preparing the hashtable
Abandoned	quark	D2630 xdiff: move hashtable calculation to a separate function
Abandoned	quark	D2629 xdiff: do not rely on hashtable in xdl_trim_ends
Abandoned	quark	D2628 xdiff: expand xdl_optimize_ctxs

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++) {

Diff	ID	Base	Description	Created	Lint	Unit
Base			Base
Diff 1	6535			Mar 3 2018, 11:21 PM	★	★