[PATCH 2 of 2 fix-default-regression] bufferedinputpipe: remove N^2 computation of buffer length (issue4735)
Pierre-Yves David
pierre-yves.david at ens-lyon.org
Fri Jun 26 21:00:53 CDT 2015
On 06/26/2015 11:42 AM, Pierre-Yves David wrote:
> # HG changeset patch
> # User Pierre-Yves David <pierre-yves.david at fb.com>
> # Date 1435343390 25200
> # Fri Jun 26 11:29:50 2015 -0700
> # Node ID cff5b737b1debd3bc0e23a4e469c09e8f4d726d4
> # Parent 995f1afb89fac10d4759d6c3524693ecb926b9f4
> bufferedinputpipe: remove N^2 computation of buffer length (issue4735)
>
> The assumption that dynamically computing the length of the buffer was N^2, but
> negligible because fast was False. So we drop the dynamic computation and
> manually keep track of the buffer length.
>
> He: Enter commit message. Lines beginning with 'HG:' are removed.
>
> diff --git a/mercurial/util.py b/mercurial/util.py
> --- a/mercurial/util.py
> +++ b/mercurial/util.py
> @@ -252,10 +252,11 @@ class bufferedinputpipe(object):
>
> def __init__(self, input):
> self._input = input
> self._buffer = []
> self._eof = False
> + self._lenbuf = 0
>
> @property
> def hasbuffer(self):
> """True is any data is currently buffered
>
> @@ -281,10 +282,11 @@ class bufferedinputpipe(object):
> def readline(self, *args, **kwargs):
> if 1 < len(self._buffer):
> # this should not happen because both read and readline end with a
> # _frombuffer call that collapse it.
> self._buffer = [''.join(self._buffer)]
> + self._lenbuf = len(self._buffer[0])
> lfi = -1
> if self._buffer:
> lfi = self._buffer[-1].find('\n')
> while (not self._eof) and lfi < 0:
> self._fillbuffer()
> @@ -296,15 +298,10 @@ class bufferedinputpipe(object):
> elif 1 < len(self._buffer):
> # we need to take previous chunks into account
> size += self._lenbuf - len(self._buffer[-1])
> return self._frombuffer(size)
>
> - @property
> - def _lenbuf(self):
> - """return the current lengh of buffered data"""
> - return sum(len(d) for d in self._buffer)
> -
> def _frombuffer(self, size):
> """return at most 'size' data from the buffer
>
> The data are removed from the buffer."""
> if size == 0 or not self._buffer:
> @@ -315,20 +312,23 @@ class bufferedinputpipe(object):
>
> data = buf[:size]
> buf = buf[len(data):]
> if buf:
> self._buffer = [buf]
> + self._lenbuf = buf[0]
as spotted by Durham, this should be:
self._lenbuf = len(buf)
This did not explode too much, because "foo" < 4 is always true, so,
some conditional was misbehaving, sending the whole process back on track.
I'll send a V2.
--
Pierre-Yves David
More information about the Mercurial-devel
mailing list