From: Junio C Hamano <gitster@pobox.com>
Date: Tue, 16 Aug 2011 17:39:25 GMT
Subject: Re: [PATCH] xdiff/xprepare: improve O(n*m) performance in xdl_cleanup_records()
Message-ID: <7vd3g5i7ci.fsf@alter.siamese.dyndns.org>
In-Reply-To: <20110816113710.000025a7@unknown>

Tay Ray Chuan <rctay89@gmail.com> writes:

> From 0da9ec94604978f877e7f7c00d307b5cdbb22b29 Mon Sep 17 00:00:00 2001
> From: Tay Ray Chuan <rctay89@gmail.com>
> Date: Tue, 16 Aug 2011 11:35:28 +0800
> Subject: [PATCH] xdiff/xprepare: improve O(n*m) performance in
>  xdl_cleanup_records()

You do not need these four lines. Thanks.

> 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().

Could we have some benchmarks to let the readers get a feel of how much
improvement this patch brings in?

This tries to trade cycles with memory, right? How much bloat are we
talking about here?