Get: Avoid needless copies of input
authorBen Gamari <ben@smart-cactus.org>
Sun, 15 May 2016 21:55:43 +0000 (23:55 +0200)
committerBen Gamari <ben@smart-cactus.org>
Sun, 15 May 2016 22:01:03 +0000 (00:01 +0200)
My `b-tree` library seems to tickle a rather pathological behavior in
`binary`'s decoding logic, where `binary` will create many needless
copies of the input buffer by evaluating things of the form `B.concat
[B.empty, leftovers]`, where `leftovers` is large.

This resulted in runtimes of over two minutes when parsing a 50 MByte
file. With this fix run drops to less than 100 milliseconds.

src/Data/Binary/Get/Internal.hs

index cf2d012..b9a0818 100644 (file)
@@ -404,7 +404,11 @@ ensureN !n0 = C $ \inp ks -> do
     enoughChunks n str
       | B.length str >= n = Right (str,B.empty)
       | otherwise = Left (n - B.length str)
-    onSucc = B.concat
+    -- Sometimes we will produce leftovers lists of the form [B.empty, nonempty]
+    -- where `nonempty` is a non-empty ByteString. In this case we can avoid a copy
+    -- by simply dropping the empty prefix. In principle ByteString might want
+    -- to gain this optimization as well
+    onSucc = B.concat . dropWhile B.null
     onFail bss = C $ \_ _ -> Fail (B.concat bss) "not enough bytes"
 {-# INLINE ensureN #-}