← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tuned_gzip.py

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2008-09-03 22:30:56 UTC
  • mfrom: (3644.2.13 index_builder_cleanup)
  • Revision ID: pqm@pqm.ubuntu.com-20080903223056-b108iytb38xkznci
(jam) Streamline BTreeBuilder.add_node et al to make btree creation
        faster.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tuned_gzip.py
1
 
# Copyright (C) 2006-2011 Canonical Ltd
 
1
# Copyright (C) 2005, 2006 Canonical Ltd
2
2
# Written by Robert Collins <robert.collins@canonical.com>
3
3
#
4
4
# This program is free software; you can redistribute it and/or modify
13
13
#
14
14
# You should have received a copy of the GNU General Public License
15
15
# along with this program; if not, write to the Free Software
16
 
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 
16
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
17
17
 
18
18
"""Bzrlib specific gzip tunings. We plan to feed these to the upstream gzip."""
19
19
 
20
 
from __future__ import absolute_import
21
 
 
22
20
from cStringIO import StringIO
23
21
 
24
22
# make GzipFile faster:
25
23
import gzip
26
 
from gzip import FEXTRA, FCOMMENT, FNAME, FHCRC
 
24
from gzip import U32, LOWU32, FEXTRA, FCOMMENT, FNAME, FHCRC
27
25
import sys
28
26
import struct
29
27
import zlib
30
28
 
31
29
# we want a \n preserved, break on \n only splitlines.
32
 
from bzrlib import symbol_versioning
 
30
import bzrlib
33
31
 
34
32
__all__ = ["GzipFile", "bytes_to_gzip"]
35
33
 
36
34
 
37
 
def U32(i):
38
 
    """Return i as an unsigned integer, assuming it fits in 32 bits.
39
 
 
40
 
    If it's >= 2GB when viewed as a 32-bit unsigned int, return a long.
41
 
    """
42
 
    if i < 0:
43
 
        i += 1L << 32
44
 
    return i
45
 
 
46
 
 
47
 
def LOWU32(i):
48
 
    """Return the low-order 32 bits of an int, as a non-negative int."""
49
 
    return i & 0xFFFFFFFFL
50
 
 
51
 
 
52
35
def bytes_to_gzip(bytes, factory=zlib.compressobj,
53
36
    level=zlib.Z_DEFAULT_COMPRESSION, method=zlib.DEFLATED,
54
37
    width=-zlib.MAX_WBITS, mem=zlib.DEF_MEM_LEVEL,
55
38
    crc32=zlib.crc32):
56
39
    """Create a gzip file containing bytes and return its content."""
57
 
    return chunks_to_gzip([bytes])
58
 
 
59
 
 
60
 
def chunks_to_gzip(chunks, factory=zlib.compressobj,
61
 
    level=zlib.Z_DEFAULT_COMPRESSION, method=zlib.DEFLATED,
62
 
    width=-zlib.MAX_WBITS, mem=zlib.DEF_MEM_LEVEL,
63
 
    crc32=zlib.crc32):
64
 
    """Create a gzip file containing chunks and return its content.
65
 
 
66
 
    :param chunks: An iterable of strings. Each string can have arbitrary
67
 
        layout.
68
 
    """
