Mercurial > hg
changeset 46360:1726a53a8494
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
| author | Joerg Sonnenberger <joerg@bec.de> |
|---|---|
| date | Fri, 15 Jan 2021 01:20:47 +0100 |
| parents | 0600e8467101 |
| children | dfca84970da8 |
| files | mercurial/branchmap.py |
| diffstat | 1 files changed, 10 insertions(+), 5 deletions(-) [+] |
line wrap: on
line diff
--- 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)