~bzr-pqm/bzr/bzr.dev

2052.3.2 by John Arbash Meinel
Change Copyright .. by Canonical to Copyright ... Canonical
1
# Copyright (C) 2005, 2006 Canonical Ltd
1641.1.1 by Robert Collins
* Various microoptimisations to knit and gzip - reducing function call
2
# Written by Robert Collins <robert.collins@canonical.com>
3
#
4
# This program is free software; you can redistribute it and/or modify
5
# it under the terms of the GNU General Public License as published by
6
# the Free Software Foundation; either version 2 of the License, or
7
# (at your option) any later version.
8
#
9
# This program is distributed in the hope that it will be useful,
10
# but WITHOUT ANY WARRANTY; without even the implied warranty of
11
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12
# GNU General Public License for more details.
13
#
14
# You should have received a copy of the GNU General Public License
15
# along with this program; if not, write to the Free Software
4183.7.1 by Sabin Iacob
update FSF mailing address
16
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
1641.1.1 by Robert Collins
* Various microoptimisations to knit and gzip - reducing function call
17
18
"""Bzrlib specific gzip tunings. We plan to feed these to the upstream gzip."""
19
1908.4.12 by John Arbash Meinel
Minor change to tuned_gzip.
20
from cStringIO import StringIO
1908.4.5 by John Arbash Meinel
Some small tweaks to knit and tuned_gzip to shave off another couple seconds
21
1641.1.1 by Robert Collins
* Various microoptimisations to knit and gzip - reducing function call
22
# make GzipFile faster:
23
import gzip
3734.2.1 by Vincent Ladeuil
Fix U32, LOWU32 disapearance in python-2.6.
24
from gzip import FEXTRA, FCOMMENT, FNAME, FHCRC
1641.1.1 by Robert Collins
* Various microoptimisations to knit and gzip - reducing function call
25
import sys
26
import struct
27
import zlib
28
1666.1.6 by Robert Collins
Make knit the default format.
29
# we want a \n preserved, break on \n only splitlines.
30
import bzrlib
31
2817.3.1 by Robert Collins
* New helper ``bzrlib.tuned_gzip.bytes_to_gzip`` which takes a byte string
32
__all__ = ["GzipFile", "bytes_to_gzip"]
33
34
3734.2.1 by Vincent Ladeuil
Fix U32, LOWU32 disapearance in python-2.6.
35
def U32(i):
36
    """Return i as an unsigned integer, assuming it fits in 32 bits.
37
38
    If it's >= 2GB when viewed as a 32-bit unsigned int, return a long.
39
    """
40
    if i < 0:
41
        i += 1L << 32
42
    return i
43
44
45
def LOWU32(i):
46
    """Return the low-order 32 bits of an int, as a non-negative int."""
47
    return i & 0xFFFFFFFFL
48
49
2817.3.1 by Robert Collins
* New helper ``bzrlib.tuned_gzip.bytes_to_gzip`` which takes a byte string
50
def bytes_to_gzip(bytes, factory=zlib.compressobj,
51
    level=zlib.Z_DEFAULT_COMPRESSION, method=zlib.DEFLATED,
52
    width=-zlib.MAX_WBITS, mem=zlib.DEF_MEM_LEVEL,
53
    crc32=zlib.crc32):
54
    """Create a gzip file containing bytes and return its content."""
55
    result = [
56
        '\037\213'  # self.fileobj.write('\037\213')  # magic header
57
        '\010'      # self.fileobj.write('\010')      # compression method
58
                    # fname = self.filename[:-3]
59
                    # flags = 0
60
                    # if fname:
61
                    #     flags = FNAME
62
        '\x00'      # self.fileobj.write(chr(flags))
63
        '\0\0\0\0'  # write32u(self.fileobj, long(time.time()))
64
        '\002'      # self.fileobj.write('\002')
65
        '\377'      # self.fileobj.write('\377')
66
                    # if fname:
67
        ''          #     self.fileobj.write(fname + '\000')
68
        ]
69
    # using a compressobj avoids a small header and trailer that the compress()
70
    # utility function adds.
