State monad - memory exhausted

[jaror]

@tomjaguarpaw

Indeed, as you found, that will make no difference. loopM always forces the Either to know whether it should go for another iteration, so there’s no benefit in forcing it before return.

It doesn’t make a difference for the leak, but it does make a difference in terms of total allocations. If you use $! in both places then you get this STG (this is all with -O1):

usesUpMemory2
  :: Int -> [Char] -> Identity (Either Int Int, [Char]) =
    \r [i eta]
        case usesUpMemory_m1 eta of { -- m1 is essentially 'test' in the source
        (,) a1 s' ->
        case a1 of {
        (,) a _ ->
        case a of {
          False ->
              case i of {
              I# x ->
              case +# [x 1#] of sat {
              __DEFAULT ->
              let { sat :: Int = I#! [sat]; } in
              let { sat :: Either Int Int = Left! [sat]; } in  (,) [sat s'];
              };
              };
          True ->
              let { sat :: Either Int Int = Right! [i]; } in  (,) [sat s'];
        };};};

This is nicely flat and only has two allocations for the I# and Left constructors. But if you leave out that outermost $! then you get:

usesUpMemory2
  :: Int -> [Char] -> Identity (Either Int Int, [Char]) =
    \r [i eta]
        case usesUpMemory_m1 eta of {
        (,) a1 s' ->
        case a1 of {
        (,) a _ ->
        let {
          sat :: Either Int Int =
              \u []
                  case a of {
                    False ->
                        case i of {
                        I# x ->
                        case +# [x 1#] of sat {
                        __DEFAULT -> let { sat :: Int = I#! [sat]; } in  Left [sat];
                        };
                        };
                    True -> Right [i];
                  };
        } in  (,) [sat s'];
        };};

Which creates an updateable closure (the \u []) a.k.a. a thunk. That thunk is put into the (,) that is used by the Writer. Of course this thunk will be forced immediately in the next generation, but I can’t imagine that’s good for performance.

@tomjaguarpaw

Do you mean that from strictness analysis (and knowledge of the definition of +) GHC can infer that the argument to Left would always be better off evaluated (and can never crash when evaluated), so it specialises it for that case?

Yes

@tomjaguarpaw

Tangentially, I never understood why GHC can’t rewrite functions to go form by itself.

You can enable it manually with -fstatic-argument-transformation (although for some reason it doesn’t seem to work in this case), but it is not always an optimisation. If the function is not inlined then it will a have to allocate a closure for that go function. @sgraf is working on improving it though. I believe the latest idea was to only apply this transformation if it makes it possible to inline the function.

@atravers

You mean there’s a substantial difference between using a local definition (go) and how loopM is currently defined

Yes. Compare the above listings with the result of using the better foldM that uses the recursive helper function go (to get this result you have to either use one of the two $!'s, it doesn’t matter which, or you have to compile with -O2):

usesUpMemory_$s$wgo :: Int# -> [Char] -> (# Int, [Char] #) =
    \r [sc eta]
        case m1 eta of {
        (,) a1 s' ->
        case a1 of {
        (,) a _ ->
        case a of {
          False ->
              case +# [sc 1#] of sat {
              __DEFAULT -> usesUpMemory_$s$wgo sat s';
              };
          True -> let { sat :: Int = I#! [sc]; } in  (#,#) [sat s'];
        };
        };
        };

Now GHC can see the loop instead of only a single iteration and it can remove the Either completely and unbox the Int. Now there is only one allocation left, but that is in the base case so that only happens once.

@ajbarber

Is it statically known that thunks can build up infinitely in a given block? A compiler warning would have a huge impact would it not, you just find it and fix it, by ! forcing or using a strict record field etc. as suggested here.

Kind of, but I think in most cases the thunks are forced rather quickly and no leak occurs. So you’d get a lot of false positives. Edsko de Vries from Well-Typed has written the nothunks library which can give warnings if there are thunks in your code: Being lazy without getting bloated - Well-Typed: The Haskell Consultants.

And all thunks are really potential memory leaks, because if GHC could predict that a thunk is always forced quickly then it wouldn’t have to create the thunk in the first place.

Personally, I’m also excited by ghc-debug (also from Well-Typed) which is a run time memory analysis tool. That tool can be used to find actual memory leaks at run time without all the false positives.