[issue2523] binary buffered reading is quadratic
Antoine Pitrou [EMAIL PROTECTED] added the comment: 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 -- resolution: - fixed status: open - closed ___ Python tracker [EMAIL PROTECTED] http://bugs.python.org/issue2523 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2523] binary buffered reading is quadratic
Antoine Pitrou [EMAIL PROTECTED] added the comment: 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? :) ___ Python tracker [EMAIL PROTECTED] http://bugs.python.org/issue2523 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2523] binary buffered reading is quadratic
Alexandre Vassalotti [EMAIL PROTECTED] added the comment: Antoine wrote: Le lundi 21 juillet 2008 à 21:18 +, 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. ___ Python tracker [EMAIL PROTECTED] http://bugs.python.org/issue2523 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2523] binary buffered reading is quadratic
Antoine Pitrou [EMAIL PROTECTED] added the comment: Selon Martin v. Löwis [EMAIL PROTECTED]: Martin v. Löwis [EMAIL PROTECTED] 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. ___ Python tracker [EMAIL PROTECTED] http://bugs.python.org/issue2523 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2523] binary buffered reading is quadratic
Martin v. Löwis [EMAIL PROTECTED] added the comment: 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. ___ Python tracker [EMAIL PROTECTED] http://bugs.python.org/issue2523 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2523] binary buffered reading is quadratic
Antoine Pitrou [EMAIL PROTECTED] added the comment: Le lundi 21 juillet 2008 à 21:18 +, 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. ___ Python tracker [EMAIL PROTECTED] http://bugs.python.org/issue2523 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2523] binary buffered reading is quadratic
Martin v. Löwis [EMAIL PROTECTED] 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.e. the way it is in patch 2). In particular, if the stream is unbuffered, it shouldn't ever end up with buffered data. -- nosy: +loewis ___ Python tracker [EMAIL PROTECTED] http://bugs.python.org/issue2523 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2523] binary buffered reading is quadratic
Antoine Pitrou [EMAIL PROTECTED] added the comment: If nobody objects I'll commit Alexandre's patch in a few days (after beta 2 though). ___ Python tracker [EMAIL PROTECTED] http://bugs.python.org/issue2523 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2523] binary buffered reading is quadratic
Antoine Pitrou [EMAIL PROTECTED] added the comment: 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. ___ Python tracker [EMAIL PROTECTED] http://bugs.python.org/issue2523 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2523] binary buffered reading is quadratic
Alexandre Vassalotti [EMAIL PROTECTED] added the comment: 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. ___ Python tracker [EMAIL PROTECTED] http://bugs.python.org/issue2523 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2523] binary buffered reading is quadratic
Antoine Pitrou [EMAIL PROTECTED] added the comment: 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... ___ Python tracker [EMAIL PROTECTED] http://bugs.python.org/issue2523 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2523] binary buffered reading is quadratic
Changes by Gregory P. Smith [EMAIL PROTECTED]: -- nosy: +gregory.p.smith priority: - high __ Tracker [EMAIL PROTECTED] http://bugs.python.org/issue2523 __ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2523] binary buffered reading is quadratic
Antoine Pitrou [EMAIL PROTECTED] added the comment: 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. Added file: http://bugs.python.org/file10222/binaryio2.patch __ Tracker [EMAIL PROTECTED] http://bugs.python.org/issue2523 __ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2523] binary buffered reading is quadratic
Antoine Pitrou [EMAIL PROTECTED] added the comment:
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
--
keywords: +patch
Added file: http://bugs.python.org/file10216/binaryio1.patch
__
Tracker [EMAIL PROTECTED]
http://bugs.python.org/issue2523
__
___
Python-bugs-list mailing list
Unsubscribe:
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2523] binary buffered reading is quadratic
Alexandre Vassalotti [EMAIL PROTECTED] added the comment: 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. __ Tracker [EMAIL PROTECTED] http://bugs.python.org/issue2523 __ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2523] binary buffered reading is quadratic
Antoine Pitrou [EMAIL PROTECTED] added the comment: 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. __ Tracker [EMAIL PROTECTED] http://bugs.python.org/issue2523 __ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2523] binary buffered reading is quadratic
Changes by Alexandre Vassalotti [EMAIL PROTECTED]: -- nosy: +alexandre.vassalotti __ Tracker [EMAIL PROTECTED] http://bugs.python.org/issue2523 __ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2523] binary buffered reading is quadratic
Antoine Pitrou [EMAIL PROTECTED] added the comment: 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. __ Tracker [EMAIL PROTECTED] http://bugs.python.org/issue2523 __ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2523] binary buffered reading is quadratic
New submission from Antoine Pitrou [EMAIL PROTECTED]:
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()
1 loops, best of 3: 46 usec per loop
./python -m timeit -s f = open('100KB', 'rb', buffering=0) f.seek(0);
f.read()
1 loops, best of 3: 88.7 usec per loop
./python -m timeit -s f = open('200KB', 'rb', buffering=0) f.seek(0);
f.read()
1 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()
1 loops, best of 3: 34.4 usec per loop
python -m timeit -s f = open('100KB', 'rb') f.seek(0); f.read()
1 loops, best of 3: 62.3 usec per loop
python -m timeit -s f = open('200KB', 'rb') f.seek(0); f.read()
1 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?
--
components: Library (Lib)
messages: 64788
nosy: pitrou
severity: normal
status: open
title: binary buffered reading is quadratic
type: performance
versions: Python 3.0
__
Tracker [EMAIL PROTECTED]
http://bugs.python.org/issue2523
__
___
Python-bugs-list mailing list
Unsubscribe:
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