71
    compress = factory(level, method, width, mem, 0)
72
    result.append(compress.compress(bytes))
73
    result.append(compress.flush())
74
    result.append(struct.pack("<L", LOWU32(crc32(bytes))))
75
    # size may exceed 2GB, or even 4GB
76
    result.append(struct.pack("<L", LOWU32(len(bytes))))
77
    return ''.join(result)
1641.1.1 by Robert Collins
* Various microoptimisations to knit and gzip - reducing function call
78
79
80
class GzipFile(gzip.GzipFile):
81
    """Knit tuned version of GzipFile.
82
83
    This is based on the following lsprof stats:
84
    python 2.4 stock GzipFile write:
85
    58971      0   5644.3090   2721.4730   gzip:193(write)
86
    +58971     0   1159.5530   1159.5530   +<built-in method compress>
87
    +176913    0    987.0320    987.0320   +<len>
88
    +58971     0    423.1450    423.1450   +<zlib.crc32>
89
    +58971     0    353.1060    353.1060   +<method 'write' of 'cStringIO.
90
                                            StringO' objects>
91
    tuned GzipFile write:
92
    58971      0   4477.2590   2103.1120   bzrlib.knit:1250(write)
93
    +58971     0   1297.7620   1297.7620   +<built-in method compress>
94
    +58971     0    406.2160    406.2160   +<zlib.crc32>
95
    +58971     0    341.9020    341.9020   +<method 'write' of 'cStringIO.
96
                                            StringO' objects>
97
    +58971     0    328.2670    328.2670   +<len>
98
99
100
    Yes, its only 1.6 seconds, but they add up.
101
    """
102
103
    def _add_read_data(self, data):
104
        # 4169 calls in 183
105
        # temp var for len(data) and switch to +='s.
106
        # 4169 in 139
107
        len_data = len(data)
108
        self.crc = zlib.crc32(data, self.crc)
109
        self.extrabuf += data
110
        self.extrasize += len_data
111
        self.size += len_data
112
1908.4.3 by John Arbash Meinel
Shave another second off of _record_to_data time, by optimizing single write versus multiple writes
113
    def _write_gzip_header(self):
114
        """A tuned version of gzip._write_gzip_header
115
116
        We have some extra constrains that plain Gzip does not.
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
117
        1) We want to write the whole blob at once. rather than multiple
1908.4.10 by John Arbash Meinel
Small cleanups
118
           calls to fileobj.write().
1908.4.3 by John Arbash Meinel
Shave another second off of _record_to_data time, by optimizing single write versus multiple writes
119
        2) We never have a filename
120
        3) We don't care about the time
121
        """
122
        self.fileobj.write(
123
           '\037\213'   # self.fileobj.write('\037\213')  # magic header
124
            '\010'      # self.fileobj.write('\010')      # compression method
125
                        # fname = self.filename[:-3]
126
                        # flags = 0
127
                        # if fname:
128
                        #     flags = FNAME
129
            '\x00'      # self.fileobj.write(chr(flags))
130
            '\0\0\0\0'  # write32u(self.fileobj, long(time.time()))
131
            '\002'      # self.fileobj.write('\002')
132
            '\377'      # self.fileobj.write('\377')
133
                        # if fname:
134
            ''          #     self.fileobj.write(fname + '\000')
135
            )
136
1641.1.1 by Robert Collins
* Various microoptimisations to knit and gzip - reducing function call
137
    def _read(self, size=1024):
138
        # various optimisations:
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
139
        # reduces lsprof count from 2500 to
1641.1.1 by Robert Collins
* Various microoptimisations to knit and gzip - reducing function call
140
        # 8337 calls in 1272, 365 internal
141
        if self.fileobj is None:
142
            raise EOFError, "Reached EOF"
143
144
        if self._new_member:
145
            # If the _new_member flag is set, we have to
146
            # jump to the next member, if there is one.
147
            #
148
            # First, check if we're at the end of the file;
149
            # if so, it's time to stop; no more members to read.
150
            next_header_bytes = self.fileobj.read(10)
151
            if next_header_bytes == '':
