Submitter | Paul Morelle |
---|---|

Date | Oct. 18, 2017, 2:36 p.m. |

Message ID | <495cbf44112b9872f280.1508337381@taranis.localdomain> |

Download | mbox | patch |

Permalink | /patch/25169/ |

State | Accepted |

Headers | show |

## Comments

## Patch

diff -r 537de0b14030 -r 495cbf44112b mercurial/revlog.py --- a/mercurial/revlog.py Wed Sep 20 19:38:06 2017 +0200 +++ b/mercurial/revlog.py Wed Oct 18 12:53:00 2017 +0200 @@ -17,6 +17,7 @@ import collections import errno import hashlib +import heapq import os import struct import zlib @@ -170,49 +171,59 @@ start = revlog.start length = revlog.length - chunkqueue = collections.deque() - chunkqueue.append((revs, 0)) + if len(revs) <= 1: + yield revs + return - while chunkqueue: - revs, depth = chunkqueue.popleft() + startbyte = start(revs[0]) + endbyte = start(revs[-1]) + length(revs[-1]) + readdata = deltachainspan = endbyte - startbyte + + chainpayload = sum(length(r) for r in revs) - startbyte = start(revs[0]) - endbyte = start(revs[-1]) + length(revs[-1]) - deltachainspan = endbyte - startbyte + if deltachainspan: + density = chainpayload / float(deltachainspan) + else: + density = 1.0 - if deltachainspan <= revlog._srminblocksize or len(revs) <= 1: - yield revs - continue + # Store the gaps in a heap to have them sorted by decreasing size + gapsheap = [] + heapq.heapify(gapsheap) + prevend = None + for i, rev in enumerate(revs): + revstart = start(rev) + revlen = length(rev) - # Find where is the largest hole (this is where we would split) and - # sum up the lengths of useful data to compute the density of the span - textlen = 0 - prevend = None - largesthole = 0 - idxlargesthole = -1 - for i, rev in enumerate(revs): - revstart = start(rev) - revlen = length(rev) + if prevend is not None: + gapsize = revstart - prevend + if gapsize: + heapq.heappush(gapsheap, (-gapsize, i)) + + prevend = revstart + revlen + + # Collect the indices of the largest holes until the density is acceptable + indicesheap = [] + heapq.heapify(indicesheap) + while gapsheap and density < revlog._srdensitythreshold: + oppgapsize, gapidx = heapq.heappop(gapsheap) + + heapq.heappush(indicesheap, gapidx) - if prevend is not None: - hole = revstart - prevend - if hole > largesthole: - largesthole = hole - idxlargesthole = i - - textlen += revlen - prevend = revstart + revlen + # the gap sizes are stored as negatives to be sorted decreasingly + # by the heap + readdata -= (-oppgapsize) + if readdata > 0: + density = chainpayload / float(readdata) + else: + density = 1.0 - density = textlen / float(deltachainspan) if deltachainspan > 0 else 1.0 - - if density > revlog._srdensitythreshold: - yield revs - continue - - # Add the left and right parts so that they will be sliced - # recursively too - chunkqueue.append((revs[:idxlargesthole], depth + 1)) - chunkqueue.append((revs[idxlargesthole:], depth + 1)) + # Cut the revs at collected indices + previdx = 0 + while indicesheap: + idx = heapq.heappop(indicesheap) + yield revs[previdx:idx] + previdx = idx + yield revs[previdx:] # index v0: # 4 bytes: offset