[PATCH 05 of 14] sparse-revlog: stop using a heap to track gaps

[Boris Feld]

# HG changeset patch
# User Boris Feld <boris.feld at octobus.net>
# Date 1541689290 -3600
#      Thu Nov 08 16:01:30 2018 +0100
# Node ID 8ebe5520cc4ae87f6fccba20897d292489a651db
# Parent  3bdd984df153304a956d31d2f3fbc3cd7f0e41c2
# EXP-Topic sparse-perf
# Available At https://bitbucket.org/octobus/mercurial-devel/
#              hg pull https://bitbucket.org/octobus/mercurial-devel/ -r 8ebe5520cc4a
sparse-revlog: stop using a heap to track gaps

The heap doesn't bring any performance advantage as we can simply sort the
final list.

Moreover, the lesser complexity helps a lot when we later implement it in C.

diff --git a/mercurial/revlogutils/deltas.py b/mercurial/revlogutils/deltas.py
--- a/mercurial/revlogutils/deltas.py
+++ b/mercurial/revlogutils/deltas.py
@@ -275,8 +275,7 @@ def _slicechunktodensity(revlog, revs, t
         return
 
     # Store the gaps in a heap to have them sorted by decreasing size
-    gapsheap = []
-    heapq.heapify(gapsheap)
+    gaps = []
     prevend = None
     for i, rev in enumerate(revs):
         revstart = start(rev)
@@ -290,21 +289,23 @@ def _slicechunktodensity(revlog, revs, t
             gapsize = revstart - prevend
             # only consider holes that are large enough
             if gapsize > mingapsize:
-                heapq.heappush(gapsheap, (-gapsize, i))
+                gaps.append((gapsize, i))
 
         prevend = revstart + revlen
+    # sort the gaps to pop them from largest to small
+    gaps.sort()
 
     # Collect the indices of the largest holes until the density is acceptable
     indicesheap = []
     heapq.heapify(indicesheap)
-    while gapsheap and density < targetdensity:
-        oppgapsize, gapidx = heapq.heappop(gapsheap)
+    while gaps and density < targetdensity:
+        gapsize, gapidx = gaps.pop()
 
         heapq.heappush(indicesheap, gapidx)
 
         # the gap sizes are stored as negatives to be sorted decreasingly
         # by the heap
-        readdata -= (-oppgapsize)
+        readdata -= gapsize
         if readdata > 0:
             density = chainpayload / float(readdata)
         else: