On Tue, Sep 28, 2010 at 5:57 AM, Antoine Pitrou <solipsis@pitrou.net> wrote:
On Mon, 27 Sep 2010 17:39:45 -0700 Guido van Rossum <guido@python.org> wrote:
On Mon, Sep 27, 2010 at 3:41 PM, Antoine Pitrou <solipsis@pitrou.net> wrote:
While trying to solve #3873 (poor performance of pickle on file objects, due to the overhead of calling read() with very small values), it occurred to me that the prefetching facilities offered by BufferedIOBase are not flexible and efficient enough.
I haven't read the whole bug but there seem to be lots of different smaller issues there, right?
The bug entry is quite old and at first the slowness had to do with the pure Python IO layer. Now the remaining performance difference with Python 2 is entirely caused by the following core issue:
It seems that one (unfortunate) constraint is that reading pickles cannot use buffered I/O (at least not on a non-seekable file) because the API has been documented to leave the file positioned right after the last byte of the pickled data, right?
Right.
Indeed, if you use seek() and read(), 1) you limit yourself to seekable files 2) performance can be hampered by very bad seek() performance (this is true on GzipFile).
Ow... I've always assumed that seek() is essentially free, because that's how a typical OS kernel implements it. If seek() is bad on GzipFile, how hard would it be to fix this?
The worst case is backwards seeks. Forward seeks are implemented as a simply read(), which makes them O(k) where k is the displacement. For buffering applications where k is bounded by the buffer size, it is O(1) (still with, of course, a non-trivial multiplier).
Backwards seeks are implemented as rewinding the whole file (seek(0)) and then reading again up to the requested position, which makes them O(n) with n the absolute target position. When your requirement is to rewind by a bounded number of bytes in order to undo some readahead, this is rather catastrophic.
I don't know how the gzip algorithm works under the hood; my impression is that optimizing backwards seeks would have us save us checkpoints of the decompressor state and restore it if needed. It doesn't sound like a trivial improvement, and would involve tradeoffs w.r.t. to performance of sequential reads.
(I haven't looked at BZ2File, which has a totally different -- and outdated -- implementation)
It's why I would favour the peek() (or peek()-like, as in the prefetch() idea) approach anyway. Not only it works on unseekable files, but implementing peek() when you have an internal buffer is quite simple (see GzipFile.peek here: http://bugs.python.org/issue9962).
peek() could also be added to BytesIO even though it claims to implement RawIOBase rather than BufferedIOBase. (buf of course, when you have a BytesIO, you can simply feed its getvalue() or getbuffer() directly to pickle.loads)
How common is the use case where you need to read a gzipped pickle *and* you need to leave the unzipped stream positioned exactly at the end of the pickle?
I really don't know. But I don't think we can break the API for a special case without potentially causing nasty surprises for the user.
Also, my intuition is that pickling directly from a stream is partly meant for cases where you want to access data following the pickle data in the stream.
If instead you use peek() and read(), the situation is better, but you end up doing multiple copies of data; also, you must call read() to advance the file pointer even though you don't care about the results.
Have you measured how bad the situation is if you do implement it this way?
It is actually quite good compared to the statu quo (3x to 10x), and as good as the seek/read solution for regular files (and, of course, much better for gzipped files once GzipFile.peek is implemented): http://bugs.python.org/issue3873#msg117483
So, for solving the unpickle performance issue, it is sufficient. Chances are the bottleneck for further improvements would be in the unpickling logic itself. It feels a bit clunky, though.
Direct timing shows that peek()+read() has a non-trivial cost compared to read():
$ ./python -m timeit -s "f=open('Misc/HISTORY', 'rb')" "f.seek(0)" \ "while f.read(4096): pass" 1000 loops, best of 3: 277 usec per loop $ ./python -m timeit -s "f=open('Misc/HISTORY', 'rb')" "f.seek(0)" \ "while f.read(4096): f.peek(4096)" 1000 loops, best of 3: 361 usec per loop
(that's on a C extension type where peek() is almost a single call to PyBytes_FromStringAndSize)
So I would propose adding the following method to BufferedIOBase:
prefetch(self, buffer, skip, minread)
Skip `skip` bytes from the stream. Then, try to read at least `minread` bytes and write them into `buffer`. The file pointer is advanced by at most `skip + minread`, or less if the end of file was reached. The total number of bytes written in `buffer` is returned, which can be more than `minread` if additional bytes could be prefetched (but, of course, cannot be more than `len(buffer)`).
Arguments: - `buffer`: a writable buffer (e.g. bytearray) - `skip`: number of bytes to skip (must be >= 0) - `minread`: number of bytes to read (must be >= 0 and <= len(buffer))
I like the idea of an API that combines seek and read into a mutable buffer. However the semantics of this call seem really weird: there is no direct relationship between where it leaves the stream position and how much data it reads into the buffer. can you explain how exactly this will help solve the gzipped pickle performance problem?
The general idea with buffering is that: - you want to skip the previously prefetched bytes (through peek() or prefetch()) which have been consumed -> hence the `skip` argument - you want to consume a known number of bytes from the stream (for example a 4-bytes little-endian integer) -> hence the `minread` argument - you would like to prefetch some more bytes if cheaply possible, so as to avoid calling read() or prefetch() too much; but you don't know yet if you will consume those bytes, so the file pointer shouldn't be advanced for them
If you don't prefetch more than the minimum needed amount of bytes, you don't solve the performance problem at all (unpickling needs many tiny reads). If you advance the file pointer after the whole prefetched data (even though it might not be entirely consumed), you need to seek() back at the end: it doesn't work on unseekable files, and is very slow on some seekable file types.
So, the proposal is like a combination of forward seek() + read() + peek() in a single call. With the advantages that: - it works on non-seekable files (things like SocketIO) - it allows the caller to operate in its own buffer (this is nice in C) - it returns the data naturally concatenated, so you don't have to do it yourself if needed - it gives more guarantees than peek() as to the min and max number of bytes returned; peek(), as it is not allowed to advance the file pointer, can return as little as 1 byte (even if you ask for 4096, and even if EOF isn't reached)
I also find it interesting that implementing a single primitive be enough for creating custom buffered types (by deriving other methods from it), but the aesthetics of this can be controversial.
Thanks for the long explanation. I have some further questions: It seems this won't make any difference for a truly unbuffered stream, right? A truly unbuffered stream would not have a buffer where it could save the bytes that were prefetched past the stream position, so it wouldn't return any optional extra bytes, so there would be no speedup. And for a buffered stream, it would be much simpler to just read ahead in large chunks and seek back once you've found the end. (Actually for a buffered stream I suppose that many short read() and small seek() calls aren't actually slow since most of the time they work within the buffer.) So it seems the API is specifically designed to improve the situation with GzipFile since it maintains the fiction of an unbuffered file but in fact has some internal buffer space. I wonder if it wouldn't be better to add an extra buffer to GzipFile so small seek() and read() calls can be made more efficient? In fact, this makes me curious as to the use that unpickling can make of the prefetch() call -- I suppose you had to implement some kind of layer on top of prefetch() that behaves more like a plain unbuffered file? I want to push back on this more, primarily because a new primitive I/O operation has high costs: it can never be removed, it has to be added to every stream implementation, developers need to learn to use the new operation, and so on. A local change that only affects GzipFile doesn't have any of these problems. Also, if you can believe the multi-core crowd, a very different possible future development might be to run the gunzip algorithm and the unpickle algorithm in parallel, on separate cores. Truly such a solution would require totally *different* new I/O primitives, which might have a higher chance of being reusable outside the context of pickle. -- --Guido van Rossum (python.org/~guido)