Re: [Monotone-devel] Netsync performance improvement patch

[Eric Anderson]

Matt Johnston writes:
 > On Fri, Aug 12, 2005 at 02:52:13PM -0700, Eric Anderson wrote:
 > > Eric Anderson writes:
 > >  > Summary: The attached patch changes the recieve buffer from a string
 > >  > to a string_queue.  This changes an O(n^2) algorithm to an O(n)
 > >  > algorithm.  The practical effect on a smallish database is a 3.48x
 > >  > CPU usage reduction on the pull side.  On a somewhat extreme case, it
 > >  > resulted in a 24.7x CPU reduction on the pull side.
 > > 
 > > Any comments from people on this fix?
 > 
 > The general approach is good I think - I'm not seeing such
 > significant improvements (119sec versus 177sec for the
 > a pull of a monotone tree with the check_sane_history() call
 > removed), but still worthwhile. I guess it depends on the
 > repository's ancestry structure - repositories with longer
 > history will be more limited by delta reconstruction etc.

It also depends on the size of the respository.  The monotone DB is
only 64MB, I have another one which has a much more trivial ancestry
structure, but is 125MB as it has much larger files in it.  

 > Trying switching the outbuf in netsync.cc to a string_queue,
 > I see a slowdown on both the client and the server side. I
 > haven't profiled that yet, so not sure why that's happening.

It was switched to a deque of strings with a index which is an offset
into each string, this has the same asymptotic performance, so the
only question is what are the constants.  I didn't change it since I
am trying to keep each patch as small as possible to speed up getting
things in; I also wasn't convinced it would be a performance boost.

 > I guess one possible objection to the patch is that
 > string_queue.hh is doing raw pointer operations, something
 > that most of the code in monotone avoids. It does appear to
 > have a fair amount of sanity checking through it - anyone
 > got thoughts on the matter?  Personally I think it might be
 > justified for a data structure like that.

I could switch it to storing a string and integer offsets into the
string, but it would effectively be the same code, and the fact that
the offsets are integers rather than pointers wouldn't help.  To me
using integers as pointers into a character array rather than just
pointers is misleading, and hence I try to avoid that.

 > I assume that a boost::circular_buffer isn't suitable since
 > that doesn't have contiguous storage?

Yes, the rest of the monotone code makes assumes that buffers are
contigous that the various buffers are all contigous.  In theory
switching to entirely non-contigous buffers would be even better from
a copy/memory usage standpoint, but that fix was going to be very
invasive, and if this patch couldn't get in, one that changes way more
seemed even less likely to get in.
        -Eric