It's security-critical that ReceiveBuffer's methods have linear worst-case complexity, and the code we use to accomplish this is non-trivial. There should be tests that we have successfully avoided the O(n^2) trap.
Automated tests for speed are difficult, but I think it's not so bad in this case, because quadratic behavior is so dramatic. So like we could do a worst case test (e.g. repeatedly read 1 byte from an N byte buffer) with N = k and N = 100*k. If we got it right then the latter will be 100x slower; if we got it wrong it'll be 10,000x slower. So we can check that it's less than 1,000x slower, and that gives us a large safety margin on both sides.
Edit: _obsolete_line_fold in _readers.py is another place where it'd be very easy to be accidentally quadratic.
It's security-critical that ReceiveBuffer's methods have linear worst-case complexity, and the code we use to accomplish this is non-trivial. There should be tests that we have successfully avoided the O(n^2) trap.
Automated tests for speed are difficult, but I think it's not so bad in this case, because quadratic behavior is so dramatic. So like we could do a worst case test (e.g. repeatedly read 1 byte from an N byte buffer) with N = k and N = 100*k. If we got it right then the latter will be 100x slower; if we got it wrong it'll be 10,000x slower. So we can check that it's less than 1,000x slower, and that gives us a large safety margin on both sides.
Edit:
_obsolete_line_foldin_readers.pyis another place where it'd be very easy to be accidentally quadratic.