Leak in mapping over ByteStrings #266

shachaf opened this Issue Feb 1, 2013 · 4 comments


None yet

3 participants


traversedStrictTree seems to have an issue that traversedStrict doesn't. Both of them are significantly slower than B.map.

Sample program:

import Control.Lens
import Control.Lens.Internal.ByteString
import qualified Data.ByteString as B
import Data.ByteString.Lens
import Data.Word

foo :: B.ByteString -> B.ByteString
--foo b = B.map (+1) b
--foo b = over (traversedStrictTree 0) (+1) b
foo b = over (traversedStrict 0) (+1) b
{-# NOINLINE foo #-}

main :: IO ()
main = do
  let b = B.replicate 50000000 97
  --let b = B.replicate 1000000000 97
  print $ B.length $ foo b

As an improvement for other things that partially addresses this, I've added RULES pragmas for converting down to simpler folds/traversals/maps when given larger types than is strictly necessary. It doesn't help with traversedStrictTree invoked directly, but when used through traversed, it'll convert down to using mapped, which then uses Data.ByteString.map directly.

I'd like to still address the core issue though.


The RULES pragmas currently cause occasional loops when enabled. See #272. Not sure how much they can be fixed if we want the users to be able to define some things in terms of more complex combinators.


The current version of traverseStrictTree uses a little over 2x the memory of the original traverseStrictTree implementation, and it's 3x slower, but this is the price we're going to pay for such incredible generality, I think.

map: 1.2s ~1.4GB
traverseStrict: 9.3s   ~1.5GB
traverseStrictTree: 32.6s ~3.6GB

(memory numbers eyeballed by me watching the Activity Monitor)

I don't think that the Tree version has a memory leak at this point (it has since been rewritten), I just think it's slightly less efficient in exchange for being less biased. What I'm not clear about at this point is what the advantage to the tree shape actually is.


I think if we don't have a leak any more, then a factor of 2x in exchange for a lack of bias strikes me as acceptable.

@ekmett ekmett closed this Aug 10, 2015
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment