[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: Daniel Shahaf <d.s_at_daniel.shahaf.name>
Date: Sun, 11 Sep 2011 15:56:39 +0300

I floated on IRC the idea of having the output not try filter out
inoperative revisions.

Stefan Sperling wrote on Sun, Sep 11, 2011 at 14:53:36 +0200:
> On Sun, Sep 11, 2011 at 10:12:01AM +0200, Stefan Sperling wrote:
> > 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.
>
> After fixing some memory leaks it gets a bit further.
> (I will commit those fixes later when I've run tests on them.)
>
> However, the real problem seems to be the list of missing ranges
> that merge --reintegrate intends to print to stdout to inform the
> user which ranges still need to be merged.
>
> Below is a *small* excerpt of what I see when I print intermediate states
> of this range list (from within log_find_operative_revs()) before svn
> eventually runs out of memory (with a per-process memory limit of 512MB).
>
> Should Subversion detect when the number of ranges gets too large to
> be useful, stop, and print something like "too many ranges to display"?
> There isn't any other value in this feature than informing users
> about missing ranges, is there? Is this feature is really useful?
> Maybe we should just suggest that users run something like
> "svn mergeinfo --show-revs eligble BRANCH_URL" if they want to see
> the list of missing ranges?
>
> ...
> 68264,1068411,1068436,1068475-1068478,1068516,1068519-1068520,1068523,1068541-1068542,1068544,1068547,1068566,1068569,1068578,1068584-1068586,1068592,1068594,1068597,1068601,1068605,1068613,1068667,1068676,1068748-1068751,1068754,1068757,1068798,1068802,1068814,1068848,1068863,1068886,1068927,1068977,1068988,1068995,1069001,1069140,1069145,1069149,1069158,1069162,1069329-1069331,1069335,1069399,1069408,1069419,1069437,1069452,1069465,1069519,1069527,1069547,1069558,1069572,1069588,1069591,1069602,1069604,1069652,1069668,1069743,1069789,1069791,1069821,1069946,1069960-1069961,1069963,1069978,1070074,1070113,1070115-1070117,1070121,1070162,1070216,1070220,1070224,1070376-1070377,1070402,1070429,1070441,1070473,1070508,1070510,1070543,1070582,1070629-1070630,1070644,1070684-1070685,1070689,1070788,1070833,1070847,1070861,1070892,1070909,1070912,1070920,1070930,1070969,1070980-1070981,1070983,1070985-1070986,1070990,1071014,1071025,1071029,1071081,1071214,1071228,1071239,1071279,1071283,1071304,1071307,1071357
,1
> 071368,1071373,1071602,1071625,1071632-1071633,1071650,1071679,1071707,1071711,1071729,1071736,1071739,1071745,1071750,1071752,1071781,1071784,1071795,1071809,1071961,1072083-1072084,1072242,1072288,1072290,1072299,1072302,1072339,1072343,1072353,1072355,1072360,1072367,1072371,1072406,1072412,1072417,1072419,1072423,1072425,1072429,1072431,1072447,1072501,1072519,1072527-1072528,1072534-1072538,1072544,1072623,1072625,1072629,1072692-1072693,1072695,1072927,1072940,1072953,1072997,1073043,1073093,1073102,1073242,1073247,1073281,1073306,1073325-1073326,1073328,1073332,1073340,1073357,1073366,1073377,1073413,1073418,1073689,1073692,1073749,1073797,1073817,1073821,1073824,1073827,1073831,1073854-1073855,1073862,1073869-1073870,1073905,1073955-1073956,1073965,1073974-1073975,1074032,1074037-1074039,1074068,1074072,1074134,1074167,1074334,1074460-1074461,1074474,1074485,1074488,1074492,1074526,1074553,1074572,1074591,1074598,1074664,1074939,1075240,1075313,1075328,1075802,1075844-1075845,1075869,1075886,107594
2,
> 1075946,1075963,1075973,1076006,1076018,1076023,1076089-1076090,1076093-1076096,1076098,1076100,1076161,1076172,1076230,1076234,1076313,1076344,1076403,1076556,1076616-1076617,1076631,1076639,1076645,1076658,1076712,1076715,1076726,1076730,1076732,1076734,1076741,1076752,1076759,1076826-1076827,1076839,1076846,1076848,1076854,1076872,1076903,1077861,1077897,1078008,1078018,1078035,1078037,1078050,1078073,1078110-1078111,1078115,1078147,1078151,1078179-1078180,1078185,1078187,1078256,1078262,1078266,1078269,1078330,1078357,1078366,1078497,1078502,1078506,1078527,1078544,1078768,1078828,1078839,1078884,1078914,1078918,1078934,1078949,1078954,1078960,1078962,1078975,1078990,1078996,1079008,1079017,1079033,1079070,1079089-1079090,1079297,1079310,1079348,1079400-1079401,1079409,1079443,1079450,1079458,1079464,1079508,1079512,1079517,1079531-1079532,1079538,1079544,1079550-1079551,1079554,1079563,1079588-1079589,1079591-1079592,1079594,1079686,1079706,1079754,1079756,1079758-1079759,1079803-1079804,1079828,10798
51
> ,1079855-1079856,1079858,1079875,1079897,1079914,1079967,1079983,1080034,1080119,1080172,1080175,1080185,1080192-1080193,1080198,1080234,1080236,1080238,1080245,1080248,1080251,1080253,1080263,1080265,1080268,1080272,1080285,1080294,1080333,...
Received on 2011-09-11 14:57:38 CEST

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