152
                raise EOFError, "Reached EOF"
153
154
            self._init_read()
155
            self._read_gzip_header(next_header_bytes)
156
            self.decompress = zlib.decompressobj(-zlib.MAX_WBITS)
157
            self._new_member = False
158
159
        # Read a chunk of data from the file
160
        buf = self.fileobj.read(size)
161
162
        # If the EOF has been reached, flush the decompression object
163
        # and mark this object as finished.
164
165
        if buf == "":
166
            self._add_read_data(self.decompress.flush())
3376.2.4 by Martin Pool
Remove every assert statement from bzrlib!
167
            if len(self.decompress.unused_data) < 8:
168
                raise AssertionError("what does flush do?")
1666.1.11 by Robert Collins
Really fix short-read support in tuned_gzip. The python zlib module behaved differently than thought.
169
            self._gzip_tail = self.decompress.unused_data[0:8]
1641.1.1 by Robert Collins
* Various microoptimisations to knit and gzip - reducing function call
170
            self._read_eof()
171
            # tell the driving read() call we have stuffed all the data
172
            # in self.extrabuf
173
            raise EOFError, 'Reached EOF'
174
175
        self._add_read_data(self.decompress.decompress(buf))
176
177
        if self.decompress.unused_data != "":
178
            # Ending case: we've come to the end of a member in the file,
179
            # so seek back to the start of the data for the next member which
180
            # is the length of the decompress objects unused data - the first
181
            # 8 bytes for the end crc and size records.
182
            #
183
            # so seek back to the start of the unused data, finish up
184
            # this member, and read a new gzip header.
185
            # (The number of bytes to seek back is the length of the unused
186
            # data, minus 8 because those 8 bytes are part of this member.
187
            seek_length = len (self.decompress.unused_data) - 8
1666.1.2 by Robert Collins
Fix race condition between end of stream and end of file with tuned_gzip.
188
            if seek_length > 0:
189
                # we read too much data
1641.1.1 by Robert Collins
* Various microoptimisations to knit and gzip - reducing function call
190
                self.fileobj.seek(-seek_length, 1)
1666.1.11 by Robert Collins
Really fix short-read support in tuned_gzip. The python zlib module behaved differently than thought.
191
                self._gzip_tail = self.decompress.unused_data[0:8]
1666.1.2 by Robert Collins
Fix race condition between end of stream and end of file with tuned_gzip.
192
            elif seek_length < 0:
193
                # we haven't read enough to check the checksum.
3376.2.4 by Martin Pool
Remove every assert statement from bzrlib!
194
                if not (-8 < seek_length):
195
                    raise AssertionError("too great a seek")
1666.1.2 by Robert Collins
Fix race condition between end of stream and end of file with tuned_gzip.
196
                buf = self.fileobj.read(-seek_length)
1666.1.11 by Robert Collins
Really fix short-read support in tuned_gzip. The python zlib module behaved differently than thought.
197
                self._gzip_tail = self.decompress.unused_data + buf
198
            else:
199
                self._gzip_tail = self.decompress.unused_data
1641.1.1 by Robert Collins
* Various microoptimisations to knit and gzip - reducing function call
200
201
            # Check the CRC and file size, and set the flag so we read
202
            # a new member on the next call
203
            self._read_eof()
204
            self._new_member = True
205
206
    def _read_eof(self):
207
        """tuned to reduce function calls and eliminate file seeking:
208
        pass 1:
209
        reduces lsprof count from 800 to 288
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
210
        4168 in 296
1641.1.1 by Robert Collins
* Various microoptimisations to knit and gzip - reducing function call
211
        avoid U32 call by using struct format L
212
        4168 in 200
213
        """
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
214
        # We've read to the end of the file, so we should have 8 bytes of
1759.2.2 by Jelmer Vernooij
Revert some of my spelling fixes and fix some typos after review by Aaron.
215
        # unused data in the decompressor. If we don't, there is a corrupt file.
1641.1.1 by Robert Collins
* Various microoptimisations to knit and gzip - reducing function call
216
        # We use these 8 bytes to calculate the CRC and the recorded file size.
