Merge lp:~mbp/bzr/bigstring into lp:bzr

[Martin Pool]

This adds a BigString class that is basically like a list of byte strings that is not bounded by memory.

It is in of bug 890085, memory usage, but it does not yet clearly help with memory usage, so I'm not sure I actually want to merge it. I'm going to propose it here though because it's pretty self-contained.

[Martin Packman (gz)]

One thing I'm not crazy about here is in almost all cases we're just going to be writing the data to disk anyway, and we carefully use a compressor that supports incremental encoding, but then need all the output in one list anyway. All to support a needlessly abstract API that wants to deal in streams but provide a length header. So, we hurt the common case by writing to disk twice with this change to avoid fixing the higher levels.

review: Abstain

[Martin Pool (mbp)]

On 2 December 2011 22:17, Martin Packman <email address hidden> wrote:
> Review: Abstain
>
> One thing I'm not crazy about here is in almost all cases we're just going to be writing the data to disk anyway, and we carefully use a compressor that supports incremental encoding, but then need all the output in one list anyway. All to support a needlessly abstract API that wants to deal in streams but provide a length header. So, we hurt the common case by writing to disk twice with this change to avoid fixing the higher levels.

Yes, obviously there is some friction in the APIs, and this is not a
magic bullet for fixing that.

Beyond the API, we do have a length-prefixed format, unless we either
can think of some clever way to write multiple chunks in a compatible
way, or we decide to handle large files by a different format flag, or
there is some other way around it (is there?). To write that format
we need to know the length of the compressed data before we write the
header, therefore we need to buffer up all the compressed data. At the
moment we buffer it in memory; we could instead buffer it to disk at
least for large blocks. When there is physical memory free writing to
a temporary file and then erasing it shouldn't be much slower than
just holding it in memory; when physical memory is low it will
probably cope much better.

--
Martin

[Martin Pool (mbp)]

...I'm not going to merge this unless it clearly does help; I've just
put it up here because it is fairly self contained.

[Martin Packman (gz)]

Yes, having the length prefix in the format does complicate things. The best idea I could come up with was to always write the pack to disk first, even when streaming to a remote location. Then it would be possible to leave log10(uncompressed_len + overhead) bytes at the start, then when finalizing the compressobj seek back and write in the compressed length with leading zeros. That may still be a format change.

[Martin Pool (mbp)]

On 8 December 2011 01:46, Martin Packman <email address hidden> wrote:
> Yes, having the length prefix in the format does complicate things. The best idea I could come up with was to always write the pack to disk first, even when streaming to a remote location. Then it would be possible to leave log10(uncompressed_len + overhead) bytes at the start, then when finalizing the compressobj seek back and write in the compressed length with leading zeros. That may still be a format change.

seeking won't work well on a network stream :)

--
Martin

[Martin Packman (gz)]

> On 8 December 2011 01:46, Martin Packman <email address hidden> wrote:
> > Yes, having the length prefix in the format does complicate things. The best
> idea I could come up with was to always write the pack to disk first, even
> when streaming to a remote location. Then it would be possible to leave
> log10(uncompressed_len + overhead) bytes at the start, then when finalizing
> the compressobj seek back and write in the compressed length with leading
> zeros. That may still be a format change.
>
> seeking won't work well on a network stream :)

Hence the need to always write to disk first. It means delaying sending any data till the whole compressed block is completed, but that's already the case now as the whole lot is compressed in memory in order to get the size for the header.

[Vincent Ladeuil (vila)]

An alternative to backpatching is to send chunks with a marker indicating that there are more to come.
The receiving side can then buffer them (memory or disk) until the last chunk is received.

[Martin Packman (gz)]

Without follow up work I don't think it's useful to land this, the code can be refereed to later even if it's not merged.

review: Disapprove

[Martin Pool (mbp)]

I agree (regretfully).

Unmerged revisions

6262. By Martin Pool on 2011-11-29

Remove stray pdb call

6261. By Martin Pool on 2011-11-14

Show the bigstring temp file name

