In py3k, buffered binary IO can be quadratic when e.g. reading a whole file.
This is a small test on 50KB, 100KB and 200KB files:

-> py3k with buffering:

./python -m timeit -s "f = open('50KB', 'rb')" "f.seek(0); f.read()"
1000 loops, best of 3: 286 usec per loop
./python -m timeit -s "f = open('100KB', 'rb')" "f.seek(0); f.read()"
1000 loops, best of 3: 1.07 msec per loop
./python -m timeit -s "f = open('200KB', 'rb')" "f.seek(0); f.read()"
100 loops, best of 3: 4.85 msec per loop

-> py3k without buffering (just the raw FileIO layer):

./python -m timeit -s "f = open('50KB', 'rb', buffering=0)" "f.seek(0);
f.read()"
10000 loops, best of 3: 46 usec per loop
./python -m timeit -s "f = open('100KB', 'rb', buffering=0)" "f.seek(0);
f.read()"
10000 loops, best of 3: 88.7 usec per loop
./python -m timeit -s "f = open('200KB', 'rb', buffering=0)" "f.seek(0);
f.read()"
10000 loops, best of 3: 156 usec per loop

-> for comparison, Python 2.5:

python -m timeit -s "f = open('50KB', 'rb')" "f.seek(0); f.read()"
10000 loops, best of 3: 34.4 usec per loop
python -m timeit -s "f = open('100KB', 'rb')" "f.seek(0); f.read()"
10000 loops, best of 3: 62.3 usec per loop
python -m timeit -s "f = open('200KB', 'rb')" "f.seek(0); f.read()"
10000 loops, best of 3: 119 usec per loop

I'm posting this issue as a reminder, but perhaps someone is already
working on this, or the goal is to translate it to C ultimately?

By the way, a simple way to fix it would be to use a native BytesIO
object (as provided by Alexandre's patch in #1751) rather than a str
object for the underlying buffer.

Here is a pure Python patch removing the quadratic behaviour and trying
to make read operations generally faster.

Here are some numbers:

./python -m timeit -s "f = open('50KB', 'rb')" "f.seek(0)" "while
f.read(11): pass"

-> py3k without patch: 23.6 msec per loop
-> py3k with patch: 14.5 msec per loop
-> Python 2.5: 4.72 msec per loop

./python -m timeit -s "f = open('50KB', 'rb')" "f.seek(0); f.read()"

-> py3k without patch: 284 usec per loop
-> py3k with patch: 90.1 usec per loop
-> Python 2.5: 33.8 usec per loop

./python -m timeit -s "f = open('100KB', 'rb')" "f.seek(0); f.read()"

-> py3k without patch: 828 usec per loop
-> py3k with patch: 142 usec per loop
-> Python 2.5: 62.5 usec per loop

./python -m timeit -s "f = open('200KB', 'rb')" "f.seek(0); f.read()"

-> py3k without patch: 3.67 msec per loop
-> py3k with patch: 375 usec per loop
-> Python 2.5: 131 usec per loop

And, for the record, with a 10MB file:

./python -m timeit -s "f = open('10MB', 'rb')" "f.seek(0); f.read()"

-> py3k without patch: still running after more than one minute, gave up
-> py3k with patch: 38.6 msec per loop
-> Python 2.5: 20.4 msec per loop

I see that the code is still using the immutable bytes object for its
buffer (which forces Python to create a new buffer every time its
modified). Also, I think it worthwhile to check if using a pre-allocated
bytearray object (i.e., bytearray(buffer_size) where `buffer_size` is an
integer) would have any performance benefits.

Hi Alexandre,

I first tried to use a (non-preallocated) bytearray object and, after
trying several optimization schemes, I found out that the best one
worked as well with an immutable bytes object :) I also found out that
the bytes <-> bytearray conversion costs can be noticeable in some
benchmarks.

The internal buffer is rarely reallocated because the current offset
inside it is remembered instead; also, when reading bytes from the
underlying unbuffered stream, a list of bytes objects is accumulated and
then joined at the end.

I think a preallocated bytearray would not make a lot of sense since we
can't readinto() an arbitrary position, so we still have a memory copy
from the bytes object returned by raw.read() to the bytearray buffer,
and then when returning the result to the user as a bytes object we have
another memory copy. In other words each read byte is copied twice more.

Of course, if this code was rewritten in C, different compromises would
be possible.

cheers

Antoine.

Some code relies on -1 being usable as the default value for read()
(instead of None), this new patch conforms to this expectation. It fixes
some failures in test_mailbox.

I recommend not letting this issue rot too much :) Eating 20+ seconds to
read the contents of a 10MB binary file in one pass is not very good
marketing-wise, and the betas are coming soon...

I am going to go through your patch as soon as I get the time -- i.e.,
later today or tomorrow morning.

I reviewed the patch and I found a few bugs -- i.e., peek() was
replacing the buffer content, read() wasn't written in consideration of
non-blocking streams, the removal of the None check in
BufferedRandom.read() was wrong.

Here's an updated patch.

Thanks for the fixes.

