[issue15758] FileIO.readall() has worst case O(n^2) complexity

2013-05-18 Thread Richard Oudkerk
Changes by Richard Oudkerk shibt...@gmail.com: -- resolution: - fixed stage: patch review - committed/rejected status: open - closed ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue15758 ___

[issue15758] FileIO.readall() has worst case O(n^2) complexity

2013-05-17 Thread Richard Oudkerk
Richard Oudkerk added the comment: Updated patch adressing Antoine's comments. -- Added file: http://bugs.python.org/file30291/readall.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue15758

[issue15758] FileIO.readall() has worst case O(n^2) complexity

2013-05-17 Thread Richard Oudkerk
Changes by Richard Oudkerk shibt...@gmail.com: Removed file: http://bugs.python.org/file26985/readall-combined.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue15758 ___

[issue15758] FileIO.readall() has worst case O(n^2) complexity

2013-05-17 Thread Richard Oudkerk
Changes by Richard Oudkerk shibt...@gmail.com: Added file: http://bugs.python.org/file26986/readall-benchmark.py ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue15758 ___

[issue15758] FileIO.readall() has worst case O(n^2) complexity

2013-05-17 Thread Richard Oudkerk
Changes by Richard Oudkerk shibt...@gmail.com: Removed file: http://bugs.python.org/file30287/readall.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue15758 ___

[issue15758] FileIO.readall() has worst case O(n^2) complexity

2013-05-17 Thread Richard Oudkerk
Changes by Richard Oudkerk shibt...@gmail.com: Added file: http://bugs.python.org/file30293/readall.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue15758 ___

[issue15758] FileIO.readall() has worst case O(n^2) complexity

2013-05-17 Thread Richard Oudkerk
Changes by Richard Oudkerk shibt...@gmail.com: Removed file: http://bugs.python.org/file30291/readall.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue15758 ___

[issue15758] FileIO.readall() has worst case O(n^2) complexity

2013-05-17 Thread Richard Oudkerk
Richard Oudkerk added the comment: New patch. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue15758 ___ ___ Python-bugs-list mailing list

[issue15758] FileIO.readall() has worst case O(n^2) complexity

2013-05-17 Thread Richard Oudkerk
Changes by Richard Oudkerk shibt...@gmail.com: Added file: http://bugs.python.org/file30295/readall.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue15758 ___

[issue15758] FileIO.readall() has worst case O(n^2) complexity

2013-05-17 Thread Richard Oudkerk
Changes by Richard Oudkerk shibt...@gmail.com: Removed file: http://bugs.python.org/file30293/readall.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue15758 ___

[issue15758] FileIO.readall() has worst case O(n^2) complexity

2013-05-17 Thread Antoine Pitrou
Antoine Pitrou added the comment: Looks fine to me. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue15758 ___ ___ Python-bugs-list mailing list

[issue15758] FileIO.readall() has worst case O(n^2) complexity

2013-05-17 Thread Roundup Robot
Roundup Robot added the comment: New changeset e4c303d23d01 by Richard Oudkerk in branch 'default': Issue #15758: Fix FileIO.readall() so it no longer has O(n**2) complexity. http://hg.python.org/cpython/rev/e4c303d23d01 -- nosy: +python-dev ___

[issue15758] FileIO.readall() has worst case O(n^2) complexity

2013-05-16 Thread Richard Oudkerk
Richard Oudkerk added the comment: I have done an updated patch. It no longer special cases Windows, so realloc() is always used for enlarging the buffer (except when fstat() is missing). Antoine, do you think this is ready to commit? -- Added file:

[issue15758] FileIO.readall() has worst case O(n^2) complexity

2013-05-16 Thread Richard Oudkerk
Changes by Richard Oudkerk shibt...@gmail.com: Removed file: http://bugs.python.org/file26986/readall-benchmark.py ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue15758 ___

[issue15758] FileIO.readall() has worst case O(n^2) complexity

2013-05-16 Thread Antoine Pitrou
Antoine Pitrou added the comment: I posted a couple of review comments. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue15758 ___ ___

[issue15758] FileIO.readall() has worst case O(n^2) complexity

2012-08-24 Thread Richard Oudkerk
Richard Oudkerk added the comment: After playing with the patch on Linux it seems that Linux much prefers the realloc() scheme to the list-of-chunks scheme. This new patch only does list-of-chunks on Windows. -- Added file: http://bugs.python.org/file26985/readall-combined.patch

[issue15758] FileIO.readall() has worst case O(n^2) complexity

2012-08-24 Thread Richard Oudkerk
Richard Oudkerk added the comment: Attached is an alternative benchmark program which does not use subprocess. -- Added file: http://bugs.python.org/file26986/readall-benchmark.py ___ Python tracker rep...@bugs.python.org

[issue15758] FileIO.readall() has worst case O(n^2) complexity

2012-08-24 Thread Richard Oudkerk
Changes by Richard Oudkerk shibt...@gmail.com: Removed file: http://bugs.python.org/file26952/push-thru-cat.py ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue15758 ___

[issue15758] FileIO.readall() has worst case O(n^2) complexity

2012-08-24 Thread Richard Oudkerk
Changes by Richard Oudkerk shibt...@gmail.com: Removed file: http://bugs.python.org/file26970/readall-combined.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue15758 ___

[issue15758] FileIO.readall() has worst case O(n^2) complexity

2012-08-24 Thread Antoine Pitrou
Antoine Pitrou added the comment: After playing with the patch on Linux it seems that Linux much prefers the realloc() scheme to the list-of-chunks scheme. What about the method call overhead in RawIO.readall(), and the different progression of buffer sizes? (the realloc scheme uses larger

[issue15758] FileIO.readall() has worst case O(n^2) complexity

2012-08-24 Thread Richard Oudkerk
Richard Oudkerk added the comment: What about the method call overhead in RawIO.readall(), and the different progression of buffer sizes? (the realloc scheme uses larger and larger read() sizes, while RawIO.readall() uses a constant read() size). For this benchmark the call overhead does

[issue15758] FileIO.readall() has worst case O(n^2) complexity

2012-08-24 Thread Antoine Pitrou
Antoine Pitrou added the comment: For this benchmark the call overhead does not seem to be noticeable, and using larger or adaptive read buffers does not seem to help either. (I have tried both on Linux.) Ok, thank you. By the way, not every non-Windows OS is Linux, so the patch is

[issue15758] FileIO.readall() has worst case O(n^2) complexity

2012-08-23 Thread Richard Oudkerk
Richard Oudkerk added the comment: Here is the patch (with the old ones removed). Note that the old code mishandled the case where _PyBytes_Resize() failed by assuming that the old bytes object would still be valid. I have assumed that stream psuedo-files will never claim to have a size

[issue15758] FileIO.readall() has worst case O(n^2) complexity

2012-08-23 Thread Antoine Pitrou
Antoine Pitrou added the comment: Here is the patch (with the old ones removed). Note that the old code mishandled the case where _PyBytes_Resize() failed by assuming that the old bytes object would still be valid. I have assumed that stream psuedo-files will never claim to have a size