217
        # We then check the that the computed CRC and size of the
218
        # uncompressed data matches the stored values.  Note that the size
219
        # stored is the true file size mod 2**32.
3376.2.4 by Martin Pool
Remove every assert statement from bzrlib!
220
        if not (len(self._gzip_tail) == 8):
221
            raise AssertionError("gzip trailer is incorrect length.")
1666.1.11 by Robert Collins
Really fix short-read support in tuned_gzip. The python zlib module behaved differently than thought.
222
        crc32, isize = struct.unpack("<LL", self._gzip_tail)
1641.1.1 by Robert Collins
* Various microoptimisations to knit and gzip - reducing function call
223
        # note that isize is unsigned - it can exceed 2GB
224
        if crc32 != U32(self.crc):
1666.1.2 by Robert Collins
Fix race condition between end of stream and end of file with tuned_gzip.
225
            raise IOError, "CRC check failed %d %d" % (crc32, U32(self.crc))
1641.1.1 by Robert Collins
* Various microoptimisations to knit and gzip - reducing function call
226
        elif isize != LOWU32(self.size):
227
            raise IOError, "Incorrect length of data produced"
228
229
    def _read_gzip_header(self, bytes=None):
230
        """Supply bytes if the minimum header size is already read.
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
231
1641.1.1 by Robert Collins
* Various microoptimisations to knit and gzip - reducing function call
232
        :param bytes: 10 bytes of header data.
233
        """
234
        """starting cost: 300 in 3998
235
        15998 reads from 3998 calls
236
        final cost 168
237
        """
238
        if bytes is None:
239
            bytes = self.fileobj.read(10)
240
        magic = bytes[0:2]
241
        if magic != '\037\213':
242
            raise IOError, 'Not a gzipped file'
243
        method = ord(bytes[2:3])
244
        if method != 8:
245
            raise IOError, 'Unknown compression method'
246
        flag = ord(bytes[3:4])
247
        # modtime = self.fileobj.read(4) (bytes [4:8])
248
        # extraflag = self.fileobj.read(1) (bytes[8:9])
249
        # os = self.fileobj.read(1) (bytes[9:10])
250
        # self.fileobj.read(6)
251
252
        if flag & FEXTRA:
253
            # Read & discard the extra field, if present
254
            xlen = ord(self.fileobj.read(1))
255
            xlen = xlen + 256*ord(self.fileobj.read(1))
256
            self.fileobj.read(xlen)
257
        if flag & FNAME:
258
            # Read and discard a null-terminated string containing the filename
259
            while True:
260
                s = self.fileobj.read(1)
261
                if not s or s=='\000':
262
                    break
263
        if flag & FCOMMENT:
264
            # Read and discard a null-terminated string containing a comment
265
            while True:
266
                s = self.fileobj.read(1)
267
                if not s or s=='\000':
268
                    break
269
        if flag & FHCRC:
270
            self.fileobj.read(2)     # Read & discard the 16-bit header CRC
271
272
    def readline(self, size=-1):
273
        """Tuned to remove buffer length calls in _unread and...
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
274
1641.1.1 by Robert Collins
* Various microoptimisations to knit and gzip - reducing function call
275
        also removes multiple len(c) calls, inlines _unread,
276
        total savings - lsprof 5800 to 5300
277
        phase 2:
278
        4168 calls in 2233
279
        8176 calls to read() in 1684
280
        changing the min chunk size to 200 halved all the cache misses
281
        leading to a drop to:
282
        4168 calls in 1977
283
        4168 call to read() in 1646
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
284
        - i.e. just reduced the function call overhead. May be worth
1641.1.1 by Robert Collins
* Various microoptimisations to knit and gzip - reducing function call
285
          keeping.
286
        """
287
        if size < 0: size = sys.maxint
288
        bufs = []
289
        readsize = min(200, size)    # Read from the file in small chunks
290
        while True:
291
            if size == 0:
292
                return "".join(bufs) # Return resulting line
293
294
            # c is the chunk
295
            c = self.read(readsize)