6260. By Martin Pool on 2011-11-14

Use BigString from groupcompress and add some debug help

6259. By Martin Pool on 2011-11-14

Add basic BigString implementation

=== added file 'bzrlib/bigstring.py'
--- bzrlib/bigstring.py	1970-01-01 00:00:00 +0000
+++ bzrlib/bigstring.py	2011-11-29 07:33:40 +0000
@@ -0,0 +1,90 @@
+# Copyright (C) 2011 Canonical Ltd
+#
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 2 of the License, or
+# (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software
+# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+
+
+"""Large bytestring-like object that spills to disk."""
+
+
+import tempfile
+
+
+class BigString(object):
+    """Large bytestring-like object that spills to disk.
+
+    BigStrings can have content appended to them, can report their length,
+    and can be read back as a series of chunks.
+    
+    The API is such as to encourage client code to be written in a way
+    that will never hold the whole string in memory.
+    
+    Typical usage:
+    
+    >>> bs = BigString()
+    >>> bs.append_chunks(' %d' % i for i in range(4))
+    >>> len(bs)
+    8
+    >>> ''.join(bs.get_chunks())
+    ' 0 1 2 3'
+
+    The last of these, joining all the chunks up in to one big in-memory
+    string, defeats the purpose of the whole thing.  Don't do that.  Write them
+    to a file one at a time.
+    """
+    
+    # TODO: Keep it in memory when it's small, and just create a file if it
+    # actually gets big.
+
+    def __init__(self):
+        # TODO: Maybe pass a 0 bufsiz, if we're sure we'll always just do large
+        # writes...
+        # 
+        # TODO: Maybe fadvise when possible.
+        self._file = tempfile.NamedTemporaryFile(
+            mode='ab+',
+            prefix='bzrbigstr-')
+        self._length = 0
+        self._read_chunk_size = 16384
+            
+    def __repr__(self):
+        return "%s(%r)" % (
+            self.__class__.__name__,
+            self._file.name)
+            
+    def append_chunks(self, chunks):
+        for b in chunks:
+            if not isinstance(b, str):
+                raise TypeError(type(b))
+            # File is in append mode, so even if we've seeked back this is safe.
+            self._file.write(b)
+            self._length += len(b)
+
+    def __len__(self):
+        return self._length
+
+    def get_chunks(self):
+        self._file.flush()  # To the OS, not necessarily to disk.
+        self._file.seek(0)
+        yielded_bytes = 0
+        while True:
+            c = self._file.read(self._read_chunk_size)
+            if not c:
+                break
+            yield c
+            yielded_bytes += len(c)
+        if yielded_bytes != self._length:
+            raise AssertionError(
+                "%r expected to get back %d bytes, actually returned %d" %
+                (self, self._length, yielded_bytes))
 
=== modified file 'bzrlib/groupcompress.py'
--- bzrlib/groupcompress.py	2011-11-18 05:13:19 +0000
+++ bzrlib/groupcompress.py	2011-11-29 07:33:40 +0000
@@ -17,12 +17,14 @@
 """Core compression logic for compressing streams of related files."""
 
 import time
