From: Tay Ray Chuan Date: Fri, 19 Aug 2011 17:12:49 GMT Subject: Re: [PATCH v2] xdiff/xprepare: improve O(n*m) performance in xdl_cleanup_records() Message-ID: In-Reply-To: <20110818224427.GB8481@sigill.intra.peff.net> On Fri, Aug 19, 2011 at 6:44 AM, Jeff King wrote: > On Wed, Aug 17, 2011 at 11:55:32PM +0800, Tay Ray Chuan wrote: > >> On Wed, Aug 17, 2011 at 1:21 PM, Jeff King wrote: >> > Wait, what? It was using 0 seconds of user time before, but still taking >> > 8.5 seconds? What was it doing? Did you actually warm up your disk cache >> > before taking these measurements? >> >> Three runs on the same machine, after a restart. >> >>   $ time git show >/dev/null >> >>   real    0m6.505s >>   user    0m0.031s >>   sys     0m0.015s >> [...] > > So it is spending only .046s of CPU time, but is taking 6.5 seconds of > wall clock time. Which implies to me that the dataset doesn't fit in > your disk cache, or it is swapping a lot. Or you are on a really > bogged-down multiuser system. :) > > But if I understand correctly, your patch is about increasing runtime > performance of a slow algorithm. So is actually the improvement of an > O(m*n) algorithm to an O(n) one, or does your new algorithm have better > memory access patterns that avoid trashing swap? > > [snip] > > So I think your patch _is_ an improvement in algorithmic runtime. I just > don't see how your numbers make any sense. Am I missing something? Is > msysgit's bash "time" just broken? Nope, available memory is more than enough, so I don't believe swapping is taking place. I think it's more likely that it's an issue with time on msysgit. Johannes, care to shed some light on this? -- Cheers, Ray Chuan