Re: [Monotone-devel] Monotone performance degrades dramatically

[Nathaniel Smith]

On Thu, Aug 31, 2006 at 10:45:34AM -0700, Steven Grimm wrote:
> Then I wrote the following simple shell script to make repeated trivial 
> changes.
> 
> #!/bin/sh
> i=1
> while true; do
>        echo $i > testfile
>        echo "update to $i" > comment
>        echo $i `date`
>        i=`expr $i + 1`
>        mtn -d /var/tmp/mtnperf/test.db commit --message-file comment
> done
> 
> And I am definitely seeing performance degrade. The first 20 revisions 
> took about 6 seconds to get through; now it's up at revision 485 and 
> it's taking 2 seconds per commit. While it's sitting there it is chewing 
> 100% of one of the machine's CPUs, so it doesn't seem to be I/O bound.

As several people pointed out in this thread, 'commit' does a scan for
heads, which is necessarily linear in the total size of the branch (or
ancestry graph, or anyway something of that order of magnitude).  And,
as several people have also pointed out lately, the head-finding
operation has gotten unreasonably slow lately :-).

The old head scanner takes quadratic memory (not usually a problem,
because the constants were low and everyone has gobs of memory these
days, but we noticed this while testing things on the 150,000
revision netbsd branch that Dan Carosone has), and has to do
cert/trust calculations for every revision in the branch (which is
quite expensive on the CPU).

I just rewrote it; the new scanner takes only linear memory, and
has to do O(log n) trust evaluations ("roughly" because it's a
randomized algorithm, and also there's some dependence on the shape of
the graph and the frequency of failing certs).  It clocks in at <10s
cpu time on the netbsd mainline.

I've been running your script against current mainline while writing
this email; it's currently at 1300 revisions committed, and while it
is slower now than when it started, it's still at <1s per commit.

So, you might just try your tests again with current mainline, which
will become 0.30.

-- Nathaniel

-- 
So let us espouse a less contested notion of truth and falsehood, even
if it is philosophically debatable (if we listen to philosophers, we
must debate everything, and there would be no end to the discussion).
  -- Serendipities, Umberto Eco