+import warnings
 import zlib
 
 from bzrlib.lazy_import import lazy_import
 lazy_import(globals(), """
 from bzrlib import (
     annotate,
+    bigstring,
     config,
     debug,
     errors,
@@ -298,11 +300,17 @@
         compressor = zlib.compressobj(zlib.Z_DEFAULT_COMPRESSION)
         # Peak in this point is 1 fulltext, 1 compressed text, + zlib overhead
         # (measured peak is maybe 30MB over the above...)
-        compressed_chunks = map(compressor.compress, chunks)
-        compressed_chunks.append(compressor.flush())
+        if 'groupcompress' in debug.debug_flags:
+            trace.mutter(
+                '_create_z_content_from_chunks: %d chunks total %d bytes' % (
+                len(chunks), sum(map(len, chunks))))
+        bigs = bigstring.BigString()
+        bigs.append_chunks(compressor.compress(c) for c in chunks)
+        bigs.append_chunks([compressor.flush()])
+        compressor = None  # Can't delete because of Python quirk?
         # Ignore empty chunks
-        self._z_content_chunks = [c for c in compressed_chunks if c]
-        self._z_content_length = sum(map(len, self._z_content_chunks))
+        self._z_content_chunks = list(bigs.get_chunks())
+        self._z_content_length = len(bigs)
 
     def _create_z_content(self):
         if self._z_content_chunks is not None:
@@ -826,6 +834,12 @@
             if nostore_sha == _null_sha1:
                 raise errors.ExistingContent()
             return _null_sha1, 0, 0, 'fulltext'
+        if 'groupcompress' in debug.debug_flags:
+            trace.mutter("compress %d bytes" % len(bytes))
+            if len(bytes) > 10<<20:
+                warnings.warn("groupcompress given over-large %d byte block"
+                    % len(bytes))
+            import pdb;pdb.set_trace()
         # we assume someone knew what they were doing when they passed it in
         if expected_sha is not None:
             sha1 = expected_sha
 
=== modified file 'bzrlib/help_topics/en/debug-flags.txt'
--- bzrlib/help_topics/en/debug-flags.txt	2011-10-10 13:51:29 +0000
+++ bzrlib/help_topics/en/debug-flags.txt	2011-11-29 07:33:40 +0000
@@ -15,6 +15,7 @@
 -Dfilters         Emit information for debugging content filtering.
 -Dforceinvdeltas  Force use of inventory deltas during generic streaming fetch.
 -Dgraph           Trace graph traversal.
+-Dgroupcompress   Groupcompress internals.
 -Dhashcache       Log every time a working file is read to determine its hash.
 -Dhooks           Trace hook execution.
 -Dhpss            Trace smart protocol requests and responses.
 
=== modified file 'bzrlib/tests/__init__.py'
--- bzrlib/tests/__init__.py	2011-11-29 06:50:54 +0000
+++ bzrlib/tests/__init__.py	2011-11-29 07:33:40 +0000
@@ -3928,6 +3928,7 @@
         'bzrlib.tests.test_api',
         'bzrlib.tests.test_atomicfile',
         'bzrlib.tests.test_bad_files',
+        'bzrlib.tests.test_bigstring',
         'bzrlib.tests.test_bisect_multi',
         'bzrlib.tests.test_branch',
         'bzrlib.tests.test_branchbuilder',
@@ -4104,6 +4105,7 @@
         return []
     return [
         'bzrlib',
+        'bzrlib.bigstring',
         'bzrlib.branchbuilder',
         'bzrlib.decorators',
         'bzrlib.inventory',
 
=== added file 'bzrlib/tests/test_bigstring.py'
--- bzrlib/tests/test_bigstring.py	1970-01-01 00:00:00 +0000
+++ bzrlib/tests/test_bigstring.py	2011-11-29 07:33:40 +0000
@@ -0,0 +1,51 @@
+# Copyright (C) 2011 Canonical Ltd
+#
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 2 of the License, or
+# (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software
+# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+
+"""Tests for BigString"""
+
+from testtools.matchers import (
+    Matcher,
+    StartsWith,
+    )
+
+from bzrlib.bigstring import BigString
+from bzrlib.tests import TestCase
+
+
+class TestBigString(TestCase):
+
+    def test_repr(self):
+        bs = BigString()
+        self.assertThat(repr(bs),
+            StartsWith('BigString('))
+            
+    def test_simple_get_chunks(self):
+        bs = BigString()
+        bs.append_chunks(['hello', 'world'])
+        self.assertEqual(''.join(bs.get_chunks()),
+            'helloworld')
+        self.assertEqual(len(bs), 10)
+
+    def test_get_chunks_limited_size(self):
+        bs = BigString()
+        bs.append_chunks(['hello', 'world', '!'])
+        bs._read_chunk_size = 3
+        self.assertEqual(
+            list(bs.get_chunks()),
+            ['hel', 'low', 'orl', 'd!'])
+        self.assertEqual(
+            len(bs),
+            11)