69
40
    result = [
70
41
        '\037\213'  # self.fileobj.write('\037\213')  # magic header
71
42
        '\010'      # self.fileobj.write('\010')      # compression method
83
54
    # using a compressobj avoids a small header and trailer that the compress()
84
55
    # utility function adds.
85
56
    compress = factory(level, method, width, mem, 0)
86
 
    crc = 0
87
 
    total_len = 0
88
 
    for chunk in chunks:
89
 
        crc = crc32(chunk, crc)
90
 
        total_len += len(chunk)
91
 
        zbytes = compress.compress(chunk)
92
 
        if zbytes:
93
 
            result.append(zbytes)
 
57
    result.append(compress.compress(bytes))
94
58
    result.append(compress.flush())
 
59
    result.append(struct.pack("<L", LOWU32(crc32(bytes))))
95
60
    # size may exceed 2GB, or even 4GB
96
 
    result.append(struct.pack("<LL", LOWU32(crc), LOWU32(total_len)))
 
61
    result.append(struct.pack("<L", LOWU32(len(bytes))))
97
62
    return ''.join(result)
98
63
 
99
64
 
120
85
    Yes, its only 1.6 seconds, but they add up.
121
86
    """
122
87
 
123
 
    def __init__(self, *args, **kwargs):
124
 
        symbol_versioning.warn(
125
 
            symbol_versioning.deprecated_in((2, 3, 0))
126
 
            % 'bzrlib.tuned_gzip.GzipFile',
127
 
            DeprecationWarning, stacklevel=2)
128
 
        gzip.GzipFile.__init__(self, *args, **kwargs)
129
 
 
130
 
    if sys.version_info >= (2, 7, 4):
131
 
        def _add_read_data(self, data):
132
 
            # 4169 calls in 183
133
 
            # temp var for len(data) and switch to +='s.
134
 
            # 4169 in 139
135
 
            len_data = len(data)
136
 
            self.crc = zlib.crc32(data, self.crc) & 0xffffffffL
137
 
            offset = self.offset - self.extrastart
138
 
            self.extrabuf = self.extrabuf[offset:] + data
139
 
            self.extrasize = self.extrasize + len_data
140
 
            self.extrastart = self.offset
141
 
            self.size = self.size + len_data
142
 
    else:
143
 
        def _add_read_data(self, data):
144
 
            # 4169 calls in 183
145
 
            # temp var for len(data) and switch to +='s.
146
 
            # 4169 in 139
147
 
            len_data = len(data)
148
 
            self.crc = zlib.crc32(data, self.crc)
149
 
            self.extrabuf += data
150
 
            self.extrasize += len_data
151
 
            self.size += len_data
 
88
    def _add_read_data(self, data):
 
89
        # 4169 calls in 183
 
90
        # temp var for len(data) and switch to +='s.
 
91
        # 4169 in 139
 
92
        len_data = len(data)
 
93
        self.crc = zlib.crc32(data, self.crc)
 
94
        self.extrabuf += data
 
95
        self.extrasize += len_data
 
96
        self.size += len_data
152
97
 
153
98
    def _write_gzip_header(self):
154
99
        """A tuned version of gzip._write_gzip_header
155
100
 
156
101
        We have some extra constrains that plain Gzip does not.
157
 
        1) We want to write the whole blob at once. rather than multiple
 
102
        1) We want to write the whole blob at once. rather than multiple 
158
103
           calls to fileobj.write().
159
104
        2) We never have a filename
160
105
        3) We don't care about the time
174
119
            ''          #     self.fileobj.write(fname + '\000')
175
120
            )
176
121
 
177
 
    if sys.version_info < (2, 7, 4):
178
 
        def _read(self, size=1024):
179
 
            # various optimisations:
180
 
            # reduces lsprof count from 2500 to
181
 
            # 8337 calls in 1272, 365 internal
182
 
            if self.fileobj is None:
 
122
    def _read(self, size=1024):
 
123
        # various optimisations:
 
124
        # reduces lsprof count from 2500 to 
 
125
        # 8337 calls in 1272, 365 internal
 
126
        if self.fileobj is None:
 
127
            raise EOFError, "Reached EOF"
 
128
 
 
129
        if self._new_member:
 
130
            # If the _new_member flag is set, we have to
 
131
            # jump to the next member, if there is one.
 
132
            #
 
133
            # First, check if we're at the end of the file;
 
134
            # if so, it's time to stop; no more members to read.
 
135
            next_header_bytes = self.fileobj.read(10)
 
136
            if next_header_bytes == '':
183
137
                raise EOFError, "Reached EOF"
184
138
 
185
 
            if self._new_member:
186
 
                # If the _new_member flag is set, we have to
187
 
                # jump to the next member, if there is one.
188
 
                #
189
 
                # First, check if we're at the end of the file;
190
 
                # if so, it's time to stop; no more members to read.
191
 
                next_header_bytes = self.fileobj.read(10)
192
 
                if next_header_bytes == '':
193
 
                    raise EOFError, "Reached EOF"
194
 
 
195
 
                self._init_read()
196
 
                self._read_gzip_header(next_header_bytes)
197
 
                self.decompress = zlib.decompressobj(-zlib.MAX_WBITS)
198
 
                self._new_member = False
199
 
 
200
 
            # Read a chunk of data from the file
201
 
            buf = self.fileobj.read(size)
202
 
 
203
 
            # If the EOF has been reached, flush the decompression object
204
 
            # and mark this object as finished.
205
 
 
206
 
            if buf == "":
207
 
                self._add_read_data(self.decompress.flush())
208
 
                if len(self.decompress.unused_data) < 8:
209
 
                    raise AssertionError("what does flush do?")
 
139
            self._init_read()
 
140
            self._read_gzip_header(next_header_bytes)
 
141
            self.decompress = zlib.decompressobj(-zlib.MAX_WBITS)
 
142
            self._new_member = False
 
