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

[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 not seem to be noticeable, and using larger or adaptive read buffers does not seem to help either.  (I have tried both on Linux.)

> By the way, not every non-Windows OS is Linux, so the patch is wrong.

Wrong in the sense of not necessarily optimal for unknown platforms?  Well, the patch retains the old (intended) behaviour on other platforms, so I would call that conservative rather than wrong.  Are you suggesting switching behaviour depending on whether some macro is defined?


64-bit Linux with current patch (and using new benchmark):
amount = 1 MB; time taken = 0.003 secs; rate = 317.22 MB/s
amount = 2 MB; time taken = 0.007 secs; rate = 283.74 MB/s
amount = 4 MB; time taken = 0.011 secs; rate = 359.58 MB/s
amount = 8 MB; time taken = 0.020 secs; rate = 395.58 MB/s
amount = 16 MB; time taken = 0.030 secs; rate = 528.18 MB/s
amount = 32 MB; time taken = 0.051 secs; rate = 627.72 MB/s
amount = 64 MB; time taken = 0.088 secs; rate = 726.36 MB/s
amount = 128 MB; time taken = 0.133 secs; rate = 960.23 MB/s
amount = 256 MB; time taken = 0.258 secs; rate = 992.32 MB/s
amount = 512 MB; time taken = 0.482 secs; rate = 1062.30 MB/s

On 64-bit Linux with previous patch:
amount = 1 MB; time taken = 0.006 secs; rate = 158.07 MB/s
amount = 2 MB; time taken = 0.011 secs; rate = 177.23 MB/s
amount = 4 MB; time taken = 0.024 secs; rate = 169.32 MB/s
amount = 8 MB; time taken = 0.047 secs; rate = 170.39 MB/s
amount = 16 MB; time taken = 0.098 secs; rate = 163.65 MB/s
amount = 32 MB; time taken = 0.220 secs; rate = 145.19 MB/s
amount = 64 MB; time taken = 0.253 secs; rate = 253.32 MB/s
amount = 128 MB; time taken = 0.724 secs; rate = 176.80 MB/s
amount = 256 MB; time taken = 0.874 secs; rate = 293.02 MB/s
amount = 512 MB; time taken = 2.292 secs; rate = 223.38 MB/s

----------

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue15758>
_______________________________________