331 >>> list(_slicechunk(revlog, [0, 11, 13, 15])) |
331 >>> list(_slicechunk(revlog, [0, 11, 13, 15])) |
332 [[0], [11, 13, 15]] |
332 [[0], [11, 13, 15]] |
333 >>> list(_slicechunk(revlog, [1, 2, 3, 5, 8, 10, 11, 14])) |
333 >>> list(_slicechunk(revlog, [1, 2, 3, 5, 8, 10, 11, 14])) |
334 [[1, 2], [5, 8, 10, 11], [14]] |
334 [[1, 2], [5, 8, 10, 11], [14]] |
335 """ |
335 """ |
|
336 for chunk in _slicechunktodensity(revlog, revs, |
|
337 revlog._srdensitythreshold, |
|
338 revlog._srmingapsize): |
|
339 yield chunk |
|
340 |
|
341 def _slicechunktodensity(revlog, revs, targetdensity=0.5, mingapsize=0): |
|
342 """slice revs to reduce the amount of unrelated data to be read from disk. |
|
343 |
|
344 ``revs`` is sliced into groups that should be read in one time. |
|
345 Assume that revs are sorted. |
|
346 |
|
347 The initial chunk is sliced until the overall density (payload/chunks-span |
|
348 ratio) is above `targetdensity`. No gap smaller than `mingapsize` is |
|
349 skipped. |
|
350 |
|
351 >>> revlog = _testrevlog([ |
|
352 ... 5, #00 (5) |
|
353 ... 10, #01 (5) |
|
354 ... 12, #02 (2) |
|
355 ... 12, #03 (empty) |
|
356 ... 27, #04 (15) |
|
357 ... 31, #05 (4) |
|
358 ... 31, #06 (empty) |
|
359 ... 42, #07 (11) |
|
360 ... 47, #08 (5) |
|
361 ... 47, #09 (empty) |
|
362 ... 48, #10 (1) |
|
363 ... 51, #11 (3) |
|
364 ... 74, #12 (23) |
|
365 ... 85, #13 (11) |
|
366 ... 86, #14 (1) |
|
367 ... 91, #15 (5) |
|
368 ... ]) |
|
369 |
|
370 >>> list(_slicechunktodensity(revlog, range(16))) |
|
371 [[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]] |
|
372 >>> list(_slicechunktodensity(revlog, [0, 15])) |
|
373 [[0], [15]] |
|
374 >>> list(_slicechunktodensity(revlog, [0, 11, 15])) |
|
375 [[0], [11], [15]] |
|
376 >>> list(_slicechunktodensity(revlog, [0, 11, 13, 15])) |
|
377 [[0], [11, 13, 15]] |
|
378 >>> list(_slicechunktodensity(revlog, [1, 2, 3, 5, 8, 10, 11, 14])) |
|
379 [[1, 2], [5, 8, 10, 11], [14]] |
|
380 >>> list(_slicechunktodensity(revlog, [1, 2, 3, 5, 8, 10, 11, 14], |
|
381 ... mingapsize=20)) |
|
382 [[1, 2, 3, 5, 8, 10, 11], [14]] |
|
383 >>> list(_slicechunktodensity(revlog, [1, 2, 3, 5, 8, 10, 11, 14], |
|
384 ... targetdensity=0.95)) |
|
385 [[1, 2], [5], [8, 10, 11], [14]] |
|
386 >>> list(_slicechunktodensity(revlog, [1, 2, 3, 5, 8, 10, 11, 14], |
|
387 ... targetdensity=0.95, mingapsize=12)) |
|
388 [[1, 2], [5, 8, 10, 11], [14]] |
|
389 """ |
336 start = revlog.start |
390 start = revlog.start |
337 length = revlog.length |
391 length = revlog.length |
338 |
392 |
339 if len(revs) <= 1: |
393 if len(revs) <= 1: |
340 yield revs |
394 yield revs |
341 return |
395 return |
342 |
396 |
343 readdata = deltachainspan = _segmentspan(revlog, revs) |
397 readdata = deltachainspan = _segmentspan(revlog, revs) |
344 |
398 |
345 if deltachainspan < revlog._srmingapsize: |
399 if deltachainspan < mingapsize: |
346 yield revs |
400 yield revs |
347 return |
401 return |
348 |
402 |
349 chainpayload = sum(length(r) for r in revs) |
403 chainpayload = sum(length(r) for r in revs) |
350 |
404 |
351 if deltachainspan: |
405 if deltachainspan: |
352 density = chainpayload / float(deltachainspan) |
406 density = chainpayload / float(deltachainspan) |
353 else: |
407 else: |
354 density = 1.0 |
408 density = 1.0 |
355 |
409 |
356 if density >= revlog._srdensitythreshold: |
410 if density >= targetdensity: |
357 yield revs |
411 yield revs |
358 return |
412 return |
359 |
413 |
360 # Store the gaps in a heap to have them sorted by decreasing size |
414 # Store the gaps in a heap to have them sorted by decreasing size |
361 gapsheap = [] |
415 gapsheap = [] |
370 continue |
424 continue |
371 |
425 |
372 if prevend is not None: |
426 if prevend is not None: |
373 gapsize = revstart - prevend |
427 gapsize = revstart - prevend |
374 # only consider holes that are large enough |
428 # only consider holes that are large enough |
375 if gapsize > revlog._srmingapsize: |
429 if gapsize > mingapsize: |
376 heapq.heappush(gapsheap, (-gapsize, i)) |
430 heapq.heappush(gapsheap, (-gapsize, i)) |
377 |
431 |
378 prevend = revstart + revlen |
432 prevend = revstart + revlen |
379 |
433 |
380 # Collect the indices of the largest holes until the density is acceptable |
434 # Collect the indices of the largest holes until the density is acceptable |
381 indicesheap = [] |
435 indicesheap = [] |
382 heapq.heapify(indicesheap) |
436 heapq.heapify(indicesheap) |
383 while gapsheap and density < revlog._srdensitythreshold: |
437 while gapsheap and density < targetdensity: |
384 oppgapsize, gapidx = heapq.heappop(gapsheap) |
438 oppgapsize, gapidx = heapq.heappop(gapsheap) |
385 |
439 |
386 heapq.heappush(indicesheap, gapidx) |
440 heapq.heappush(indicesheap, gapidx) |
387 |
441 |
388 # the gap sizes are stored as negatives to be sorted decreasingly |
442 # the gap sizes are stored as negatives to be sorted decreasingly |