143
 
 
144
        # Read a chunk of data from the file
 
145
        buf = self.fileobj.read(size)
 
146
 
 
147
        # If the EOF has been reached, flush the decompression object
 
148
        # and mark this object as finished.
 
149
 
 
150
        if buf == "":
 
151
            self._add_read_data(self.decompress.flush())
 
152
            if len(self.decompress.unused_data) < 8:
 
153
                raise AssertionError("what does flush do?")
 
154
            self._gzip_tail = self.decompress.unused_data[0:8]
 
155
            self._read_eof()
 
156
            # tell the driving read() call we have stuffed all the data
 
157
            # in self.extrabuf
 
158
            raise EOFError, 'Reached EOF'
 
159
 
 
160
        self._add_read_data(self.decompress.decompress(buf))
 
161
 
 
162
        if self.decompress.unused_data != "":
 
163
            # Ending case: we've come to the end of a member in the file,
 
164
            # so seek back to the start of the data for the next member which
 
165
            # is the length of the decompress objects unused data - the first
 
166
            # 8 bytes for the end crc and size records.
 
167
            #
 
168
            # so seek back to the start of the unused data, finish up
 
169
            # this member, and read a new gzip header.
 
170
            # (The number of bytes to seek back is the length of the unused
 
171
            # data, minus 8 because those 8 bytes are part of this member.
 
172
            seek_length = len (self.decompress.unused_data) - 8
 
173
            if seek_length > 0:
 
174
                # we read too much data
 
175
                self.fileobj.seek(-seek_length, 1)
210
176
                self._gzip_tail = self.decompress.unused_data[0:8]
211
 
                self._read_eof()
212
 
                # tell the driving read() call we have stuffed all the data
213
 
                # in self.extrabuf
214
 
                raise EOFError, 'Reached EOF'
215
 
 
216
 
            self._add_read_data(self.decompress.decompress(buf))
217
 
 
218
 
            if self.decompress.unused_data != "":
219
 
                # Ending case: we've come to the end of a member in the file,
220
 
                # so seek back to the start of the data for the next member
221
 
                # which is the length of the decompress objects unused data -
222
 
                # the first 8 bytes for the end crc and size records.
223
 
                #
224
 
                # so seek back to the start of the unused data, finish up
225
 
                # this member, and read a new gzip header.
226
 
                # (The number of bytes to seek back is the length of the unused
227
 
                # data, minus 8 because those 8 bytes are part of this member.
228
 
                seek_length = len (self.decompress.unused_data) - 8
229
 
                if seek_length > 0:
230
 
                    # we read too much data
231
 
                    self.fileobj.seek(-seek_length, 1)
232
 
                    self._gzip_tail = self.decompress.unused_data[0:8]
233
 
                elif seek_length < 0:
234
 
                    # we haven't read enough to check the checksum.
235
 
                    if not (-8 < seek_length):
236
 
                        raise AssertionError("too great a seek")
237
 
                    buf = self.fileobj.read(-seek_length)
238
 
                    self._gzip_tail = self.decompress.unused_data + buf
239
 
                else:
240
 
                    self._gzip_tail = self.decompress.unused_data
241
 
 
242
 
                # Check the CRC and file size, and set the flag so we read
243
 
                # a new member on the next call
244
 
                self._read_eof()
245
 
                self._new_member = True
246
 
 
247
 
        def _read_eof(self):
248
 
            """tuned to reduce function calls and eliminate file seeking:
249
 
            pass 1:
250
 
            reduces lsprof count from 800 to 288
251
 
            4168 in 296
252
 
            avoid U32 call by using struct format L
253
 
            4168 in 200
254
 
            """
255
 
            # We've read to the end of the file, so we should have 8 bytes of
256
 
            # unused data in the decompressor. If we don't, there is a corrupt
257
 
            # file.  We use these 8 bytes to calculate the CRC and the recorded
258
 
            # file size.  We then check the that the computed CRC and size of
259
 
            # the uncompressed data matches the stored values.  Note that the
260
 
            # size stored is the true file size mod 2**32.
261
 
            if not (len(self._gzip_tail) == 8):
262
 
                raise AssertionError("gzip trailer is incorrect length.")
263
 
            crc32, isize = struct.unpack("<LL", self._gzip_tail)
264
 
            # note that isize is unsigned - it can exceed 2GB
265
 
            if crc32 != U32(self.crc):
266
 
                raise IOError, "CRC check failed %d %d" % (crc32, U32(self.crc))
267
 
            elif isize != LOWU32(self.size):
268
 
                raise IOError, "Incorrect length of data produced"
 
