On 12.10.16 09:31, Nathaniel Smith wrote:
But amortized O(1) deletes from the front of bytearray are totally
different, and more like amortized O(1) appends to list: there are
important use cases[1] that simply cannot be implemented without some
feature like this, and putting the implementation inside bytearray is
straightforward, deterministic, and more efficiently than hacking
together something on top. Python should just guarantee it, IMO.


[1] My use case is parsing HTTP out of a receive buffer. If deleting
the first k bytes of an N byte buffer is O(N), then not only does
parsing becomes O(N^2) in the worst case, but it's the sort of O(N^2)
that random untrusted network clients can trigger at will to DoS your

Deleting from buffer can be avoided if pass the starting index together with the buffer. For example:

    def read_line(buf: bytes, start: int) -> (bytes, int):
            end = buf.index(b'\r\n', start)
        except ValueError:
            return b'', start

        return buf[start:end], end+2

Python-Dev mailing list

Reply via email to