[svn.haxx.se] · SVN Dev · SVN Users · SVN Org · TSVN Dev · TSVN Users · Subclipse Dev · Subclipse Users · this month's index

Re: O(n**3) behaviour in reintegrate merge

From: Paul Burba <ptburba_at_gmail.com>
Date: Wed, 28 Sep 2011 13:28:15 -0400

On Mon, Sep 12, 2011 at 4:05 PM, Stefan Sperling <stsp_at_elego.de> wrote:
> On Sun, Sep 11, 2011 at 03:56:39PM +0300, Daniel Shahaf wrote:
>> I floated on IRC the idea of having the output not try filter out
>> inoperative revisions.
> That would not completey fix the problem.
> In the case we're looking at there is one huge gap in the range of
> revisions already merged. So, yes, the output would be short if we
> collapsed inoperative revisions -- we'd just print a single range.
> However, what if I want to reintegrate a long-lived branch in which
> every other revision was a cherry-pick merge from trunk?
> In this case, the missing revisions are N, N+2, N+4, ...
> which cannot be combined into a single range. This is a contrived case,
> of course. But I'd prefer a solution that cannot cause such problems
> under any circumstances.
> We shouldn't try to keep a list of unknown and potentially massive
> size in memory. So putting this list into an error message is wrong.
> At the very least, we should pass off ranges to a client-provided callback
> as we receive them from the server. Then the client can print each range
> and the range can be freed immediately before the server sends the next one.
> But, again, I don't see how printing a precise, but massive, list of
> missing revisions helps users. The time spent downloading and displaying
> all this information could be better spent if we told users "there are
> one or more missing ranges, please run a sync merge from trunk first,
> and try again."

Some relevant discussion about this on IRC today (scroll to the bottom
if you want the summary :-):

<stsp> pburba, any news on the '--reintegrate presents missing ranges
to the user' discussion?
<stsp> i was about to poke on dev@ about it
<stsp> as things stand, i think the feature should be removed in 1.7.1
and further
<stsp> and just say "there are some missing ranges"
<stsp> (would've been nice to fix this for .0, but I was too busy with
other stuff for 2 weeks to pursue this discussion)

<pburba> stsp: THe 'O(n**3) behaviour in reintegrate merge' thread?

<stsp> pburba, yes
<stsp> we've fixed the qsort() problem,
<stsp> which we still need to backport,
<stsp> but the fix revealed another underlying issue

<pburba> stsp: As an aside I am working right now on the memory bloat
of svn_rangelist_merge2, which applies to more than just that issue.
It's still pretty gruesome

<stsp> the basic problem is that the list of missing ranges can grow
too large to be held in memory,
<stsp> and too large to be of value to the user
<stsp> even if we fix all memory leaks,

<pburba> stsp: Let's agree those are two separate problems yes?

<stsp> if there are too many revs to show there is a problem

<pburba> The first is what I'm working on now...

<stsp> pburba, yes, separate problems

<pburba> ...as to that (the second)

<stsp> however, i think the problem of deciding to construct the list
of missing ranges in the first place is the bigger issue
<stsp> the pool/iterpool fixes are nice but don't provide an immediate fix
<stsp> they just allow the list to grow a bit further before svn runs
out of memory

<markphip> I think showing the ranges is somewhat important for
usability. We could potentially not show all of them or word it
<markphip> but when 1.5.0 came out, we did not show them and it was a
nightmare because you had no idea what the problem was

<pburba> stsp: No you misunderstand, I am *working* on an uncommitted
fix. There is no way that a bit of mergeinfo should use up too much
memory. In a patch I have right now mempory use in danielsh's example
drops from 1.3GB to 27KB

<stsp> say you have a branch where every other revision was a
cherry-pick merge, and you have N outstanding revisions
<stsp> you'll have to show N/2 ranges because you cannot collapse them

<pburba> markphip: Agreed.

<stsp> so, while collapsing the ranges might fix the specific instance
of the problem which we are seeing (where is one huge gap), it will
still be bad for cases with many gaps

<pburba> stsp: Well then aren't yo uabusing the sync-merge/reintegrate model?

<stsp> so i think the approach is flawed

<pburba> stsp: Maybe I'm misunderstanding your use case

<stsp> pburba, depends on the branching/merging pattern you use

<markphip> stsp: not exactly

<stsp> basically, the tool will fail if you decide to reintegrate some
branch that has received lots of cherry-picking merges

