Re: [PATCH v2] xdiff/xprepare: improve O(n*m) performance in xdl_cleanup_records()

From: Tay Ray Chuan <rctay89@gmail.com>
Date: Aug 19, 2011, 17:12 UTC
Message-ID: <CALUzUxoPwNhziRX3WU-YhSEXkjm_FvVLmN=pAffexr-QpmhGgg@mail.gmail.com>
In-Reply-To: <20110818224427.GB8481@sigill.intra.peff.net>

On Fri, Aug 19, 2011 at 6:44 AM, Jeff King <peff@peff.net> wrote:

Show 31 quoted lines

> 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 <peff@peff.net> 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