author | Tay Ray Chuan <rctay89@gmail.com> | |
Wed, 17 Aug 2011 01:53:57 +0000 (09:53 +0800) | ||
committer | Junio C Hamano <gitster@pobox.com> | |
Thu, 18 Aug 2011 00:15:05 +0000 (17:15 -0700) | ||
commit | 27af01d552331eacf1ed2671b2b4b6ad4c268106 | |
tree | f74cdcae565bca29ad0ee78fb539d4e4df50738d | tree | snapshot |
parent | 4bfe7cb6668c43c1136304bbb17eea1b3ddf0237 | commit | diff |
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>
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 | diff | blob | history |