<danielsh> pburba: that's a 99.998% improvement!

<markphip> in your example, --reintegrate can never be used. Running
out of memory is never good, but user cannot use reintegrate anyway

<stsp> markphip, sure
<stsp> the point of the error message is to alert the user of that fact
<stsp> but we never get to print it
<stsp> because we run out of memory first
<stsp> it is a bad idea to construct an error message that is many MB in size

<markphip> the point is that with a proper fix, only an extreme
example, such as 10 million cherry picked revisions is going to cause
a problem

<stsp> no

<markphip> to a user that entered the wrong option

<stsp> the problem already happens when the error message becomes to
large to be useful

<pburba> stsp: Again, I believe I can fix that problem. The error
message is not multiple MB, it's a bug in svn_rangelist_merge2

<stsp> the user will get tons of output if svn doesn't run out of memory

<markphip> but who is to say at what point it is no longer useful?

<danielsh> can 'svn mergeinfo' subcommand be used to get the revision
numbers that the error message wants to contain?

<markphip> I think we agree with small numbers of revisions it is useful?
<markphip> so what is the cut off?

<stsp> danielsh, that's what I was thinking: tell people to run 'svn
mergeinfo' if they want to know which ranges are missing

<pburba> stsp: Ok, maybe we want to truncate the error message after X
number of missing ranges, but doing away with it entirely makes no

<stsp> instead of constructing the error messages (which takes time in
any case -- time wasted if the user doesn't care which ranges are
<stsp> pburba, yes, we could either cap after some limit,
<stsp> or just error out quickly and let users know how to get at the
list of missing ranges
<stsp> i would prefer the second approach
<stsp> because the error happens sooner, and the user can still get at
the information if required

<markphip> does svn mergeinfo give the answer currently? I know it
did not used to

<stsp> if it does not then we should fix it

<pburba> markphip: It should give the right answer if we ask for the right range

So basically there is a memory leak with svn_rangelist_merge*() which
is exposed by the way we create the error message. I'm working on
that, but it is largely a separate issue.

The issue to be decided here is what error message to provide when a
reintegrate merge fails because the source is not fully synced with
the target:

1) Current behavior: Issue an error message describing the unsynced
revs and which

>svn merge ^^/branch-X A --reintegrate
..\..\..\subversion\svn\merge-cmd.c:382: (apr_err=195016)
..\..\..\subversion\libsvn_client\merge.c:10904: (apr_err=195016)
..\..\..\subversion\libsvn_client\merge.c:10873: (apr_err=195016)
..\..\..\subversion\libsvn_client\merge.c:10873: (apr_err=195016)
..\..\..\subversion\libsvn_client\merge.c:10811: (apr_err=195016)
svn: E195016: Reintegrate can only be used if revisions 2 through 12
were previously merged from
to the reintegrate source, but this is not the case:
    Missing ranges: /A:3-4

2) Same as #1 but truncate the output after N revisions and/or M sources

3) No detailed error message, instead suggest that a sync merge be run first.

4) No detailed error message, instead suggest the specific 'svn
mergeinfo' command that must be run to find any unsynced revisions.

Personally I'm happy with the current solution (once the memory bloat
has been fixed of course). Daniel's original example in this thread,

  "After cherry-picking r1167546 from trunk to the fs-successor-ids branch
   in r1167550, reintegrating that branch to trunk takes a long time
   (sufficiently long for the server to assume the client has disconnected)."

seems to me to be a purposeful abuse of what reintegrate is intended
to support. The fs-successor-ids branch was copied from trunk_at_880535
in r880536 and *never* synced with trunk. The only change from trunk
brought to fs-successor-ids was the single cherry-pick of r1167546.
So obviously the reintegrate merge is going to fail and in this case
the intervening 287010 missing revisions result in a rather unwieldy
error message.

I think the far more common use case (based on customer questions I
have dealt with) is where a user has been keeping a branch in sync
with "trunk" but somewhere along the line did a subtree merge, or is
otherwise missing some "reasonably" small part of trunk. In those
cases the error messages pinpoint the problem down the the specific
subtree with mergeinfo.

Keep in mind this error has been around since 1.5.5 and I don't see a
lot of complaints about it.


P.S. I'm out of the office the remainder of today so might not get
right back to you.
Received on 2011-09-28 19:28:47 CEST

This is an archived mail posted to the Subversion Dev mailing list.

This site is subject to the Apache Privacy Policy and the Apache Public Forum Archive Policy.