By the way, I don't know much about non-blocking streams, but it seems
to me that "optimal" non-blocking read() would require that the chunks
we ask to the OS are block-aligned, which is not the case currently (we
use 2*avail, which can be an arbitrary value).

Oh, that is simple to fix. You can round the value 2*avail to the
nearest block by doing something like (2*avail) & ~(bksize-1) where
bksize is a power of 2, or the less magic (2*avail//bksize) * bksize.

Yup. However, if you try it, you'll probably notice that it decreases
performance of normal (blocking) reads as well :-)

Anyway, non-blocking file objects are pretty much second-class citizens
in Py3k right now, so my remark was theoretical.

If nobody objects I'll commit Alexandre's patch in a few days (after
beta 2 though).

I don't understand the second loop (where n is given). If n is given,
there should be only a single read operation, using

  max(buffer_size, n-avail)

(i.e. the way it is in patch 2). In particular, if the stream is
unbuffered, it shouldn't ever end up with buffered data.

Selon "Martin v. Löwis" <report@bugs.python.org>:
>
> Martin v. Löwis <martin@v.loewis.de> added the comment:
>
> I don't understand the second loop (where n is given). If n is given,
> there should be only a single read operation, using
>
>   max(buffer_size, n-avail)

I mimicked the original logic rather than rethink the algorithm. I'm not totally
sure what motivates the original logic but the purpose seems to be that
non-blocking streams can return at least a few bytes rather than an empty string
when less than N bytes are ready at OS level.

> (i.e. the way it is in patch 2). In particular, if the stream is
> unbuffered, it shouldn't ever end up with buffered data.

Hmm, what do you mean by "if the stream is unbuffered"? Unbuffered streams
should use the raw unbuffered objects (e.g. FileIO) rather than wrap them with
BufferedReader.

>>   max(buffer_size, n-avail)
> 
> I mimicked the original logic rather than rethink the algorithm. I'm not totally
> sure what motivates the original logic but the purpose seems to be that
> non-blocking streams can return at least a few bytes rather than an empty string
> when less than N bytes are ready at OS level.

IIUC, a read of the full requested size would achieve exactly that: on a
non-blocking stream (IIUC), a read will always return
min(bytes_available, bytes_requested).

> Hmm, what do you mean by "if the stream is unbuffered"? Unbuffered streams
> should use the raw unbuffered objects (e.g. FileIO) rather than wrap them with
> BufferedReader.

IIUC, io.open will always return a BufferedReader, potentially with
buffer_size=0 for unbuffered IO. This case must be supported.

Le lundi 21 juillet 2008 à 21:18 +0000, Martin v. Löwis a écrit :
> IIUC, a read of the full requested size would achieve exactly that: on a
> non-blocking stream (IIUC), a read will always return
> min(bytes_available, bytes_requested).

Hmm, it seems logical indeed... Alexandre, do you have other information
on the subject?

> IIUC, io.open will always return a BufferedReader, potentially with
> buffer_size=0 for unbuffered IO. This case must be supported.

No, io.open returns the raw object without wrapping it:

    if buffering == 0:
        if binary:
            raw._name = file
            raw._mode = mode
            return raw
        raise ValueError("can't have unbuffered text I/O")

We could even decide to raise a ValueError when trying to construct a
BufferedReader with a buffer_size < 1.

Antoine wrote:
> Le lundi 21 juillet 2008 à 21:18 +0000, Martin v. Löwis a écrit :
> > IIUC, a read of the full requested size would achieve exactly that: 
on a
> > non-blocking stream (IIUC), a read will always return
> > min(bytes_available, bytes_requested).
>
> Hmm, it seems logical indeed... Alexandre, do you have other 
information
> on the subject?

Martin is right. However, I don't how Python handle the case where 
bytes_available is zero (in C, an error value is returned and errno is 
set to EWOULDBLOCK).

When I revised the patch I had a weak understanding of nonblocking I/O. 
I thought the "exponential" reads were for nonblocking I/O, but I see 
now that is non-sense.

I am not sure, but I think Martin is also right about the second loop. 
The max() call should be changed back to "max(self.buffer_size, n))", 
like in the 2nd patch.

> When I revised the patch I had a weak understanding of nonblocking I/O.
> I thought the "exponential" reads were for nonblocking I/O, but I see
> now that is non-sense.

Fine, so it will make the patch simpler.

As for non-blocking IO, I think we should raise the general issue on
python-3000. There is no real support for it right now, by which I mean (1) no
easy and portable way of enable non-blocking IO on a file object and (2) no test
cases of non-blocking IO in real-world conditions (rather than with mock
objects). This shouldn't stop us from fixing the present bug though.

> I am not sure, but I think Martin is also right about the second loop.
> The max() call should be changed back to "max(self.buffer_size, n))",
> like in the 2nd patch.

Ok. Could you produce an updated patch? :)

Following our discussion and Guido's answer on python-3000 (*), I
committed a modified fix in r65264.

(*) http://mail.python.org/pipermail/python-3000/2008-July/014466.html