Re: [Monotone-devel] Re: Netsync performance improvement patch

[Eric Anderson]

graydon hoare writes:
 > In gmane.comp.version-control.monotone.devel, Eric Anderson wrote:
 > > In the long term, using a non-contigous data-structure to represent
 > > "strings" throughout the code is probably the best way to structurally
 > > reduce the memory usage, and could result in a performance boost if
 > > the lack of fast random access is taken into account.
 > 
 > You might like the SGI "rope" class, which appears on my system as
 > part of gnu libstdc++, /usr/include/c++/4.0.0/ext/rope

I had completely forgotton about that.  The document Petr pointed to
(http://complement.sourceforge.net/compare.pdf) compares strings and
ropes for "a mix of copy, insert, append, and replace" operations" The
results on the last page show that for his machine (1.33 GHz Athlon
XP, gcc 3.3.3 or 3.4.1), ropes are significantly (>2x slower) up to
around 5k long strings, and the two have the same performance around
12.5k.  As expected ropes are constant time, and strings are linear.

Unfortunately monotone's netsync has a mix of small and large
messages, depending in part on what is in the repository (small or
large files).  This makes it risky to replace strings with ropes
unless we have a fairly thorough set of performance test cases because
it would make some cases worse and some better.  Conversely the string
queue I wrote seems to be as good or better than the existing string
approach which is not a surprise as it is implemented in almost the
same way as strings just with the extra front pointer that lets
removal from the front be constant time.

 > I didn't use anything like this at first because I didn't really
 > assume there would be much mucking about with strings after
 > construction. That probably stopped being a valid assumption around
 > the time of writing netsync. Sorry for implementing it the slow way.

Nothing to be sorry about, writing something like the string_queue
from scratch would be a mistake unless you've already measured it and
found that the time is being spent in there.

 > Thanks for taking the time to investigate these performance issues.

No problem, I'm hoping to get some sort of resolution on this patch so
I can move on to some of the other ones.  A resolution to me would be
any of:
  a) "x" needs to be fixed about the patch, but it is in spirit ok, so
     with the fix will go in.
  b) the patch works around a big slowdown, so will be acceptable for
     now, but please look into alternatives as we would like to replace
     it with something else
  c) this style of patch isn't ever going to go in, another approach needs
     to be found to solve the problem.
        -Eric