attoparsec holds on to all input until we're done parsing, using O(input) memory. It would probably be worth mentioning under "Performance considerations" in Data.Attoparsec.ByteString.
How is it with the lazy version, does it works the same? I would guess so, because there isn't really a way of telling attoparsec to "commit" to make clear that what we've come across so far is to be accepted, which means at any point it might back-track to the beginning.
Document space usage in the face of incremental input
This fixes gh-41.