IO.Iteratee.takeUntil() is O(n^2) in the number of Chunks
The implementation looks like this:
The offending line are these:
So unfortunately we rescan the whole aggregated bytes variable for every new chunk.
def step(taken: ByteString)(input: Input): (Iteratee[ByteString], Input) = input match {
case Chunk(more) ⇒
val bytes = taken ++ more
val startIdx = bytes.indexOfSlice(delimiter, math.max(taken.length - delimiter.length, 0))
if (startIdx >= 0) {
val endIdx = startIdx + delimiter.length
(Done(bytes take (if (inclusive) endIdx else startIdx)), Chunk(bytes drop endIdx))
} else {
(Next(step(bytes)), Chunk.empty)
}
case EOF ⇒ (Failure(new EOFException("Unexpected EOF")), EOF)
case e @ Error(cause) ⇒ (Failure(cause), e)
}
The offending line are these:
val bytes = taken ++ more
val startIdx = bytes.indexOfSlice(delimiter, math.max(taken.length - delimiter.length, 0))
So unfortunately we rescan the whole aggregated bytes variable for every new chunk.
Leave a comment