[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: Stefan Sperling <stsp_at_elego.de>
Date: Sun, 11 Sep 2011 10:12:01 +0200

On Sat, Sep 10, 2011 at 08:48:50PM +0300, Daniel Shahaf wrote:
> 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).
>
> Stefan debugged this and found that most time is spent in
> combine_with_lastrange(). (Backtrace attached.)
>
> Adding a debug print (patch attached) just above the qsort() shows an
> interesting pattern:
>
> [[[
> DBG: mergeinfo.c: 439: Sorting with 253 elements
> DBG: mergeinfo.c: 439: Sorting with 254 elements
> DBG: mergeinfo.c: 439: Sorting with 255 elements
> DBG: mergeinfo.c: 439: Sorting with 256 elements
> DBG: mergeinfo.c: 439: Sorting with 257 elements
> DBG: mergeinfo.c: 439: Sorting with 258 elements
> DBG: mergeinfo.c: 439: Sorting with 259 elements
> DBG: mergeinfo.c: 439: Sorting with 260 elements
> DBG: mergeinfo.c: 439: Sorting with 261 elements
> DBG: mergeinfo.c: 439: Sorting with 262 elements
> DBG: mergeinfo.c: 439: Sorting with 263 elements
> ]]]
>
> That happens with both serf and neon, and Stefan reports it was fast
> yesterday (before my cherry-pick and other commits today).

As of r1167681, this merge doesn't hog the CPU anymore.
However, it runs out of memory very quickly:

$ time svn merge --reintegrate ^/subversion/branches/fs-successor-ids
Out of memory - terminating application.
Abort trap (core dumped)
    0m6.36s real 0m0.71s user 0m0.19s system

I haven't yet debugged this to the point of understanding what
is going on.
Received on 2011-09-11 10:13:14 CEST

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