xdiff/xprepare: improve O(n*m) performance in xdl_cleanup_records()
authorTay Ray Chuan <rctay89@gmail.com>
Wed, 17 Aug 2011 01:53:57 +0000 (09:53 +0800)
committerJunio C Hamano <gitster@pobox.com>
Thu, 18 Aug 2011 00:15:05 +0000 (17:15 -0700)
commit27af01d552331eacf1ed2671b2b4b6ad4c268106
treef74cdcae565bca29ad0ee78fb539d4e4df50738d
parent4bfe7cb6668c43c1136304bbb17eea1b3ddf0237
xdiff/xprepare: improve O(n*m) performance in xdl_cleanup_records()

In xdl_cleanup_records(), we see O(n*m) performance, where n is the
number of records from xdf->dstart to xdf->dend, and m is the size of a
bucket in xdf->rhash (<= by mlim).

Here, we improve this to O(n) by pre-computing nm (in rcrec->len(1|2))
in xdl_classify_record().

Reported-by: Marat Radchenko <marat@slonopotamus.org>
Signed-off-by: Tay Ray Chuan <rctay89@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
xdiff/xprepare.c