High memory use when compiling many let bindings.

Forgot to mention: this is based on the report in http://www.haskell.org/pipermail/glasgow-haskell-users/2007-January/011866.html

See also #1875, #783

J_mem_vs_time.png shows the memory use against time for J.hs, with different values of numa/numb. It doesn't look like there is a complexity problem, but the constant factor seems high, using about 10k per binding. J_heap_profile.png is the heap profile for the largest case (400/20000), and peak usage works out at about 5k per binding (the difference presumably being due to the copying GC). Typecheck-Rename stands out, but there are also a few other large space users.

Interesting. I simplified it still more to a program of form:

a = let a0 = ()
    in let a1 = a0
        ...
    in let a10000 = a9999

and it still takes ages in the type checker, with a residency of 87M for 10,000 bindings. Splitting up the lets eliminates dependency analysis as the problem (in the type checker at least).

Do you think you might do a little bit more profiling to see where the typechecker/renamers costs are coming, for this simpler program?

Simon

Could

For J2, consider this module:

module J where

data Foo a b c d = Foo a b c d

a = let
    a0 = a3
    a1 = a0
    a2 = a1
    a3 = a2
 in Foo a0 a1 a2 a3

We get (tidied up a bit):

==================== Desugar ====================
Rec {
J.a :: forall t0 t1 t2 t3. J.Foo t0 t1 t2 t3
J.a = \ (@ t0) (@ t1) (@ t2) (@ t3) ->
  letrec {
    res :: J.Foo t0 t1 t2 t3
    res =
      letrec {
        tup :: forall ttup. (ttup, ttup, ttup, ttup)
        tup =
          \ (@ ttup) ->
            letrec {
              tupa1 :: ttup
              tupa1 = tupa0;
              tupa2 :: ttup
              tupa2 = tupa1;
              tupa3 :: ttup
              tupa3 = tupa2;
              tupa0 :: ttup
              tupa0 = tupa3; } in
            (tupa0, tupa3, tupa2, tupa1);
        a0 :: forall ttup. ttup
        a0 = \ (@ ttup) -> case tup @ ttup of _ { (tup0, _, _, _) -> tup0 };
        a3 :: forall ttup. ttup
        a3 = \ (@ ttup) -> case tup @ ttup of _ { (_, tup1, _, _) -> tup1 };
        a2 :: forall ttup. ttup
        a2 = \ (@ ttup) -> case tup @ ttup of _ { (_, _, tup2, _) -> tup2 };
        a1 :: forall ttup. ttup
        a1 = \ (@ ttup) -> case tup @ ttup of _ { (_, _, _, tup3) -> tup3 };
      } in
      J.Foo
        @ t0
        @ t1
        @ t2
        @ t3
        (a0 @ t0)
        (a1 @ t1)
        (a2 @ t2)
        (a3 @ t3); } in
  res
end Rec }

I think that most of the space usage comes from the tuple deconstructors. We should look into desugaring into something like this instead:

==================== Desugar ====================
Rec {
J.a :: forall t0 t1 t2 t3. J.Foo t0 t1 t2 t3
J.a = \ (@ t0) (@ t1) (@ t2) (@ t3) ->
  letrec {
    res :: J.Foo t0 t1 t2 t3
    res =
      letrec {
        a0 :: forall ttup. ttup
        a0 = \ (@ ttup) -> a3;
        a3 :: forall ttup. ttup
        a3 = \ (@ ttup) -> a2;
        a2 :: forall ttup. ttup
        a2 = \ (@ ttup) -> a1;
        a1 :: forall ttup. ttup
        a1 = \ (@ ttup) -> a0;
      } in
      J.Foo
        @ t0
        @ t1
        @ t2
        @ t3
        (a0 @ t0)
        (a1 @ t1)
        (a2 @ t2)
        (a3 @ t3); } in
  res
end Rec }

Simon was worried about losing dictionary sharing if we did so, so we need to check into whether that causes a performance problem, and whether we can get the sharing some other way.

This patch should help

Thu Jun  5 05:44:23 PDT 2008  simonpj@microsoft.com
  * Desugar multiple polymorphic bindings more intelligently

But I suspect there is something else going on too in the typechecker, perhaps chains of mutable variables.

But first let's see if there's any improvement.

Simon