children, n^2 and solutions?

Matt Mackall mpm at selenic.com
Tue Jul 27 15:47:17 CDT 2010


On Tue, 2010-07-27 at 19:04 +0200, Benoit Boissinot wrote:
> On Tue, Jul 27, 2010 at 3:28 AM, Nicolas Dumazet <nicdumz at gmail.com> wrote:
> > - For operations outside of MacHg? Just consider the operations ADDING
> > changesets for now.  You can use the set of heads as a cache
> > key/identifier for your cache, save it on disk with the cache, and you
> > win.
> 
> Actually, unless we have a heads cache (we have branchheads, but
> probably not heads),
> there isn't any reason why heads would be faster than debugdag, it's
> just a plain DAG walking in both cases, using only the index.

$ time hg heads -qt
201733:0621979997a2

real	0m1.220s
user	0m1.107s
sys	0m0.093s

$ time hg debugdag -q > /dev/null

real	0m2.919s
user	0m2.780s
sys	0m0.100s

$ time hg tip -q
201733:0621979997a2

real	0m0.146s
user	0m0.100s
sys	0m0.033s

$ time hg log -r -100:tip | wc
    558    2191   21665

real	0m0.694s
user	0m0.590s
sys	0m0.100s

$ time hg log -qr -100:tip | wc
    100     100    2000

real	0m0.152s
user	0m0.130s
sys	0m0.017s

Simple cache algorithm:

buildcache():
  read graph from debugdag
  read log -q for last 100 csets
  read date of changelog
  add both to cache

checkcache():
  if date of changelog has changed:
    read log -q of last 100 csets
    find first changed cset
    if found: # small change
      truncate cache if needed
      use hg log to rebuild remainder
    if not found: # big change
      buildcache



-- 
Mathematics is the supreme nostalgia of our time.




More information about the Mercurial-devel mailing list