296
            # number of bytes read
297
            len_c = len(c)
298
            i = c.find('\n')
299
            if size is not None:
300
                # We set i=size to break out of the loop under two
301
                # conditions: 1) there's no newline, and the chunk is
302
                # larger than size, or 2) there is a newline, but the
303
                # resulting line would be longer than 'size'.
304
                if i==-1 and len_c > size: i=size-1
305
                elif size <= i: i = size -1
306
307
            if i >= 0 or c == '':
308
                # if i>= 0 we have a newline or have triggered the above
309
                # if size is not None condition.
310
                # if c == '' its EOF.
311
                bufs.append(c[:i+1])    # Add portion of last chunk
312
                # -- inlined self._unread --
313
                ## self._unread(c[i+1:], len_c - i)   # Push back rest of chunk
314
                self.extrabuf = c[i+1:] + self.extrabuf
315
                self.extrasize = len_c - i + self.extrasize
316
                self.offset -= len_c - i
317
                # -- end inlined self._unread --
318
                return ''.join(bufs)    # Return resulting line
319
320
            # Append chunk to list, decrease 'size',
321
            bufs.append(c)
322
            size = size - len_c
323
            readsize = min(size, readsize * 2)
324
325
    def readlines(self, sizehint=0):
326
        # optimise to avoid all the buffer manipulation
327
        # lsprof changed from:
328
        # 4168 calls in 5472 with 32000 calls to readline()
329
        # to :
330
        # 4168 calls in 417.
331
        # Negative numbers result in reading all the lines
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
332
1908.4.15 by John Arbash Meinel
comment on tuned_gzip.readlines() functionality.
333
        # python's gzip routine uses sizehint. This is a more efficient way
334
        # than python uses to honor it. But it is even more efficient to
335
        # just read the entire thing and use cStringIO to split into lines.
336
        # if sizehint <= 0:
337
        #     sizehint = -1
338
        # content = self.read(sizehint)
339
        # return bzrlib.osutils.split_lines(content)
1908.4.12 by John Arbash Meinel
Minor change to tuned_gzip.
340
        content = StringIO(self.read(-1))
1908.4.5 by John Arbash Meinel
Some small tweaks to knit and tuned_gzip to shave off another couple seconds
341
        return content.readlines()
1641.1.1 by Robert Collins
* Various microoptimisations to knit and gzip - reducing function call
342
343
    def _unread(self, buf, len_buf=None):
344
        """tuned to remove unneeded len calls.
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
345
1641.1.1 by Robert Collins
* Various microoptimisations to knit and gzip - reducing function call
346
        because this is such an inner routine in readline, and readline is
347
        in many inner loops, this has been inlined into readline().
348
349
        The len_buf parameter combined with the reduction in len calls dropped
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
350
        the lsprof ms count for this routine on my test data from 800 to 200 -
1641.1.1 by Robert Collins
* Various microoptimisations to knit and gzip - reducing function call
351
        a 75% saving.
352
        """
353
        if len_buf is None:
354
            len_buf = len(buf)
355
        self.extrabuf = buf + self.extrabuf
356
        self.extrasize = len_buf + self.extrasize
357
        self.offset -= len_buf
358
359
    def write(self, data):
360
        if self.mode != gzip.WRITE:
361
            import errno
362
            raise IOError(errno.EBADF, "write() on read-only GzipFile object")
363
364
        if self.fileobj is None:
365
            raise ValueError, "write() on closed GzipFile object"
366
        data_len = len(data)
367
        if data_len > 0:
368
            self.size = self.size + data_len
369
            self.crc = zlib.crc32(data, self.crc)
370
            self.fileobj.write( self.compress.compress(data) )
371
            self.offset += data_len
372
373
    def writelines(self, lines):
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
374
        # profiling indicated a significant overhead
1641.1.1 by Robert Collins
* Various microoptimisations to knit and gzip - reducing function call
375
        # calling write for each line.
376
        # this batch call is a lot faster :).
377
        # (4 seconds to 1 seconds for the sample upgrades I was testing).
378
        self.write(''.join(lines))
379
380