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

From: Jeff King <peff@peff.net>
Date: Aug 18, 2011, 22:44 UTC
Message-ID: <20110818224427.GB8481@sigill.intra.peff.net>
In-Reply-To: <CALUzUxovdmhnRKPaEq01-q0pvez91s_Z_rHWg-FkwcU0VD3HQQ@mail.gmail.com>

On Wed, Aug 17, 2011 at 11:55:32PM +0800, Tay Ray Chuan wrote:

Show 13 quoted lines

> 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?

Downloading the files from the original problem report, I see much different timings:

  [before]
  $ time git diff >/dev/null
  real    0m7.690s
  user    0m7.648s
  sys     0m0.024s

  [after (your v2 patch)]
  real    0m0.272s
  user    0m0.236s
  sys     0m0.036s

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?

-Peff