177
            elif seek_length < 0:
 
178
                # we haven't read enough to check the checksum.
 
179
                if not (-8 < seek_length):
 
180
                    raise AssertionError("too great a seek")
 
181
                buf = self.fileobj.read(-seek_length)
 
182
                self._gzip_tail = self.decompress.unused_data + buf
 
183
            else:
 
184
                self._gzip_tail = self.decompress.unused_data
 
185
 
 
186
            # Check the CRC and file size, and set the flag so we read
 
187
            # a new member on the next call
 
188
            self._read_eof()
 
189
            self._new_member = True
 
190
 
 
191
    def _read_eof(self):
 
192
        """tuned to reduce function calls and eliminate file seeking:
 
193
        pass 1:
 
194
        reduces lsprof count from 800 to 288
 
195
        4168 in 296 
 
196
        avoid U32 call by using struct format L
 
197
        4168 in 200
 
198
        """
 
199
        # We've read to the end of the file, so we should have 8 bytes of 
 
200
        # unused data in the decompressor. If we don't, there is a corrupt file.
 
201
        # We use these 8 bytes to calculate the CRC and the recorded file size.
 
202
        # We then check the that the computed CRC and size of the
 
203
        # uncompressed data matches the stored values.  Note that the size
 
204
        # stored is the true file size mod 2**32.
 
205
        if not (len(self._gzip_tail) == 8):
 
206
            raise AssertionError("gzip trailer is incorrect length.")
 
207
        crc32, isize = struct.unpack("<LL", self._gzip_tail)
 
208
        # note that isize is unsigned - it can exceed 2GB
 
209
        if crc32 != U32(self.crc):
 
210
            raise IOError, "CRC check failed %d %d" % (crc32, U32(self.crc))
 
211
        elif isize != LOWU32(self.size):
 
212
            raise IOError, "Incorrect length of data produced"
269
213
 
270
214
    def _read_gzip_header(self, bytes=None):
271
215
        """Supply bytes if the minimum header size is already read.
272
 
 
 
216
        
273
217
        :param bytes: 10 bytes of header data.
274
218
        """
275
219
        """starting cost: 300 in 3998
312
256
 
313
257
    def readline(self, size=-1):
314
258
        """Tuned to remove buffer length calls in _unread and...
315
 
 
 
259
        
316
260
        also removes multiple len(c) calls, inlines _unread,
317
261
        total savings - lsprof 5800 to 5300
318
262
        phase 2:
322
266
        leading to a drop to:
323
267
        4168 calls in 1977
324
268
        4168 call to read() in 1646
325
 
        - i.e. just reduced the function call overhead. May be worth
 
269
        - i.e. just reduced the function call overhead. May be worth 
326
270
          keeping.
327
271
        """
328
272
        if size < 0: size = sys.maxint
370
314
        # to :
371
315
        # 4168 calls in 417.
372
316
        # Negative numbers result in reading all the lines
373
 
 
 
317
        
374
318
        # python's gzip routine uses sizehint. This is a more efficient way
375
319
        # than python uses to honor it. But it is even more efficient to
376
320
        # just read the entire thing and use cStringIO to split into lines.
383
327
 
384
328
    def _unread(self, buf, len_buf=None):
385
329
        """tuned to remove unneeded len calls.
386
 
 
 
330
        
387
331
        because this is such an inner routine in readline, and readline is
388
332
        in many inner loops, this has been inlined into readline().
389
333
 
390
334
        The len_buf parameter combined with the reduction in len calls dropped
391
 
        the lsprof ms count for this routine on my test data from 800 to 200 -
 
335
        the lsprof ms count for this routine on my test data from 800 to 200 - 
392
336
        a 75% saving.
393
337
        """
394
338
        if len_buf is None:
412
356
            self.offset += data_len
413
357
 
414
358
    def writelines(self, lines):
415
 
        # profiling indicated a significant overhead
 
359
        # profiling indicated a significant overhead 
416
360
        # calling write for each line.
417
361
        # this batch call is a lot faster :).
418
362
        # (4 seconds to 1 seconds for the sample upgrades I was testing).
419
363
        self.write(''.join(lines))
420
364
 
421
 
    if sys.version_info > (2, 7):
422
 
        # As of Python 2.7 the crc32 must be positive when close is called
423
 
        def close(self):
424
 
            if self.fileobj is None:
425
 
                return
426
 
            if self.mode == gzip.WRITE:
427
 
                self.crc &= 0xFFFFFFFFL
428
 
            gzip.GzipFile.close(self)
429
365