[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 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,1075942,
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,1079851
,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:54:23 CEST

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