reverse-branch-cache: switch to doubling allocating scheme
In preperation for updating the reverse-branch-cache incrementally
whenever a new changeset comes in, avoid bad performance on resize with
Python 3.7 (and likely other 3.x versions).
Differential Revision: https://phab.mercurial-scm.org/D9778
--- a/mercurial/branchmap.py Sun Jan 17 23:21:33 2021 +0100
+++ b/mercurial/branchmap.py Fri Jan 15 01:20:47 2021 +0100
@@ -566,6 +566,7 @@
# [4 byte hash prefix][4 byte branch name number with sign bit indicating open]
_rbcrecfmt = b'>4sI'
_rbcrecsize = calcsize(_rbcrecfmt)
+_rbcmininc = 64 * _rbcrecsize
_rbcnodelen = 4
_rbcbranchidxmask = 0x7FFFFFFF
_rbccloseflag = 0x80000000
@@ -730,11 +731,15 @@
if rev == nullrev:
return
rbcrevidx = rev * _rbcrecsize
- if len(self._rbcrevs) < rbcrevidx + _rbcrecsize:
- self._rbcrevs.extend(
- b'\0'
- * (len(self._repo.changelog) * _rbcrecsize - len(self._rbcrevs))
- )
+ requiredsize = rbcrevidx + _rbcrecsize
+ rbccur = len(self._rbcrevs)
+ if rbccur < requiredsize:
+ # bytearray doesn't allocate extra space at least in Python 3.7.
+ # When multiple changesets are added in a row, precise resize would
+ # result in quadratic complexity. Overallocate to compensate by
+ # use the classic doubling technique for dynamic arrays instead.
+ # If there was a gap in the map before, less space will be reserved.
+ self._rbcrevs.extend(b'\0' * max(_rbcmininc, requiredsize))
pack_into(_rbcrecfmt, self._rbcrevs, rbcrevidx, node, branchidx)
self._rbcrevslen = min(self._rbcrevslen, rev)