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

Changes by Richard Oudkerk : -- resolution: -> fixed stage: patch review -> committed/rejected status: open -> closed ___ Python tracker ___

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

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 ___ Pytho

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

Antoine Pitrou added the comment: Looks fine to me. -- ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: http://m

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

Changes by Richard Oudkerk : Removed file: http://bugs.python.org/file30293/readall.patch ___ Python tracker ___ ___ Python-bugs-list mailing

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

Changes by Richard Oudkerk : Added file: http://bugs.python.org/file30295/readall.patch ___ Python tracker ___ ___ Python-bugs-list mailing li

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

Richard Oudkerk added the comment: New patch. -- ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.py

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

Changes by Richard Oudkerk : Removed file: http://bugs.python.org/file30291/readall.patch ___ Python tracker ___ ___ Python-bugs-list mailing

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

Changes by Richard Oudkerk : Added file: http://bugs.python.org/file30293/readall.patch ___ Python tracker ___ ___ Python-bugs-list mailing li

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

Changes by Richard Oudkerk : Removed file: http://bugs.python.org/file30287/readall.patch ___ Python tracker ___ ___ Python-bugs-list mailing

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

Changes by Richard Oudkerk : Added file: http://bugs.python.org/file26986/readall-benchmark.py ___ Python tracker ___ ___ Python-bugs-list mai

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

Changes by Richard Oudkerk : Removed file: http://bugs.python.org/file26985/readall-combined.patch ___ Python tracker ___ ___ Python-bugs-list

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

Richard Oudkerk added the comment: Updated patch adressing Antoine's comments. -- Added file: http://bugs.python.org/file30291/readall.patch ___ Python tracker ___ __

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

Antoine Pitrou added the comment: I posted a couple of review comments. -- ___ Python tracker ___ ___ Python-bugs-list mailing list Un

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

Changes by Richard Oudkerk : Removed file: http://bugs.python.org/file26986/readall-benchmark.py ___ Python tracker ___ ___ Python-bugs-list m

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

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: http://bugs.python.org/file30287/re

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

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 w

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

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

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 a

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

Changes by Richard Oudkerk : Removed file: http://bugs.python.org/file26970/readall-combined.patch ___ Python tracker ___ ___ Python-bugs-list

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

Changes by Richard Oudkerk : Removed file: http://bugs.python.org/file26952/push-thru-cat.py ___ Python tracker ___ ___ Python-bugs-list maili

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

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 ___

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

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

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 >

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

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 greate